Schönhage-Strassen algoritmus

A Schönhage-Strassen szorzási módszer ( eng. Schönhage-Strassen algoritmus ) egy algoritmus nagy egész számok szorzására a gyors Fourier transzformáció alapján , megköveteli ) bitműveletek, ahol a szorzatban lévő bináris számjegyek száma [1] . $O(N\cdot \log N\cdot \log \log N$ $N$

Arnold Schönhage és Volker Strassen találta fel 1971-ben [2] .

Valójában ez a polinomok egy változóból való szorzásának módszere, számok szorzó algoritmusává alakul, ha ezeket a számokat a számrendszer alapjából polinomként ábrázoljuk, és az eredmény kézhezvétele után átvisszük a számjegyeket. Például 157 és 171 (tizedes jelöléssel) szorzásához a következő műveleteket kell végrehajtani:

mint , és mint , ahol ; $157$ $x^{2}+5x+7$ $171$ $x^{2}+7x+1$ $x=10$
a polinomokat megszorozzuk , és a gyors Fourier-transzformáció segítségével az eredmény: ; $x^{2}+5x+7$ $x^{2}+7x+1$ $x^{4}+12x^{3}+43x^{2}+54x+7$
a számjegyeken át kötőjeleket alkalmazunk:, azaz . $2x^{4}+6x^{3}+8x^{2}+4x+7$ $26847$

Szintén az algoritmusban szorozhatja meg a modulo Fermat-számokat , ha bináris számrendszert használ . $2^{{2^{n}}}+1$

A módszert az aszimptotikusan leggyorsabb módszernek tartották 1971-től 2007-ig, amikor is feltalálták a jobb komplexitásbecslésű Fuhrer-algoritmust [3] . A gyakorlatban a Schönhage-Strassen módszer kezd felülmúlni a korábbi klasszikus módszereket, mint például a Karatsuba szorzást és a Toom-Cook algoritmust (a Karatsuba módszer általánosítása), a sorrendű egész számokkal kezdve - (10 000 és 40 000 tizedesjegy között) [4 ] [5] [6] . ${\displaystyle 10^{10000))$ $10^{40000}$

Jegyzetek

↑ Bürgisser P., Clausen M., Shokrollahi A. Algebrai komplexitáselmélet. - Berlin: Springer-Verlag, 1997. - 618 p. — ISBN 3-540-60582-7 . .
↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Számítástechnika. - 1971. - 7. sz . - P. 281-292.
↑ Furer M. Gyorsabb egész szorzás // STOC 2007 Proceedings. - 2007. - P. 57-66. Archiválva az eredetiből 2013. április 25-én.
↑ Meter van R., Itoh KM Gyors kvantummoduláris hatványozás // Physical Review A. - 2005. - 71. kötet .
↑ A Magma V2.9 szolgáltatásainak áttekintése, aritmetikai rész Archivált 2006-08-20 . : Különböző algoritmusok közötti gyakorlati keresztezési pontokat tárgyal.
↑ Coronado García LC Felgyorsíthatja a Schönhage szorzás az RSA titkosítást vagy visszafejtést? // Műszaki Egyetem. – Darmstadt, 2005.

Számelméleti algoritmusok
Egyszerűség tesztek	Molnár Miller – Rabin Luca - Lemaire pepina Agrawala – Kayala – Szászország Nightingale - Strassen
Prímszámok keresése	Iteráció osztók felett Eratoszthenész szita Atkin szitája Szita Sundarama
Faktorizáció	Iteráció osztók felett Fermat módszer p −1 Pollard-módszer Pollard ρ-algoritmusa Lehmann módszer Elliptikus görbe módszer (Lenstra-algoritmus) Dixon algoritmusa Négyzet alakú szita
Diszkrét logaritmus	Gelfond-Shanks algoritmus Polig-Hellman algoritmus Pollard ρ-módszere Pollard kenguru algoritmusa Adleman algoritmusa COS algoritmus
GCD keresése	Euklidész algoritmusa Speciális algoritmus Bináris algoritmus
Modulo aritmetika	Montgomery algoritmusa Kínai maradék tétel
Számok szorzása és osztása	Karatsuba algoritmus Toom-Cook algoritmus Schönhage-Strassen algoritmus Führer algoritmus Harvey-van der Hoeven algoritmus Burnickel-Ziegler algoritmus
A négyzetgyök kiszámítása	Tonelli-Shanks algoritmus Berlekamp-Rabin algoritmus