Integer multiplication below n log n

정수 곱셈의 계산 복잡도를 n log n 아래로 내릴 수 있다는 것을 보인 논문이 주목받았다. 기존 Schönhage–Strassen 알고리즘은 n log n log log n 복잡도였는데, 새로운 접근이 이론적 한계에 더 가까워졌다는 의미다.

정수 곱셈은 암호화, 수치 계산, 빅데이터 처리 등 컴퓨터 과학의 기초가 되는 연산이다. 곱셈 알고리즘의 개선은 이들 분야 전반의 성능을 올리는 일이므로, 알고리즘 이론 커뮤니티에서는 수십 년 간 이 문제의 개선을 추구해왔다. 이번 성과는 그 오랜 노력에 한 걸음 더 나아간 것이다.