Editing Schönhage–Strassen algorithm (section)

=== 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]].