Schönhage-Strassen algoritme

Schönhage-Strassen multiplikationsmetoden ( eng.  Schönhage-Strassen algorithm ) er en algoritme til at multiplicere store heltal baseret på den hurtige Fourier transformation , kræver ) bitoperationer, hvor er antallet af binære cifre i produktet [1] .

Opfundet af Arnold Schönhage og Volker Strassen i 1971 [2] .

Faktisk er det en metode til at multiplicere polynomier fra en variabel, den bliver til en algoritme til at multiplicere tal, hvis disse tal er repræsenteret som polynomier fra bunden af ​​talsystemet, og efter at have modtaget resultatet, overføres gennem cifrene. For for eksempel at gange 157 og 171 (i decimalnotation) udføres følgende operationer:

• er repræsenteret som , og  som , hvor ;
• polynomier ganges og ved hjælp af den hurtige Fourier-transformation er resultatet ;
• bindestreger gennem cifre anvendes :, dvs.

Også i algoritmen kan du multiplicere modulo Fermat-tal , hvis du bruger det binære talsystem .

Metoden blev betragtet som den asymptotisk hurtigste metode fra 1971 til 2007, hvor Fuhrer-algoritmen med et bedre kompleksitetsestimat blev opfundet [3] . I praksis begynder Schönhage-Strassen-metoden at udkonkurrere tidligere klassiske metoder såsom Karatsuba-multiplikationen og Toom-Cook-algoritmen (en generalisering af Karatsuba-metoden), begyndende med heltal af orden - (fra 10.000 til 40.000 decimaler) [4 ] [5] [6] .

Noter

1. ↑ Bürgisser P., Clausen M., Shokrollahi A. Algebraic Complexity Theory. - 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. Hurtigere heltalsmultiplikation  // STOC 2007 Proceedings. - 2007. - S. 57-66. Arkiveret fra originalen den 25. april 2013.
4. ↑ Meter van R., Itoh KM Hurtig kvantemodulær eksponentiering  // Physical Review A. - 2005. - Vol. 71 .
5. ↑ Oversigt over Magma V2.9-funktioner, aritmetisk sektion Arkiveret 2006-08-20 . : Diskuterer praktiske krydsningspunkter mellem forskellige algoritmer.
6. ↑ Coronado García LC Kan Schönhage-multiplikation fremskynde RSA-krypteringen eller dekrypteringen?  // Teknisk Universitet. - Darmstadt, 2005.