Fuhrerův algoritmus

Führerův algoritmus je rychlá metoda pro násobení velkých celých čísel. Algoritmus byl sestaven v roce 2007 švýcarským matematikem Martinem Führerem [1] z University of Pennsylvania jako asymptoticky rychlejší algoritmus než jeho předchůdce, Schönhage-Strassenův algoritmus , publikovaný v roce 1971 [2] . Problém rychlého množení velkých čísel je velmi zajímavý v oblasti kryptografie s veřejným klíčem .

Předchůdce Fuhrerova algoritmu, Schönhage-Strassenův algoritmus, používal rychlou Fourierovu transformaci k násobení velkých čísel v čase , ale jeho autoři Arnold Schönhage ( německy Arnold Schönhage ) a Volker Strassen předpokládali, že existuje algoritmus, který může vyřešit problém násobení velkých čísel v . Fuhrerův algoritmus [1] zaplnil mezeru mezi těmito hranicemi: lze jej použít k násobení čísel v čase , kde je iterovaný logaritmus n . Časový rozdíl mezi algoritmy je však patrný při velmi velkých násobených číslech (větších než 10 000 000 000 000 $O\left(n\log n\log \log n\right)$ $O\left(n\log n\vpravo)$ $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $\log ^{*}n$ [3] platné číslice).

V roce 2008 Anindaya De, Shenden Saha, Pyush Kurur a Ramprasad Saptharishi vytvořili podobný algoritmus založený spíše na modulární než komplexní aritmetice, přičemž dosáhli stejné doby běhu [4] .

Teorie

Konvoluce

Řekněme, že vynásobíme čísla 123 a 456 "ve sloupci", ale bez provedení převodu. Výsledek bude vypadat takto:

		jeden	2	3
	×	čtyři	5	6

		6	12	osmnáct
	5	deset	patnáct
čtyři	osm	12

čtyři	13	28	27	osmnáct

Tato sekvence (4, 13, 28, 27, 18) se nazývá acyklická nebo lineární konvoluce sekvencí (1,2,3) a (4,5,6). Při znalosti acyklické konvoluce dvou sekvencí není obtížné vypočítat součin: stačí provést převod (například ve sloupci úplně vpravo necháme 8 a přidáme 1 do sloupce obsahujícího 27). V našem příkladu to má za následek 56088.

Existují i jiné typy záhybů, které mohou být užitečné. Řekněme, že vstupní sekvence obsahují n prvků (v příkladu - 3). Výsledná lineární konvoluce pak obsahuje n + n − 1 prvků; pokud vezmeme pravý sloupec z n prvků a přidáme sloupec nejvíce vlevo z n − 1 ', skončíme s kruhovou konvolucí:

	28	27	osmnáct
+		čtyři	13

	28	31	31

Pokud provedeme zabalení, bude výsledek stejný jako při násobení čísel modulo B n − 1 (v tomto příkladu je to 10 3 − 1 = 999). Proveďme převod (zatím ne cyklický): (31+3=34, 28+3=31) a dostaneme 3141. Přičteme-li levou trojku k pravé, dostaneme 144 ≡ 56088 (mod 999) (The převod musí být prováděn cyklicky, to znamená, že 3 z nižších 31 se přidají k vyšším 31, 3 z přijatých 34 se přidají k 28 a trojnásobek přijatých 31 se přičte k nižšímu řádu, tzn. do 1).

A naopak, vezmeme-li sloupec zcela vpravo z n prvků a odečteme sloupec zcela vlevo od n − 1 prvků, skončíme s defoldingem:

	28	27	osmnáct
−		čtyři	13

	28	23	5

Pokud provedeme rollback, bude výsledek stejný, jako když vynásobíme čísla modulo B n + 1. V tomto příkladu 10 3 + 1 = 1001 provedeme přenos (28, 23, 5) a získejte 3035, zatímco 3035 ≡ 56088 (mod 1001). Reverzní sklad může obsahovat záporná čísla, která lze během balení odstranit stejnou technikou jako u dlouhých odečítání.

Konvoluční teorém

Stejně jako jiné metody založené na rychlé Fourierově transformaci je Fuhrerův algoritmus zásadně závislý na konvoluční větě, která poskytuje účinný způsob výpočtu cyklické konvoluce dvou sekvencí. Její myšlenka je:

Cyklickou konvoluci dvou vektorů lze nalézt pomocí diskrétní Fourierovy transformace (DFT) každého z nich, vynásobením výsledných vektorů prvek po prvku, následovaným inverzní Fourierovou transformací (IDFT).

Nebo pomocí vzorců:

CyclicConvolution(X, Y) = IDFT(DFT(X) DFT(Y)), kde: CyclicConvolution - cyklická konvoluce , DFT - Diskrétní Fourierova transformace , IDFT - Inverzní diskrétní Fourierova transformace .

