Algoritmul Schönhage-Strassen

Metoda de înmulțire Schönhage-Strassen ( ing. Algoritmul Schönhage-Strassen ) este un algoritm de înmulțire a numerelor întregi mari bazat pe transformarea Fourier rapidă , necesită ) operații pe biți, unde este numărul de cifre binare din produsul [1] . $O(N\cdot \log N\cdot \log \log N$ $N$

Inventat de Arnold Schönhage și Volker Strassen în 1971 [2] .

De fapt, este o metodă de înmulțire a polinoamelor dintr-o variabilă, se transformă într-un algoritm de înmulțire a numerelor, dacă aceste numere sunt reprezentate ca polinoame de la baza sistemului numeric, iar după primirea rezultatului, se transferă prin cifre. De exemplu, pentru a înmulți 157 și 171 (în notație zecimală), se efectuează următoarele operații:

este reprezentat ca , și ca , unde ; $157$ $x^{2}+5x+7$ $171$ $x^{2}+7x+1$ $x=10$
polinoamele sunt înmulțite și folosind transformata Fourier rapidă , rezultatul este ; $x^{2}+5x+7$ $x^{2}+7x+1$ $x^{4}+12x^{3}+43x^{2}+54x+7$
se aplică cratime prin cifre:, adică . $2x^{4}+6x^{3}+8x^{2}+4x+7$ $26847$

De asemenea, în algoritm, puteți înmulți numerele modulo Fermat , dacă utilizați sistemul de numere binar . $2^{{2^{n}}}+1$

Metoda a fost considerată cea mai rapidă metodă asimptotic din 1971 până în 2007, când a fost inventat algoritmul Fuhrer cu o estimare mai bună a complexității [3] . În practică, metoda Schönhage-Strassen începe să depășească metodele clasice anterioare, cum ar fi înmulțirea Karatsuba și algoritmul Toom-Cook (o generalizare a metodei Karatsuba), începând cu numere întregi de ordine - (de la 10.000 la 40.000 de zecimale) [4] ] [5] [6] . ${\displaystyle 10^{10000))$ $10^{40000}$

Note

↑ Bürgisser P., Clausen M., Shokrollahi A. Teoria complexității algebrice. - Berlin: Springer-Verlag, 1997. - 618 p. — ISBN 3-540-60582-7 . .
↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. - 1971. - Nr 7 . - P. 281-292.
↑ Furer M. Faster integer multiplication // STOC 2007 Proceedings. - 2007. - P. 57-66. Arhivat din original pe 25 aprilie 2013.
↑ Meter van R., Itoh KM Fast quantum modular exponentiation // Physical Review A. - 2005. - Vol. 71 .
↑ Prezentare generală a caracteristicilor Magma V2.9, secțiunea aritmetică Arhivată 20-08-2006 . : Discută puncte practice de încrucișare între diverși algoritmi.
↑ Coronado García LC Poate multiplicarea Schönhage să accelereze criptarea sau decriptarea RSA? // Universitatea de Tehnologie. — Darmstadt, 2005.

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin