.png){kind=icon}
.png){kind=icon}
Return
Integer multiplication in time O(n log n)
.png){kind=icon}
OA
AI
DOI：10.4007/annals.2021.193.2.4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present an algorithm that computes the product of two n-bit integers in O (n log n) bit operations, thus confirming a conjecture of Schonhage and Strassen from 1971. Our complexity analysis takes place in the multitape Turing machine model, with integers encoded in the usual binary representation. Central to the new algorithm is a novel Gaussian resampling technique that enables us to reduce the integer multiplication problem to a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two. These transforms may then be evaluated rapidly by means of Nussbaumer's fast polynomial transforms.
Keywords:
integer multiplication
FFT
complexity
Journal
IF:
5.3
Papers:
1.4K
Citations:
1.6W