Schönhage–Strassen algorithm
Template:Short descriptionTemplate:More citations needed
The Schönhage–Strassen algorithm is an asymptotically fast multiplication algorithm for large integers, published by Arnold Schönhage and Volker Strassen in 1971.<ref name="schönhage">Template:Cite journal</ref> It works by recursively applying fast Fourier transform (FFT) over the integers modulo <math>2^n + 1</math>. The run-time bit complexity to multiply two Template:Mvar-digit numbers using the algorithm is <math>O(n \cdot \log n \cdot \log \log n)</math> in [[big O notation|big Template:Mvar notation]].
The Schönhage–Strassen algorithm was the asymptotically fastest multiplication method known from 1971 until 2007. 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.<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> Template:Pb Template:Cite journal Template:Pb A discussion of practical crossover points between various algorithms can be found in: Overview of Magma V2.9 Features, arithmetic section Template:Webarchive Template:Pb Luis Carlos Coronado García, "Can Schönhage multiplication speed up the RSA encryption or decryption? Archived", University of Technology, Darmstadt (2005) Template: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: Template:Pb {{#invoke:citation/CS1|citation |CitationClass=web }} Template:Pb {{#invoke:citation/CS1|citation |CitationClass=web }} Template:Pb {{#invoke:citation/CS1|citation |CitationClass=web }} </ref> In 2007, Martin Fürer published 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> Template:Pb Template:Cite conferenceTemplate:PbTemplate:Cite journal Template:Pb Fürer's algorithm is used in the Basic Polynomial Algebra Subprograms (BPAS) open source library. See: Template:Cite book </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>Template:Cite journal</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 Template: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 ECM library.</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
DescriptionEdit
This section has a simplified version of the algorithm, showing how to compute the product <math>ab</math> of two natural numbers <math>a,b</math>, modulo a number of the form <math>2^n+1</math>, where <math>n=2^kM</math> is some fixed number. The integers <math>a,b</math> are to be divided into <math>D=2^k</math> blocks of <math>M</math> bits, so in practical implementations, it is important to strike the right balance between the parameters <math>M,k</math>. In any case, this algorithm will provide a way to multiply two positive integers, provided <math>n</math> is chosen so that <math>ab < 2^n+1</math>.
Let <math>n=DM</math> be the number of bits in the signals <math>a</math> and <math>b</math>, where <math>D=2^k</math> is a power of two. Divide the signals <math>a</math> and <math>b</math> into <math>D</math> blocks of <math>M</math> bits each, storing the resulting blocks as arrays <math>A,B</math> (whose entries we shall consider for simplicity as arbitrary precision integers).
We now select a modulus for the Fourier transform, as follows. Let <math>M'</math> be such that <math>DM'\ge 2M+k</math>. Also put <math>n'=DM'</math>, and regard the elements of the arrays <math>A,B</math> as (arbitrary precision) integers modulo <math>2^{n'}+1</math>. Observe that since <math>2^{n'} + 1 \ge 2^{2M+k} + 1 = D2^{2M}+1</math>, the modulus is large enough to accommodate any carries that can result from multiplying <math>a</math> and <math>b</math>. Thus, the product <math>ab</math> (modulo <math>2^n+1</math>) can be calculated by evaluating the convolution of <math>A,B</math>. Also, with <math>g=2^{2M'}</math>, we have <math>g^{D/2}\equiv -1\pmod{2^{n'}+1}</math>, and so <math>g</math> is a primitive <math>D</math>th root of unity modulo <math>2^{n'}+1</math>.
We now take the discrete Fourier transform of the arrays <math>A,B</math> in the ring <math>\mathbb Z/(2^{n'}+1)\mathbb Z</math>, using the root of unity <math>g</math> for the Fourier basis, giving the transformed arrays <math>\widehat A,\widehat B</math>. Because <math>D=2^k</math> is a power of two, this can be achieved in logarithmic time using a fast Fourier transform.
Let <math>\widehat C_i=\widehat A_i\widehat B_i</math> (pointwise product), and compute the inverse transform <math>C</math> of the array <math>\widehat C</math>, again using the root of unity <math>g</math>. The array <math>C</math> is now the convolution of the arrays <math>A,B</math>. Finally, the product <math>ab\pmod{2^n+1}</math> is given by evaluating <math display="block">ab\equiv \sum_j C_j2^{Mj}\mod{2^n+1}.</math>
This basic algorithm can be improved in several ways. Firstly, it is not necessary to store the digits of <math>a,b</math> to arbitrary precision, but rather only up to <math>n'+1</math> bits, which gives a more efficient machine representation of the arrays <math>A,B</math>. Secondly, it is clear that the multiplications in the forward transforms are simple bit shifts. With some care, it is also possible to compute the inverse transform using only shifts. Taking care, it is thus possible to eliminate any true multiplications from the algorithm except for where the pointwise product <math>\widehat C_i=\widehat A_i\widehat B_i</math> is evaluated. It is therefore advantageous to select the parameters <math>D,M</math> 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. Selecting the parameters <math>D,M</math> is thus an important area for further optimization of the method.
DetailsEdit
Every number in base B, can be written as a polynomial:
- <math> X = \sum_{i=0}^N {x_iB^i} </math>
Furthermore, multiplication of two numbers could be thought of as a product of two polynomials:
- <math>XY = \left(\sum_{i=0}^N {x_iB^i}\right)\left(\sum_{j=0}^N {y_iB^j}\right) </math>
Because, for <math> B^k </math>: <math>c_k =\sum_{(i,j):i+j=k} {a_ib_j} = \sum_{i=0}^k {a_ib_{k-i}} </math>, we have a convolution.
By using FFT (fast Fourier transform), used in the original version rather than NTT (Number-theoretic transform),<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> with convolution rule; we get
- <math> \hat{f}(a * b) = \hat{f}\left(\sum_{i=0}^k a_ib_{k-i} \right) = \hat{f}(a) \bullet \hat{f}(b). </math>
That is; <math> C_k = a_k \bullet b_k </math>, where <math> C_k </math> is the corresponding coefficient in Fourier space. This can also be written as: <math>\text{fft}(a * b) = \text{fft}(a) \bullet \text{fft}(b)</math>.
We have the same coefficients due to linearity under the Fourier transform, and because these polynomials only consist of one unique term per coefficient:
- <math> \hat{f}(x^n) = \left(\frac{i}{2\pi}\right)^n \delta^{(n)} </math> and
- <math> \hat{f}(a\, X(\xi) + b\, Y(\xi)) = a\, \hat{X}(\xi) + b\, \hat{Y}(\xi)</math>
Convolution rule: <math> \hat{f}(X * Y) = \ \hat{f}(X) \bullet \hat{f}(Y) </math>
We have reduced our convolution problem to product problem, through FFT.
By finding the FFT of the polynomial interpolation of each <math>C_k </math>, one can determine the desired coefficients.
This algorithm uses the divide-and-conquer method to divide the problem into subproblems.
Convolution under mod NEdit
- <math>c_k =\sum_{(i,j):i+j \equiv k \pmod {N(n)}} a_ib_j </math>, where <math> N(n) = 2^n + 1 </math>.
By letting:
- <math> a_i' = \theta^i a_i </math> and <math> b_j' = \theta^j b_j,</math>
where <math> \theta^N = -1 </math> is the nth root, one sees that:<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
- <math>
\begin{align} C_k & =\sum_{(i,j):i+j=k \equiv \pmod {N(n)}} a_ib_j = \theta^{-k} \sum_{(i,j):i+j \equiv k \pmod {N(n)}} a_i'b_j' \\[6pt] & = \theta^{-k} \left(\sum_{(i,j):i+j=k} a_i'b_j' + \sum_{(i,j):i+j=k+n} a_i'b_j' \right) \\[6pt] & = \theta^{-k}\left(\sum_{(i,j):i+j=k} a_ib_j\theta^k + \sum_{(i,j):i+j=k+n} a_ib_j\theta^{n+k} \right) \\[6pt] & = \sum_{(i,j):i+j=k} a_ib_j + \theta^n \sum_{(i,j):i+j=k+n} a_ib_j. \end{align} </math>
This mean, one can use weight <math> \theta^i </math>, and then multiply with <math> \theta^{-k} </math> after.
Instead of using weight, as <math> \theta^N = -1 </math>, in first step of recursion (when <math> n = N </math>), one can calculate:
- <math> C_k =\sum_{(i,j):i+j \equiv k \pmod {N(N)}} = \sum_{(i,j):i+j=k} a_ib_j - \sum_{(i,j):i+j=k+n} a_ib_j </math>
In a normal FFT which operates over complex numbers, one would use:
- <math display="block">
\exp \left(\frac{2k\pi i}{n}\right) =\cos\frac{2k\pi}{n} + i \sin \frac{2k\pi} n, \qquad k=0,1,\dots, n-1. </math>
- <math>
\begin{align} C_k & = \theta^{-k}\left(\sum_{(i,j):i+j=k} a_ib_j\theta^k + \sum_{(i,j):i+j=k+n} a_ib_j \theta^{n+k} \right) \\[6pt] & = e^{-i2\pi k/n} \left(\sum_{(i,j):i+j=k} a_ib_je^{i2\pi k /n} +\sum_{(i,j):i+j=k+n} a_ib_je^{i2\pi (n+k)/n} \right) \end{align} </math>
However, FFT can also be used as a NTT (number theoretic transformation) in Schönhage–Strassen. This means that we have to use Template:Mvar to generate numbers in a finite field (for example <math>\mathrm{GF}( 2^n + 1 )</math>).
A root of unity under a finite field Template:Math, is an element a such that <math> \theta^{r-1} \equiv 1 </math> or <math> \theta^r \equiv \theta </math>. For example Template:Math, where Template:Mvar is a prime number, gives <math>\{1,2,\ldots,p-1\}</math>.
Notice that <math> 2^n \equiv -1</math> in <math>\operatorname{GF}(2^n + 1)</math> and <math> \sqrt{2} \equiv -1 </math> in <math>\operatorname{GF}(2^{n+2} + 1) </math>. For these candidates, <math> \theta^N \equiv -1 </math> under its finite field, and therefore act the way we want .
Same FFT algorithms can still be used, though, as long as Template:Mvar is a root of unity of a finite field.
To find FFT/NTT transform, we do the following:
- <math>
\begin{align} C_k' & = \hat{f}(k) = \hat{f}\left(\theta^{-k}\left(\sum_{(i,j):i+j=k} a_ib_j\theta^k +\sum_{(i,j):i+j=k+n} a_ib_j\theta^{n+k} \right) \right) \\[6pt] C_{k+k}' & = \hat{f}(k+k) = \hat{f} \left(\sum_{(i,j):i+j=2k} a_i b_j \theta^k +\sum_{(i,j):i+j=n+2k} a_i b_j \theta^{n+k} \right) \\[6pt] & = \hat{f}\left(\sum_{(i,j):i+j=2k} a_i b_j \theta^k + \sum_{(i,j):i+j=2k+n} a_i b_j \theta^{n+k} \right) \\[6pt] & = \hat{f}\left(A_{k \leftarrow k}\right) \bullet \hat{f}(B_{k \leftarrow k}) + \hat{f}(A_{k \leftarrow k+n}) \bullet \hat{f}(B_{k \leftarrow k+n}) \end{align} </math>
First product gives contribution to <math> c_k </math>, for each Template:Mvar. Second gives contribution to <math> c_k </math>, due to <math>(i+j)</math> mod <math> N(n) </math>.
To do the inverse:
- <math> C_k = 2^{-m}\hat{f^{-1}} (\theta^{-k} C_{k+k}') </math> or <math> C_k = \hat{f^{-1}}(\theta^{-k} C_{k+k}') </math>
depending whether data needs to be normalized.
One multiplies by <math> 2^{-m} </math> to normalize FFT data into a specific range, where <math> \frac{1}{n} \equiv 2^{-m} \bmod N(n) </math>, where Template:Mvar is found using the modular multiplicative inverse.
Implementation detailsEdit
Why N = 2M + 1 mod NEdit
In Schönhage–Strassen algorithm, <math> N = 2^M + 1 </math>. This should be thought of as a binary tree, where one have values in <math> 0 \le \text{index} \le 2^{M}=2^{i+j} </math>. By letting <math> K \in [0,M] </math>, for each Template:Mvar one can find all <math> i+j = K </math>, and group all <math>(i,j)</math> pairs into M different groups. Using <math> i+j = k </math> to group <math>(i,j)</math> pairs through convolution is a classical problem in algorithms.<ref>Template:Cite book</ref>
Having this in mind, <math> N = 2^M + 1 </math> help us to group <math> (i,j) </math> into <math> \frac{M}{2^k} </math> groups for each group of subtasks in depth Template:Mvar in a tree with <math> N = 2^{\frac{M}{2^k}} + 1 </math>
Notice that <math> N = 2^M + 1 = 2^{2^L} + 1 </math>, for some L. This makes N a Fermat number. When doing mod <math> N = 2^M + 1 = 2^{2^L} + 1 </math>, we have a Fermat ring.
Because some Fermat numbers are Fermat primes, one can in some cases avoid calculations.
There are other N that could have been used, of course, with same prime number advantages. By letting <math> N = 2^k - 1 </math>, one have the maximal number in a binary number with <math> k+1 </math> bits. <math> N = 2^k - 1 </math> is a Mersenne number, that in some cases is a Mersenne prime. It is a natural candidate against Fermat number <math> N = 2^{2^L} + 1 </math>
In search of another NEdit
Doing several mod calculations against different Template:Mvar, can be helpful when it comes to solving integer product. By using the Chinese remainder theorem, after splitting Template:Mvar into smaller different types of Template:Mvar, one can find the answer of multiplication Template:Mvar <ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Fermat numbers and Mersenne numbers are just two types of numbers, in something called generalized Fermat Mersenne number (GSM); with formula:<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
- <math> G_{q,p,n} = \sum_{i=1}^p q^{(p-i)n} = \frac{q^{pn}-1}{q^n-1} </math>
- <math> M_{p,n} = G_{2,p,n} </math>
In this formula, <math> M_{2,2^k} </math> is a Fermat number, and <math> M_{p,1} </math> is a Mersenne number.
This formula can be used to generate sets of equations, that can be used in CRT (Chinese remainder theorem):<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
- <math>g^{\frac{(M_{p,n}-1)}{2}} \equiv -1 \pmod {M_{p,n}}</math>, where Template:Mvar is a number such that there exists an Template:Mvar where <math> x^2 \equiv g \pmod {M_{p,n}}</math>, assuming <math> N = 2^n </math>
Furthermore; <math>g^{2^{(p-1)n}-1} \equiv a^{2^n -1} \pmod {M_{p,n}}</math>, where Template:Mvar is an element that generates elements in <math> \{1,2,4,...2^{n-1},2^n\} </math> in a cyclic manner.
If <math> N=2^t </math>, where <math> 1 \le t \le n </math>, then <math> g_t = a^{(2^n-1)2^{n-t}} </math>.
How to choose K for a specific NEdit
The following formula is helpful, finding a proper Template:Mvar (number of groups to divide Template:Mvar bits into) given bit size Template:Mvar by calculating efficiency :<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
<math> E = \frac{\frac{2N}{K}+k}{n} </math> Template:Mvar is bit size (the one used in <math> 2^N + 1 </math>) at outermost level. Template:Mvar gives <math> \frac{N}{K} </math> groups of bits, where <math> K = 2^k </math>.
Template:Mvar is found through Template:Mvar and Template:Mvar by finding the smallest Template:Mvar, such that <math> 2N/K +k \le n = K2^x </math>
If one assume efficiency above 50%, <math> \frac{n}{2} \le \frac{2N}{K}, K \le n </math> and Template:Mvar is very small compared to rest of formula; one get
- <math> K \le 2\sqrt{N} </math>
This means: When something is very effective; Template:Mvar is bound above by <math> 2\sqrt{N} </math> or asymptotically bound above by <math> \sqrt{N} </math>
PseudocodeEdit
Following algorithm, the standard Modular Schönhage-Strassen Multiplication algorithm (with some optimizations), is found in overview through <ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Template:Olist
- T3MUL = Toom–Cook multiplication
- SMUL = Schönhage–Strassen multiplication
- Evaluate = FFT/IFFT
Further studyEdit
For implemantion details, one can read the book Prime Numbers: A Computational Perspective.<ref name="crandall">R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer, 2005. Section 9.5.6: Schönhage method, p. 502. Template:ISBN</ref> 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.<ref>Template:Cite book</ref>
OptimizationsEdit
This section explains a number of important practical optimizations, when implementing Schönhage–Strassen.
Use of other multiplications algorithm, inside algorithmEdit
Below a certain cutoff point, it's more efficient to use other multiplication algorithms, such as Toom–Cook multiplication.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Square root of 2 trickEdit
The idea is to use <math> \sqrt{2} </math> as a root of unity of order <math> 2^{n+2} </math> in finite field <math>\mathrm{GF}(2^{n+2} +1)</math> ( it is a solution to equation <math> \theta^{2^{n+2}} \equiv 1 \pmod {2^{n+2} + 1}</math>), when weighting values in NTT (number theoretic transformation) approach. It has been shown to save 10% in integer multiplication time.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Granlund's trickEdit
By letting <math> m = N + h </math>, one can compute <math>uv \bmod {2^N +1}</math> and <math>(u \bmod {2^h})(v \bmod 2^h)</math>. In combination with CRT (Chinese Remainder Theorem) to find exact values of multiplication Template:Mvar<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>