초등학교 곱셈에서 시작된 반세기의 레이스
OpenAI의 수학 관련 GitHub 저장소에 2026년 9월 23일자로 'Integer multiplication below n log n'이라는 프리프린트가 올라왔어요. 제목 그대로, n자리 정수 두 개를 곱하는 데 n log n보다 적은 시간이 드는 알고리즘을 찾았다는 주장이에요. 이게 왜 큰일인지 알려면 곱셈 알고리즘의 역사를 잠깐 훑어봐야 해요.
곱셈 알고리즘 연대기
초등학교에서 배운 세로 곱셈으로 n자리 수끼리 곱하면 한 자리 곱셈을 대략 n²번 해야 해요. 1960년 수학자 콜모고로프는 세미나에서 “이게 최선일 것”이라는 추측을 내놨는데, 그 세미나에 참석한 23살 학생 카라추바가 일주일 만에 이걸 깨버렸어요. 핵심 트릭은 이거예요.
(a·B + b)(c·B + d) = ac·B² + (ad + bc)·B + bd
ad + bc = (a + b)(c + d) − ac − bd
원래 곱셈 4번(ac, ad, bc, bd)이 필요한데, 가운데 항을 이미 구한 ac와 bd로 재활용하면 3번으로 줄어요. 이걸 재귀로 반복하면 약 n^1.585까지 내려가요. 분할 정복의 교과서 같은 예제죠.
그 뒤로 숫자를 더 잘게 쪼개는 Toom–Cook이 나왔고, 1971년 쇤하게와 슈트라센이 FFT(고속 푸리에 변환)를 써서 O(n log n log log n)을 달성했어요. 이게 뭐냐면, 두 수를 곱하는 건 사실 자릿수 배열끼리의 '합성곱(convolution)'이에요. 그런데 FFT로 변환하면 합성곱이 같은 위치끼리의 단순 곱셈으로 바뀌거든요. 음악 파일을 주파수 성분으로 쪼갤 때 쓰는 바로 그 FFT예요. 이때 두 사람은 “궁극적인 한계는 n log n일 것”이라고 추측했어요.
2007년 퓌러(Martin Fürer)가 log log n 부분을 더 줄였고, 2019년 David Harvey와 Joris van der Hoeven이 마침내 O(n log n)을 달성했어요(2021년 Annals of Mathematics 게재). 많은 사람들이 “이제 끝났다”고 생각했죠. 추측대로라면 여기가 바닥이니까요.
n log n이 하한이라는 건 증명된 적이 없어요
여기서 중요한 포인트가 있어요. n log n이 최적이라는 건 추측이지 증명된 정리가 아니에요. 정수 곱셈에 대해 아무 조건 없이 증명된 의미 있는 하한은 사실상 없거든요. 2019년 Afshani 등의 연구가 '네트워크 코딩 추측'이라는 또 다른 미해결 추측이 참이라면 불리언 회로 모델에서 n log n이 하한이라는 걸 보이긴 했지만, 어디까지나 조건부예요.
그러니까 n log n이라는 벽은 강력한 정황 증거에 기댄 믿음이었던 셈이에요. 이번 결과가 맞다면 반세기 넘은 추측이 뒤집히는 거고, 어떤 모델에서의 결과냐에 따라 다른 추측과도 충돌할 수 있어서 이론 컴퓨터 과학계에서 아주 꼼꼼하게 검증받게 될 거예요.
꼭 확인해야 할 체크포인트
첫째, 계산 모델이에요. “몇 단계 걸린다”는 말은 어떤 기계를 가정하느냐에 따라 완전히 달라져요. Harvey–van der Hoeven 결과는 '다중 테이프 튜링 기계'라는 아주 보수적인 모델이 기준이에요. 반면 쇤하게는 1980년에 '저장소 수정 기계(SMM)'라는 다른 모델에서는 이미 선형 시간 곱셈이 가능하다는 걸 보였어요. 모델만 바꿔도 n log n보다 빠른 게 새삼스럽지 않을 수 있다는 뜻이죠. 그래서 이번 프리프린트가 어떤 모델에서 n log n 아래로 내려갔는지가 결과의 무게를 결정해요.
둘째, 동료 검토예요. 프리프린트는 아직 심사를 거치지 않은 원고예요. Harvey–van der Hoeven 논문도 공개부터 저널 게재까지 2년 가까이 걸렸어요.
셋째, AI의 역할이에요. OpenAI 저장소에 올라온 만큼 AI 모델이 연구에 어떻게 기여했는지도 관심사예요. 최근 AI가 수학 문제를 풀었다는 발표가 이어졌지만, 2025년엔 '미해결 에르되시 문제를 풀었다'던 주장이 알고 보니 이미 있던 문헌을 찾아낸 것이었다는 해프닝도 있었죠. 결과 검증과는 별개로 주장의 맥락을 차분히 볼 필요가 있어요.
실무에 영향이 있을까
솔직히 당장은 없을 가능성이 커요. Harvey–van der Hoeven 알고리즘만 해도 이른바 '은하급 알고리즘(galactic algorithm)'이에요. 이론상으로는 더 빠르지만, 그 이점이 드러나려면 숫자의 자릿수가 우주의 원자 수보다도 터무니없이 커야 하거든요. 실제로 GMP는 크기에 따라 세로 곱셈, 카라추바, Toom–Cook, FFT 기반 곱셈을 바꿔가며 쓰고, CPython의 int는 큰 수에 카라추바를, 자바 BigInteger는 카라추바와 Toom-Cook 3-way를 써요. RSA 같은 암호 연산은 2048~4096비트 수준이라 점근적 복잡도보다 상수와 하드웨어 최적화가 훨씬 중요하고요.
한국 개발자에게 주는 시사점
알고리즘 공부하는 분들에겐 이 레이스 자체가 훌륭한 교재예요. 카라추바는 코딩 테스트를 준비하다 보면 분할 정복 예제로 한 번쯤 만나게 되고, 백준 같은 온라인 저지에는 FFT를 써야만 시간 안에 통과하는 큰 수 곱셈 문제도 있어요. FFT로 다항식 곱셈을 직접 구현해보면 곱셈이 왜 합성곱인지가 손에 잡힐 거예요. 그리고 빅오는 숫자가 한없이 커질 때의 경향일 뿐, 실제 성능은 상수, 캐시, 메모리 접근 패턴이 좌우한다는 것도 이번 기회에 다시 새겨둘 만해요.
마무리
한 줄 정리: n log n은 증명된 벽이 아니라 다들 믿어온 벽이었고, 이번 프리프린트가 그 믿음에 도전장을 냈어요. 검증은 이제부터예요.
AI가 기여한 수학 결과가 늘어난다면, 여러분은 그 결과를 어떻게 믿게 될 것 같나요? Lean 같은 형식 검증을 필수로 붙여야 한다고 보시나요?
🔗 출처: Hacker News