Schönhage-Strassen-algoritmi

Schönhage-Strassen-kertomenetelmä ( eng.  Schönhage-Strassen-algoritmi ) on algoritmi suurten kokonaislukujen kertomiseen perustuen nopeaan Fourier-muunnokseen , vaatii ) bittioperaatioita, jossa on tulon binäärilukujen määrä [1] .

Sen keksivät Arnold Schönhage ja Volker Strassen vuonna 1971 [2] .

Itse asiassa se on menetelmä polynomien kertomiseksi yhdestä muuttujasta, se muuttuu lukujen kertomisalgoritmiksi, jos nämä luvut esitetään polynomeina lukujärjestelmän perustasta, ja tuloksen saatuaan ne siirretään numeroiden läpi. Jos esimerkiksi kerrotaan 157 ja 171 (desimaalimuodossa), suoritetaan seuraavat toiminnot:

• esitetään muodossa , ja  muodossa , missä ;
• polynomit kerrotaan ja käyttämällä nopeaa Fourier-muunnosta tulos on ;
• väliviivoja numeroiden kautta käytetään:, eli .

Myös algoritmissa voit kertoa modulo Fermat-luvut , jos käytät binäärilukujärjestelmää .

Menetelmää pidettiin asymptoottisesti nopeimpana menetelmänä vuodesta 1971 vuoteen 2007, jolloin keksittiin Fuhrer-algoritmi , jolla oli parempi kompleksisuusarvio [3] . Käytännössä Schönhage-Strassen-menetelmä alkaa päihittää aikaisemmat klassiset menetelmät, kuten Karatsuba-kertolasku ja Toom-Cook-algoritmi (Karatsuba-menetelmän yleistys), alkaen järjestyksen kokonaisluvuista - (10 000 - 40 000 desimaalista) [4 ] [5] [6] .

Muistiinpanot

1. ↑ Bürgisser P., Clausen M., Shokrollahi A. Algebrallinen kompleksiteoria. - Berliini: Springer-Verlag, 1997. - 618 s. — ISBN 3-540-60582-7 . .
2. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. - 1971. - Nro 7 . - s. 281-292.
3. ↑ Furer M. Nopeampi kokonaislukukerto  // STOC 2007 Proceedings. - 2007. - s. 57-66. Arkistoitu alkuperäisestä 25. huhtikuuta 2013.
4. ↑ Meter van R., Itoh KM Nopea kvanttimodulaarinen eksponentio  // Physical Review A. - 2005. - Vol. 71 .
5. ↑ Yleiskatsaus Magma V2.9 -ominaisuuksista, aritmeettinen osa Arkistoitu 2006-08-20 . : Keskustelee käytännön risteyspisteistä eri algoritmien välillä.
6. ↑ Coronado García LC Voiko Schönhagen kertolasku nopeuttaa RSA-salausta tai salauksen purkamista?  // Teknillinen korkeakoulu. – Darmstadt, 2005.