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] .

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:

Szintén az algoritmusban szorozhatja meg a modulo Fermat-számokat , ha bináris számrendszert használ .

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] .

Jegyzetek

  1. Bürgisser P., Clausen M., Shokrollahi A. Algebrai komplexitáselmélet. - Berlin: Springer-Verlag, 1997. - 618 p. — ISBN 3-540-60582-7 . .
  2. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Számítástechnika. - 1971. - 7. sz . - P. 281-292.
  3. Furer M. Gyorsabb egész szorzás  // STOC 2007 Proceedings. - 2007. - P. 57-66. Archiválva az eredetiből 2013. április 25-én.
  4. Meter van R., Itoh KM Gyors kvantummoduláris hatványozás  // Physical Review A. - 2005. - 71. kötet .
  5. 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.
  6. Coronado García LC Felgyorsíthatja a Schönhage szorzás az RSA titkosítást vagy visszafejtést?  // Műszaki Egyetem. – Darmstadt, 2005.