Pokud vypočítáme DFT a ODFT pomocí rychlé Fourierovy transformace a zavoláme náš multiplikační algoritmus rekurzivně, abychom vynásobili vstupy(?) transformovaných vektorů DFT(X) a DFT(Y), skončíme s účinným algoritmem pro výpočet cyklického konvoluce.

V tomto algoritmu je mnohem efektivnější vypočítat inverzní kruhovou konvoluci; jak se ukazuje, mírně upravená verze konvoluční věty to dokáže. Předpokládejme, že vektory X a Y mají délku n a a je primitivní odmocnina řádu 2 n (což znamená, že a 2 n = 1 a všechny menší mocniny a nejsou rovny 1). Můžeme tedy definovat třetí vektor A , nazývaný hmotnostní vektor , který má následující vlastnosti:

A = ( aj ) , 0 ≤ j < n A −1 = ( a −j), 0 ≤ j < n

Nyní můžeme napsat:

Negacyklická konvoluce( X , Y ) = A −1 IDFT(DFT( A X ) DFT ( A Y )), kde Negacyclic Convolution — Reverzní cyklická konvoluce , DFT - Diskrétní Fourierova transformace , IDFT - Inverzní diskrétní Fourierova transformace .

Jinými slovy, je to stejné až na to, že vstupní vektory jsou vynásobeny A a výsledek je vynásoben A −1 .

Výběr prstenu

Jednotlivá Fourier transformace je abstraktní operace, která může být vykonávána na nějakém algebraickém prstenu ; to je obvykle převzato z pole komplexních čísel, ale ve skutečnosti používat komplexní aritmetiku s dostatečnou přesností poskytovat přesné výsledky je pomalé a neefektivní. Místo toho můžeme použít číselně teoretickou transformaci, která transformuje pole celých čísel modulo N na nějaké celé číslo N.

Stejně jako existují primitivní jednotkové kořeny libovolného řádu v komplexní rovině, pro libovolné dané n můžeme zvolit vhodné N takové, že b je primitivní jednotkový kořen řádu n v oboru celých čísel modulo N (jinými slovy b n ≡ 1 (mod N ), a všechny menší mocniny b se nerovnají 1 mod N).

Algoritmus tráví většinu času rekurzivně prováděním součinu menších čísel; v jednoduché verzi algoritmu se to děje na mnoha místech:

Uvnitř algoritmu rychlé Fourierovy transformace je primitivní jednotkový kořen b opakovaně umocněn na mocninu a násoben jinými čísly.
Když zvýšíme primitivní odmocninu jednotky a na mocninu , abychom dostali vektor o hmotnosti A, a pak vektory A nebo A −1 vynásobili jinými vektory.
Při provádění sekvenčního násobení transformovaných vektorů.

Klíčovým bodem je zvolit N, modulo 2 n + 1 pro nějaké celé číslo n . Tato metoda má řadu výhod v řadě standardních systémů, ve kterých jsou velká celá čísla reprezentována binárně:

Libovolné číslo lze rychle snížit modulo 2 n + 1 pouze pomocí posunu a sčítání.
Jakékoli primitivní jednotkové kořeny v tomto kruhu mohou být zapsány ve tvaru 2 k ; podle toho můžeme násobit nebo dělit libovolné číslo odmocninou jednoty pomocí posunu.
Element-by-element rekurzivní násobení transformovaných vektorů může být provedeno pomocí dekonvoluce, která je rychlejší než acyklická konvoluce a již má modulo 2 n + 1 redukci výsledku.

Rozdíl od předchůdce

Hlavním rozdílem od jeho předchůdce je vícenásobné provedení komprese čísel, která poskytuje výpočetní složitost, na rozdíl od jediného použití v algoritmu Schönhage-Strassen, který poskytuje složitost $n \log n\,2^{O(\log^* n)}$ $n\log n\log \log n$

Struktura algoritmu

Součin celých čísel

Modulový součin celých čísel Rozklad FFT Rozložený produkt Inverzní FFT Složení výsledku

Poznámky

↑ 1 2 Furer, M. (2007). « Faster Integer Multiplication Archivováno z originálu 25. dubna 2013. » ve sborníku z 39. výročního sympozia ACM o teorii výpočetní techniky, 11. až 13. června 2007, San Diego, Kalifornie, USA
↑ A. Schönhage a V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), str. 281-292.
↑ Alexander J. Yee. Algoritmy v y-cruncher - nejrychlejší program pro výpočet různých konstant s vysokou přesností. (21. června 2014). Získáno 24. června 2014. Archivováno z originálu 30. března 2014. (neurčitý)
↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Rychlé násobení celých čísel pomocí modulární aritmetiky. Symposium on Theory of Computation (STOC) 2008. arXiv : 0801.1416

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin