정수 곱셈의 한계를 넘었다는 주장
이번 항목은 한 AI 연구 서비스가 공개한 ‘Auto Research’ 페이지예요. AI가 스스로 연구를 진행한다는 콘셉트인데, 내건 주제가 꽤 도발적이에요. 바로 정수 곱셈을 n log n보다 빠르게 하는 거거든요.
이게 왜 대담한 주장이냐면요. 2019년 데이비드 하비(David Harvey)와 요리스 반 데르 호번(Joris van der Hoeven)이 n자리 정수를 O(n log n) 시간에 곱하는 알고리즘을 발표했고, 학계는 이게 사실상 최적이라고 보고 있어요. 1971년 쇤하게(Schönhage)와 슈트라센(Strassen)이 n log n이 한계일 거라고 추측한 뒤 거의 50년 만에 그 목표에 도달한 결과였죠. 그러니 이보다 빠르다는 건 반세기 된 추측을 뒤집는 얘기예요. 그래서 더 꼼꼼하게 읽어야 하는데요, 판단하려면 이 분야의 역사부터 알아두면 좋아요.
초등학교 곱셈에서 n log n까지
초등학교에서 배운 세로 곱셈은 n자리 수끼리 곱할 때 한 자리 곱셈이 대략 n²번 필요해요. 1960년 소련의 대수학자... 아니, 정확히는 확률론의 대가였던 수학자 콜모고로프가 이게 최선일 거라고 추측했어요. 그런데 그 세미나에 있던 23살 학생 카라추바(Karatsuba)가 일주일 만에 반례를 찾아냈어요.
카라추바의 아이디어는 이래요. 큰 수를 앞부분 a와 뒷부분 b로 나누고, 다른 수도 c와 d로 나눠요. 원래는 ac, ad, bc, bd 네 번을 곱해야 하는데, ac와 bd를 구한 다음 (a+b)(c+d)를 한 번 곱하고 거기서 ac와 bd를 빼면 ad+bc가 나와요. 곱셈 네 번을 세 번으로 줄인 거죠. 이걸 재귀적으로 반복하면 복잡도가 약 n^1.585로 떨어져요.
그 뒤의 흐름을 정리하면 이래요.
- Toom-Cook: 수를 더 많은 조각으로 나눠서 지수를 계속 낮췄어요.
- 쇤하게-슈트라센(1971): FFT를 이용해 O(n log n log log n)을 달성했어요.
- 퓌러(Fürer, 2007): log log n 부분을 더 줄였어요.
- 하비-반 데르 호번(2019): 드디어 O(n log n)에 도달했어요.
계산 모델이라는 함정
n log n보다 빠르다는 주장을 볼 때 제일 먼저 물어야 할 건 어떤 계산 모델 기준이냐예요. 하비와 반 데르 호번의 결과는 멀티테이프 튜링 기계에서 비트 단위 연산 횟수를 세는 모델 기준이에요. 그런데 모델이 바뀌면 얘기도 달라져요. 예를 들어 쇤하게는 1980년에 포인터 기반의 특수한 기계 모델(SMM)에서는 정수 곱셈을 선형 시간에 할 수 있다는 걸 보였어요. 여러 비트를 한꺼번에 처리하는 워드 단위 연산을 한 번으로 치는 모델에서도 숫자가 달라지고요. 그러니까 모델만 슬쩍 바꿔도 n log n보다 빠른 것처럼 보이게 만들 수 있어요.
또 n log n이 정말 최적인지는 아직 증명되지 않았어요. 2019년 아프샤니(Afshani) 등이 불리언 회로에서 Ω(n log n) 하한을 보였지만, 네트워크 코딩에 관한 미해결 추측이 참이라는 전제가 붙어 있어요. 이 벽을 넘는 게 원리적으로 불가능하다고 단정할 수는 없지만, 넘었다고 주장하려면 아주 강력한 근거가 있어야 해요.
AI 연구 주장을 읽는 체크리스트
AI가 수학적 발견을 했다는 주장이 늘어나면서 걸러 읽는 눈이 더 중요해졌어요. 2025년에는 GPT-5가 에르되시 문제 여러 개를 풀었다는 주장이 나왔다가, 알고 보니 이미 논문으로 해결된 문제를 찾아낸 것이었다는 일도 있었죠. 이런 주장을 볼 때는 이걸 확인해 보세요. 계산 모델이 적혀 있는지, 수학적 증명인지 아니면 유한한 크기에서 잰 벤치마크인지(점근 복잡도는 벤치마크로 증명할 수 없어요), 워드 크기나 미리 계산된 테이블 같은 숨은 가정은 없는지, 전문가 검토나 Lean 같은 형식 검증을 거쳤는지요.
한국 개발자에게 주는 시사점
실무에서는 점근 복잡도보다 임계값이 더 중요해요. GMP 같은 큰 수 라이브러리는 수의 크기에 따라 세로 곱셈, 카라추바, Toom-Cook, FFT 기반 방식을 바꿔가며 써요. CPython 정수도 일정 크기를 넘으면 카라추바를 쓰고, 자바의 BigInteger도 카라추바와 Toom-Cook을 써요. RSA 같은 암호 연산도 결국 큰 정수 곱셈 위에서 돌아가니까, 이 원리를 알아두면 성능 튜닝할 때 시야가 넓어져요.
마무리
한 줄 정리: 정수 곱셈은 n log n이 사실상 종착역으로 여겨지는 만큼, 그보다 빠르다고 주장한다면 계산 모델과 증명부터 따져봐야 해요.
여러분은 AI가 내놓은 연구 결과를 어디까지 믿으시나요? AI의 자동 연구가 정말 새로운 수학을 만들어낼 날이 올까요, 아니면 당분간은 검증하기 쉬운 좁은 문제에서만 의미가 있을까요?
🔗 출처: Hacker News