Content deleted Content added
→Usage in computers: suggest to link (via redirect) to appropriate section |
→Fourier transform methods: suggest to link Theta in each section, as these links are hard to find due to their shortness |
||
Line 352:
The ring ''Z/NZ'' would thus have a ''2m<sup>th</sup>'' root of unity, namely 8. Also, it can be checked that ''c<sub>k</sub> < N'', and thus no wrap around will occur.
The algorithm has a time complexity of [[Bachmann-Landau notation|Θ]](''n'' log(''n'') log(log(''n''))) and is used in practice for numbers with more than 10,000 to 40,000 decimal digits. In 2007 this was improved by Martin Fürer ([[Fürer's algorithm]]) <ref name="fürer_1">Fürer, M. (2007). "[https://web.archive.org/web/20130425232048/http://www.cse.psu.edu/~furer/Papers/mult.pdf Faster Integer Multiplication]" in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11–13, 2007, San Diego, California, USA</ref> to give a time complexity of ''n'' log(''n'') 2<sup>Θ([[iterated logarithm|log<sup>*</sup>]](''n''))</sup> using Fourier transforms over complex numbers. Anindya De, Chandan Saha, Piyush Kurur and Ramprasad Saptharishi<ref>Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008.</ref> gave a similar algorithm using [[modular arithmetic]] in 2008 achieving the same running time. In context of the above material, what these latter authors have achieved is to find ''N'' much less than ''2<sup>3k</sup> + 1'', so that ''Z/NZ'' has a ''2m<sup>th</sup>'' root of unity. This speeds up computation and reduces the time complexity. However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.
Using [[number-theoretic transform]]s instead of [[discrete Fourier transform]]s avoids [[rounding error]] problems by using modular arithmetic instead of [[floating point|floating-point]] arithmetic. In order to apply the factoring which enables the FFT to work, the length of the transform must be factorable to small primes and must be a factor of ''N''-1, where ''N'' is the field size. In particular, calculation using a Galois Field GF(''k''<sup>2</sup>), where ''k'' is a [[Mersenne Prime]], allows the use of a transform sized to a power of 2; e.g. ''k'' = 2<sup>31</sup>-1 supports transform sizes up to 2<sup>32</sup>.
| |||