Schönhage-Strassen algoritm

Multiplikationsmetoden Schönhage-Strassen ( eng.  Schönhage-Strassen algorithm ) är en algoritm för att multiplicera stora heltal baserad på den snabba Fouriertransformen , kräver ) bitoperationer, där är antalet binära siffror i produkten [1] .

Uppfanns av Arnold Schönhage och Volker Strassen 1971 [2] .

Faktum är att det är en metod för att multiplicera polynom från en variabel, den förvandlas till en algoritm för att multiplicera tal, om dessa tal representeras som polynom från basen av talsystemet, och efter att ha mottagit resultatet, överförs genom siffrorna. Till exempel, för att multiplicera 157 och 171 (i decimalnotation) utförs följande operationer:

• representeras som , och  som , där ;
• polynom multipliceras och med den snabba Fouriertransformen blir resultatet ;
• bindestreck genom siffror används:, det vill säga .

Även i algoritmen kan du multiplicera modulo Fermat-tal , om du använder det binära talsystemet .

Metoden ansågs vara den asymptotiskt snabbaste metoden från 1971 till 2007, då Fuhrer-algoritmen med en bättre komplexitetsuppskattning uppfanns [3] . I praktiken börjar Schönhage-Strassen-metoden att överträffa tidigare klassiska metoder som Karatsuba-multiplikationen och Toom-Cook-algoritmen (en generalisering av Karatsuba-metoden), som börjar med ordningens heltal - (från 10 000 till 40 000 decimaler) [4 ] [5] [6] .

Anteckningar

1. ↑ Bürgisser P., Clausen M., Shokrollahi A. Algebraisk komplexitetsteori. - Berlin: Springer-Verlag, 1997. - 618 s. — ISBN 3-540-60582-7 . .
2. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. - 1971. - Nr 7 . - s. 281-292.
3. ↑ Furer M. Snabbare heltalsmultiplikation  // STOC 2007 Proceedings. - 2007. - S. 57-66. Arkiverad från originalet den 25 april 2013.
4. ↑ Meter van R., Itoh KM Snabb kvantmodulär exponentiering  // Physical Review A. - 2005. - Vol. 71 .
5. ↑ Översikt över Magma V2.9-funktioner, aritmetiskt avsnitt Arkiverad 2006-08-20 . : Diskuterar praktiska korsningspunkter mellan olika algoritmer.
6. ↑ Coronado García LC Kan Schönhage multiplikation påskynda RSA-krypteringen eller dekrypteringen?  // Tekniska högskolan. — Darmstadt, 2005.