Schönhage–Strassen algorithm
[1] It works by recursively applying fast Fourier transform (FFT) over the integers modulo
The run-time bit complexity to multiply two n-digit numbers using the algorithm is
It is asymptotically faster than older methods such as Karatsuba and Toom–Cook multiplication, and starts to outperform them in practice for numbers beyond about 10,000 to 100,000 decimal digits.
[2] In 2007, Martin Fürer published an algorithm with faster asymptotic complexity.
[3] In 2019, David Harvey and Joris van der Hoeven demonstrated that multi-digit multiplication has theoretical
[4] 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 π, as well as practical applications such as Lenstra elliptic curve factorization via Kronecker substitution, which reduces polynomial multiplication to integer multiplication.
[5][6] This section has a simplified version of the algorithm, showing how to compute the product
bits, so in practical implementations, it is important to strike the right balance between the parameters
, the modulus is large enough to accommodate any carries that can result from multiplying
is a power of two, this can be achieved in logarithmic time using a fast Fourier transform.
Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts.
Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product
so that this pointwise product can be performed efficiently, either because it is a single machine word or using some optimized algorithm for multiplying integers of a (ideally small) number of words.
A root of unity under a finite field GF(r), is an element a such that
Same FFT algorithms can still be used, though, as long as θ is a root of unity of a finite field.
Doing several mod calculations against different N, can be helpful when it comes to solving integer product.
This formula can be used to generate sets of equations, that can be used in CRT (Chinese remainder theorem):[12] Furthermore;
and k is very small compared to rest of formula; one get This means: When something is very effective; K is bound above by
bits to store them, For implemantion details, one can read the book Prime Numbers: A Computational Perspective.
[15] This variant differs somewhat from Schönhage's original method in that it exploits the discrete weighted transform to perform negacyclic convolutions more efficiently.
Another source for detailed information is Knuth's The Art of Computer Programming.
[16] This section explains a number of important practical optimizations, when implementing Schönhage–Strassen.
), when weighting values in NTT (number theoretic transformation) approach.
In combination with CRT (Chinese Remainder Theorem) to find exact values of multiplication uv[19] Van Meter, Rodney; Itoh, Kohei M. (2005).
A discussion of practical crossover points between various algorithms can be found in: Overview of Magma V2.9 Features, arithmetic section Archived 2006-08-20 at the Wayback Machine Luis Carlos Coronado García, "Can Schönhage multiplication speed up the RSA encryption or decryption?
Archived", University of Technology, Darmstadt (2005) 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.
Fürer's algorithm is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library.
See: Covanov, Svyatoslav; Mohajerani, Davood; Moreno Maza, Marc; Wang, Linxiao (2019-07-08).
"Big Prime Field FFT on Multi-core Processors".
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation (PDF).
