Editing Schönhage–Strassen algorithm (section)

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