Editing Schönhage–Strassen algorithm (section)

{{short description|Multiplication algorithm}}{{More citations needed|date=October 2024}}
[[File:Integer multiplication by FFT.svg|thumb|350px|The Schönhage–Strassen algorithm is based on the [[Multiplication algorithm#Fourier transform method|fast Fourier transform (FFT) method of integer multiplication]]. This figure demonstrates multiplying 1234 &times; 5678 = 7006652 using the simple FFT method. Base 10 is used in place of base 2<sup>''w''</sup> for illustrative purposes. ]]
[[File:StrassenSchonhage1979 MFO8655.jpg|thumb|Schönhage (on the right) and Strassen (on the left) playing chess in [[Mathematical Research Institute of Oberwolfach|Oberwolfach]], 1979]]
The '''Schönhage–Strassen algorithm''' is an asymptotically fast [[multiplication algorithm]] for large [[integer]]s, published by [[Arnold Schönhage]] and [[Volker Strassen]] in 1971.<ref name="schönhage">{{cite journal |last1=Schönhage |first1=Arnold |author1-link=Arnold Schönhage |last2=Strassen |first2=Volker |author2-link=Volker Strassen |year=1971 |title=Schnelle Multiplikation großer Zahlen |language=de |trans-title=Fast multiplication of large numbers |journal=Computing |volume=7 |issue=3–4 |pages=281–292 |doi=10.1007/BF02242355 |s2cid=9738629 }}</ref> It works by recursively applying [[fast Fourier transform]] (FFT) over [[Modular arithmetic|the integers modulo]] <math>2^n + 1</math>. The run-time [[bit complexity]] to multiply two {{mvar|n}}-digit numbers using the algorithm is <math>O(n \cdot \log n \cdot \log \log n)</math> in [[big O notation|big {{mvar|O}} notation]].

The Schönhage–Strassen algorithm was the [[multiplication algorithm#Computational complexity of multiplication|asymptotically fastest multiplication method]] known from 1971 until 2007. It is asymptotically faster than older methods such as [[Karatsuba multiplication|Karatsuba]] and [[Toom–Cook multiplication]], and starts to outperform them in practice for numbers beyond about 10,000 to 100,000 decimal digits.<ref>
Karatsuba multiplication has asymptotic complexity of about <math>O(n^{1.58})</math> and Toom–Cook multiplication  has asymptotic complexity of about <math>O(n^{1.46}).</math>
{{pb}}
{{cite journal |first1=Rodney |last1=Van Meter |first2=Kohei M. |last2=Itoh |title=Fast Quantum Modular Exponentiation |journal=Physical Review |volume=71 |year=2005 |issue=5 |pages= 052320|doi=10.1103/PhysRevA.71.052320 |arxiv=quant-ph/0408006 |bibcode=2005PhRvA..71e2320V |s2cid=14983569 }}
{{pb}}
A discussion of practical crossover points between various algorithms can be found in: [http://magma.maths.usyd.edu.au/magma/Features/node86.html Overview of Magma V2.9 Features, arithmetic section] {{webarchive|url=https://web.archive.org/web/20060820053803/http://magma.maths.usyd.edu.au/magma/Features/node86.html |date=2006-08-20 }}
{{pb}}
Luis Carlos Coronado García, "[http://www.cdc.informatik.tu-darmstadt.de/~coronado/Vortrag/MoraviaCrypt-talk-s.pdf  Can Schönhage multiplication speed up the RSA encryption or decryption?] [https://web.archive.org/web/20110719095830/http://www.cdc.informatik.tu-darmstadt.de/~coronado/Vortrag/MoraviaCrypt-talk-s.pdf Archived]", ''University of Technology, Darmstadt'' (2005)
{{pb}}
The [[GNU Multi-Precision Library]] uses it for values of at least 1728 to 7808 64-bit words (33,000 to 150,000 decimal digits), depending on architecture. See:
{{pb}}
{{Cite web|title=FFT Multiplication (GNU MP 6.2.1)|url=https://gmplib.org/manual/FFT-Multiplication|access-date=2021-07-20|website=gmplib.org}}
{{pb}}
{{cite web|title=MUL_FFT_THRESHOLD|url=http://gmplib.org/devel/MUL_FFT_THRESHOLD.html|work=GMP developers' corner|access-date=3 November 2011|url-status=dead|archive-url=https://web.archive.org/web/20101124062232/http://gmplib.org/devel/MUL_FFT_THRESHOLD.html|archive-date=24 November 2010}}
{{pb}}
{{Cite web|title=MUL_FFT_THRESHOLD|url=https://gmplib.org/devel/thres/MUL_FFT_THRESHOLD|access-date=2021-07-20|website=gmplib.org}}
</ref> In 2007, Martin Fürer published [[Fürer's algorithm|an algorithm]] with faster asymptotic complexity.<ref>
Fürer's algorithm has asymptotic complexity <math display=inline>O\bigl(n \cdot \log n \cdot 2^{\Theta(\log^* n)}\bigr).</math>
{{pb}}
{{cite conference |last=Fürer |first=Martin |year=2007 |title=Faster Integer Multiplication |book-title=Proc. STOC '07 |conference=Symposium on Theory of Computing, San Diego, Jun 2007 |pages=57–66 |url=http://www.cse.psu.edu/~furer/Papers/mult.pdf |url-status=dead |archive-url=https://web.archive.org/web/20070305200654id_/http://www.cse.psu.edu/~furer/Papers/mult.pdf |archive-date=2007-03-05 }}{{pb}}{{Cite journal |last=Fürer |first=Martin |year=2009 |title=Faster Integer Multiplication |url=http://dx.doi.org/10.1137/070711761 |journal=SIAM Journal on Computing |volume=39 |issue=3 |pages=979–1005 |doi=10.1137/070711761 |issn=0097-5397}}
{{pb}}
Fürer's algorithm is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library. See: {{Cite book |last1=Covanov |first1=Svyatoslav |last2=Mohajerani |first2=Davood |last3=Moreno Maza |first3=Marc |last4=Wang |first4=Linxiao |title=Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation |chapter=Big Prime Field FFT on Multi-core Processors |date=2019-07-08 |chapter-url=https://dl.acm.org/doi/10.1145/3326229.3326273 |language=en |location=Beijing China |publisher=ACM |pages=106–113 |doi=10.1145/3326229.3326273 |isbn=978-1-4503-6084-5|s2cid=195848601 |url=https://hal.inria.fr/hal-02191652/file/cmmw-2019.ISSAC.sigconf.pdf }}
</ref> In 2019, David Harvey and [[Joris van der Hoeven]] demonstrated that multi-digit multiplication has theoretical <math>O(n\log n)</math> complexity; however, their algorithm has constant factors which make it impossibly slow for any conceivable practical problem (see [[galactic algorithm]]).<ref>{{cite journal | last1 = Harvey | first1 = David | last2 = van der Hoeven | first2 = Joris | author2-link = Joris van der Hoeven | doi = 10.4007/annals.2021.193.2.4 | issue = 2 | journal = [[Annals of Mathematics]] | mr = 4224716 | pages = 563–617 | series = Second Series | title = Integer multiplication in time <math>O(n \log n)</math> | volume = 193 | year = 2021| s2cid = 109934776 | url = https://hal.archives-ouvertes.fr/hal-02070778v2/file/nlogn.pdf }}</ref>

Applications of the Schönhage–Strassen algorithm include large computations done for their own sake such as the [[Great Internet Mersenne Prime Search]] and [[Approximations of π|approximations of {{mvar|π}}]], as well as practical applications such as [[Lenstra elliptic curve factorization]] via [[Kronecker substitution]], which reduces polynomial multiplication to integer multiplication.<ref>This method is used in INRIA's [https://gitlab.inria.fr/zimmerma/ecm ECM] library.</ref><ref>{{Cite web |title=ECMNET |url=https://members.loria.fr/PZimmermann/records/ecmnet.html |access-date=2023-04-09 |website=members.loria.fr}}</ref>