Editing Schönhage–Strassen algorithm (section)

===Why ''N'' = 2{{sup|''M''}} + 1 mod ''N'' ===

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 {{mvar|K}} 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>{{cite book |last1=Kleinberg |first1=Jon |last2=Tardos |first2=Eva |title=Algorithm Design |date=2005 |publisher=Pearson |isbn=0-321-29535-8 |page=237 |edition=1|url=https://archive.org/details/AlgorithmDesign1stEditionByJonKleinbergAndEvaTardos2005PDF/page/n259/mode/2up}}</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 {{mvar|k}} 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 ''N'' ====

Doing several mod calculations against different {{mvar|N}}, can be helpful when it comes to solving integer product. By using the [[Chinese remainder theorem]], after splitting {{mvar|M}} into smaller different types of {{mvar|N}}, one can find the answer of multiplication {{mvar|xy}} <ref>{{cite web |last1=Gaudry |first1=Pierrick |last2=Alexander |first2=Kruppa |last3=Paul |first3=Zimmermann |title=A GMP-based implementation of Schönhage-Strassen's large integer multiplication algorithm |page=6 | year=2007|url=https://inria.hal.science/inria-00126462/file/fft.final.pdf}}</ref>

Fermat numbers and Mersenne numbers are just two types of numbers, in something called generalized Fermat Mersenne number (GSM); with formula:<ref>{{cite web |last1=S. Dimitrov |first1=Vassil |last2=V. Cooklev |first2=Todor |last3=D. Donevsky |page=2|year=1994|first3=Borislav |title=Generalized Fermat-Mersenne Number Theoretic Transform |url=https://www.researchgate.net/publication/3324542}}</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>{{cite web |last1=S. Dimitrov |first1=Vassil |last2=V. Cooklev |first2=Todor |last3=D. Donevsky |page=3|year=1994|first3=Borislav |title=Generalized Fermat-Mersenne Number Theoretic Transform |url=https://www.researchgate.net/publication/3324542}}</ref>

:<math>g^{\frac{(M_{p,n}-1)}{2}} \equiv -1  \pmod {M_{p,n}}</math>, where {{mvar|g}} is a number such that there exists an {{mvar|x}} 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 {{mvar|a}} 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>.