Harvey 2026 정수 곱셈 알고리즘, O(n log n) 장벽을 깨다

요약

2026년 10월 David Harvey가 발표한 알고리즘은 두 개의 n비트 정수를 곱하는 데 o(n log n) 비트 연산을 달성하여, 2021년 Harvey-van der Hoeven 알고리즘의 오랜 O(n log n) 한계를 개선했습니다. 이 결과는 FFT 기반 컨볼루션에서 나비 연산의 수를 줄이는 새로운 텐서 증폭 기법과, 많은 독립적인 DFT를 평가하는 데 있어 예상보다 적은 슬라이스 호출을 사용하는 정교한 장치에 기반합니다. 저자가 모든 세부 사항을 확인하지는 않았지만, 광범위한 LLM 지원 검증으로 뒷받침된 커뮤니티의 합의는 이 주장이 그럴듯하고 잠재적으로 정확하다고 봅니다.

1. o(n log n)이 중요한 이유

핵심: 로그 인자의 지수를 1보다 낮추면 정수 곱셈이 고전적인 FFT에 기반한 어떤 알고리즘보다 점근적으로 빨라지며, O(n log n)이 수십 년 동안 최적이라는 믿음을 뒤집습니다.

의미:

실행 시간이 O(n (log n)^α)인 새로운 정수 곱셈 지수 α < 1을 도입합니다. 논문은 α≈0.9983을 보고하며, 이는 작지만 수학적으로 중요한 개선입니다.
Schönhage–Strassen(1971)과 2021년 O(n log n) 알고리즘 이후 유지된 장벽을 깨뜨립니다.
α를 더 낮추고, 아마도 추측된 ½ 하한을 향해 나아갈 수 있는 템플릿(텐서 증폭 + 장치 구성)을 제공합니다.

2. 새 알고리즘의 높은 수준 구조

2.1. 2021년 알고리즘 기반 구축

2021년 Harvey-van der Hoeven 알고리즘은 정수 곱셈을 링 R = C[y]/(y^r + 1)에 대한 **고차원 이산 푸리에 변환(DFT)**으로 축소합니다. 핵심 비용은 O(n log n) 항에 기여하는 FFT의 나비 연산에서 발생합니다.

2.2. 텐서 증폭 아이디어

A를 2 × 2 나비 행렬이라고 하자. 크기 2^m의 벡터에 A^{⊗ m}을 계산하려면 일반적으로 m·2^{m-1} 슬라이스 호출(나비 적용)이 필요합니다.
프로그램이 g < m 슬라이스 호출로 A^{⊗ m}을 계산할 수 있다면, 프로그램을 재귀적으로 텐서 확장하여 크기 2^{mk}의 입력에 대해 (g/m)^k의 인자를 얻습니다. 이는 n^{log g / log m} · 2^{n-1}, 즉 α = log g / log m < 1인 O(N (log N)^α)의 실행 시간을 산출합니다.
핵심은 적당한 m에 대해 그러한 프로그램을 찾은 다음 증폭하는 것입니다.

2.3. 장치

Harvey는 A^{⊗ m}의 W개의 독립적인 복사본을 평가하는 데 있어, 단순한 W·m 슬라이스 호출보다 적은 호출을 사용하는 장치를 설명합니다. 구성:

나비 행렬의 유니터리 버전 C(C = (1/√2)·B)로 작업합니다.
슬라이스 호출 Cv(방향별 나비)와 재라벨링(선형 순열)을 도입하며, 이는 부울 회로 모델에서 무료입니다.
레지스터를 F₂^m의 부분 공간으로 구성하고, 신중하게 선택된 직교 벡터를 사용하여 슬라이스 호출을 여러 레지스터를 동시에 진행시키는 제어된 연산으로 전환합니다.
부분 공간 간의 선형 관계를 활용하여 장치는 레지스터당 상수 인자를 절약하여 총 슬라이스 호출 수를 W·m에서 **W·m − Θ(|T|)**로 줄입니다. 여기서 |T|는 매개변수 h(기본 3원소 부분 집합의 크기)에 대해 3차입니다.

