정수 곱셈의 O(n log n) 알고리즘 제안

수학자들이 정수 곱셈 문제의 계산 복잡도를 O(n log n)으로 줄이는 알고리즘을 제안했다. 이는 1971년 Schönhage-Strassen 알고리즘 이후 50년 만에 이론적 한계에 도달한 결과다. 기존에는 O(n log n log log n) 수준이었다.

실제 컴퓨터에서 쓰일 만큼 빠른지는 별개 문제지만, 수학적으로 정수 곱셈이 선형 시간과 로그 팩터만큼만 필요하다는 것을 증명한 것이 의미다. 암호화·과학 계산·빅인티저 라이브러리 개발자들은 이 결과가 미래 최적화의 이론적 근거를 제시한다고 본다.