Editing Schönhage–Strassen algorithm (section)

== Details ==
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>{{cite web |last1=Becker |first1=Hanno |last2=Hwang |first2=Vincent |last3=J. Kannwischer |first3=Matthias |last4=Panny |page=|date=2022|first4=Lorenz |title=Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms |url=https://eprint.iacr.org/2022/439.pdf}}</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 ''N'' ===
: <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 n<sup>th</sup> root, one sees that:<ref>{{cite web |last1=Lüders |year=2014|page=26|first1=Christoph |title=Fast Multiplication of Large Integers: Implementation and Analysis of the DKSS Algorithm |url=https://www.researchgate.net/publication/273701188}}</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 transform|number theoretic transformation]]) in Schönhage–Strassen. This means that we have to use {{mvar| &theta;}} to generate numbers in a finite field (for example <math>\mathrm{GF}( 2^n + 1 )</math>).

A root of unity under a finite field {{math|GF(''r'')}}, is an element a such that <math> \theta^{r-1} \equiv 1 </math> or <math> \theta^r \equiv \theta  </math>. For example {{math|GF(''p'')}}, where {{mvar|p}} 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 {{mvar|&theta;}} 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 {{mvar|k}}. 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 {{mvar|m}} is found using the [[modular multiplicative inverse]].