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] .
Számelméleti algoritmusok | |
---|---|
Egyszerűség tesztek | |
Prímszámok keresése | |
Faktorizáció | |
Diszkrét logaritmus | |
GCD keresése | |
Modulo aritmetika | |
Számok szorzása és osztása | |
A négyzetgyök kiszámítása |