h가 충분히 클 때(h ≥ 22, 저자의 계산에 따르면), 절약이 오버헤드를 능가하여 슬라이스 호출의 순 감소를 제공합니다.

3. 구성의 상세 분석

3.1. 표기법 요약

C₂: 2차원 복소 벡터 공간.
(C₂)^{⊗ m}: 텐서 거듭제곱, 크기 2^m의 배열을 나타냄.
F₂^m: 이진 주소 공간; 벡터는 v로 표기.
Cv: 방향 v(즉, 쌍 (x, x+v))에 C를 적용하는 슬라이스 호출.
Φ_U: 부분 공간 U에 대한 Cv의 곱을 구현하는 선형 연산자.
U, U^⊥: 내적 아래 비퇴화 부분 공간과 그 직교 여공간.

3.2. 베이비 프로그램(섹션 7.5)

베이비 프로그램은 적당한 차원 h ≥ 8에서 작동하며 핵심 절약을 보여줍니다:

레지스터는 데이터(x_T, y_S), 측면(A_{S,T}), 중앙(c_i, c_*)으로 분할됩니다.
각 레지스터는 연관된 부분 공간 U를 가지며; 슬라이스 호출 Cv는 기본 값을 변경하지 않고 U를 업데이트합니다.
8단계의 시퀀스는 변환 단계(부분 공간을 성장시키기 위해 슬라이스 호출 추가)와 혼합 단계(동일한 부분 공간을 공유하는 레지스터의 선형 결합)를 번갈아 수행합니다.
총 슬라이스 호출 수는 **W·h − 2|T| + 2(h² + h)**이 되며, |T| = Θ(h³)이므로 충분히 큰 h에 대해 W·h보다 작습니다.

3.3. 메인 프로그램으로 확장(섹션 7.6)

메인 프로그램은 베이비 구성을 m = h³ 차원으로 끌어올립니다:

주소는 F₂^{m} = (F₂^{h})^{⊗ 3}, 즉 h × h × h 비트 배열이 됩니다.
데이터 레지스터는 이제 모든 삼중항 (a₁,a₂,a₃)∈T³에 대한 삼중항 x_{a₁,a₂,a₃}, **y_{a₁,a₂,a₃}**입니다.
세 단계는 각 텐서 차원을 따라 베이비 프로그램을 적용하며, 각 시간에 슬라이스 방향을 텐서 팽창시킵니다(v → v⊗v_{a₂}⊗v_{a₃} 등).
세 단계 후, 모든 레지스터는 C^{⊗ m}, 즉 컨볼루션에 필요한 전체 DFT로 변환됩니다.
총 슬라이스 호출 수는 **W·m − Θ(|T|²)**로 단순화되며, 큰 h에 대해 단순한 W·m보다 엄격히 작습니다.

4. 커뮤니티 반응 및 미해결 문제

댓글 작성자	핵심 요점	관련성
jdb1729	공식 Lean 증명이 존재함(α≈1-2⁻¹⁴·³⁸).	그럴듯함을 확인; 기계 검증 기반을 제공.
Kapura	저자가 논문을 읽지 않았다고 인정; LLM 설명에 의존.	LLM이 이해를 중재하는 새로운 연구 워크플로우를 강조.
kenferry	LLM(Claude Fable 5.1)이 인간과 달리 논문을 즉시 "이해"하는 것으로 보임.	AI가 정확성을 주장할 때 신뢰와 검증에 대한 우려 제기.
DannyBee	모델이 아직 g < m인 프로그램을 생성할 수 없음; 불가능할 수 있는 이유를 주장.	잠재적 장벽 제시: 각 슬라이스 호출은 0이 아닌 항목을 최대 두 배로 늘릴 수 있음.
flebron	O와 o 표기법의 구분을 강조.	개선이 엄격히 O(n log n) 미만임을 명확히 함.
Eji1700	실질적 영향은 현재 제한적; 개선은 점근적.	단기 응용에 대한 현실적 기대 설정.

미해결 기술 질문(저자가 식별):

