Schönhage-Strassenův algoritmus

Schönhage-Strassenova metoda násobení ( angl.  Schönhage-Strassen algorithm ) je algoritmus pro násobení velkých celých čísel založený na rychlé Fourierově transformaci , vyžaduje ) bitové operace, kde je počet binárních číslic v součinu [1] .

Vynalezli Arnold Schönhage a Volker Strassen v roce 1971 [2] .

Ve skutečnosti se jedná o metodu násobení polynomů z jedné proměnné, mění se v algoritmus pro násobení čísel, pokud jsou tato čísla reprezentována jako polynomy ze základu číselné soustavy, a po obdržení výsledku přenést přes cifry. Například pro násobení 157 a 171 (v desítkové soustavě) se provádějí následující operace:

• je reprezentováno jako , a  jako , kde ;
• polynomy jsou násobeny a pomocí rychlé Fourierovy transformace je výsledkem ;
• pomlčky přes číslice jsou použity:, to je, .

Také v algoritmu můžete násobit modulo Fermatova čísla , pokud používáte binární číselný systém .

Metoda byla považována za asymptoticky nejrychlejší metodu od roku 1971 do roku 2007, kdy byl vynalezen Fuhrerův algoritmus s lepším odhadem složitosti [3] . V praxi začíná Schönhage-Strassenova metoda překonávat dřívější klasické metody, jako je Karatsubovo násobení a Toom-Cookův algoritmus (zobecnění Karatsubovy metody), počínaje celými čísly řádu - (od 10 000 do 40 000 desetinných míst) [4 ] [5] [6] .

Poznámky

1. ↑ Bürgisser P., Clausen M., Shokrollahi A. Teorie algebraické složitosti. - Berlín: Springer-Verlag, 1997. - 618 s. — ISBN 3-540-60582-7 . .
2. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. - 1971. - č. 7 . - S. 281-292.
3. ↑ Furer M. Rychlejší celočíselné násobení  // STOC 2007 Proceedings. - 2007. - S. 57-66. Archivováno z originálu 25. dubna 2013.
4. ↑ Meter van R., Itoh KM Rychlá kvantová modulární umocňování  // Physical Review A. - 2005. - Vol. 71 .
5. ↑ Přehled funkcí Magma V2.9, aritmetická část Archivováno 20. 8. 2006 . : Probírá praktické body křížení mezi různými algoritmy.
6. ↑ Coronado García LC Může násobení Schönhage urychlit šifrování nebo dešifrování RSA?  // Technologická univerzita. — Darmstadt, 2005.