선형 연산 수 및 합성 단위근 – 텐서 증폭과 어떻게 상호 작용하는지.
2021년 알고리즘에서 차원 매개변수 d 증가의 효과.
튜링 모델에서 데이터 재배열 비용 – 현재 무시되지만 완전한 복잡성 주장에 필수적.
더 작은 장치 찾기 – 더 나은 장치는 α를 더 낮출 수 있으며, 아마도 추측된 ½을 향해.

5. 관련 문제에 대한 결과

정수 곱셈의 지수: 논문은 α를 O(n (log n)^α)를 만족하는 지수의 하한으로 정의합니다. 새로운 경계는 α < 1을 보여주며, α = 1이라는 이전 믿음을 뒤집습니다.
네트워크 코딩 하한: Afshani et al. [AFKL19]의 부울 회로 하한과 결합하여, 결과는 Li–Li 네트워크 코딩 추측을 반증합니다.
유한 필드 위의 다항식 곱셈: 현재 최신 기술은 O(n log n · 4^{log* n}) [HvdH19]입니다. 이 기법들은 조건부 O(n (log n)^α) 알고리즘을 시사하지만, 무조건적인 개선은 아직 알려지지 않았습니다.
소수 열거 알고리즘: Harvey 자신의 소수 열거 작업 [Har26]은 F₂[x]에서 빠른 곱셈에 의존합니다; 조건부 다항식 곱셈 개선이 실현되면 새 경계가 병목 현상을 개선할 수 있습니다.

6. 발견에서 AI의 역할

Harvey의 메모는 이해의 대부분이 LLM(Claude Fable 5.1)에서 나왔다는 점에서 이례적입니다:

저자는 모델에게 밀도 높은 38페이지 원고를 설명하도록 요청했습니다.
모델은 단계별 설명을 제공하고, 중요한 증폭 트릭을 식별했으며, 베이비 프로그램의 무결성 검사 구현까지 생성했습니다.
이 워크플로우는 인간 전문가가 통찰력의 유일한 원천이 아니라 AI 추론의 조정자 역할을 하는 새로운 연구 패러다임을 보여줍니다.

커뮤니티의 엇갈린 반응—돌파구에 대한 흥분과 불투명한 AI 설명에 대한 과도한 의존에 대한 경계—은 AI 증강 수학에 대한 더 넓은 논쟁을 반영합니다.

7. 전망

알고리즘의 점근적 개선은 실재합니다(장치와 증폭 주장이 유효하다고 가정). 다음 이정표는:

형식적 검증(예: Lean 증명)으로 남아 있는 의심을 제거.
튜링 모델로의 확장, 데이터 이동 비용을 고려.
장치 최적화로 α를 더 낮추고, 아마도 이론적 ½ 장벽에 접근.
실용적 영향 탐구, 예: 상수 인자가 합리적이 되면 고정밀 라이브러리에 통합.

이러한 단계가 성공하면, 결과는 정수 곱셈에 대한 교과서 항목을 다시 쓸 뿐만 아니라 AI를 최전선 이론 컴퓨터 과학에서 일급 협력자로 굳힐 것입니다.

8. 참고 문헌

[AFKL19] Afshani, Freksen, Kamma, Larsen. Lower bounds for multiplication via network coding, ICALP 2019.
[Har26] D. Harvey. Faster enumeration of primes, arXiv:2606.22851, 2026.
[HvdH19] D. Harvey & J. van der Hoeven. Faster polynomial multiplication over finite fields, J. Complexity 54 (2019).
[HvdH21] D. Harvey & J. van der Hoeven. Integer multiplication in time O(n log n), Ann. of Math. 193 (2021).
[HvdH22] D. Harvey & J. van der Hoeven. Polynomial multiplication over finite fields in time O(n log n), J. ACM 69 (2022).
[HvdH25] D. Harvey & J. van der Hoeven. Integer multiplication is at least as hard as matrix transposition, arXiv:2503.22848, 2025.
[LL04] Z. Li & B. Li. Network coding in undirected networks, CISS 2004.
[TC26a-c] The Company. Integer multiplication below n log n (GitHub, 2026).
추가 커뮤니티 댓글은 기사 전체에 인용되어 있습니다.