Algoritmul Fuhrer

Algoritmul lui Führer este o metodă rapidă pentru înmulțirea numere întregi mari. Algoritmul a fost construit în 2007 de către matematicianul elvețian Martin Führer [1] de la Universitatea din Pennsylvania ca un algoritm asimptotic mai rapid decât predecesorul său, algoritmul Schönhage-Strassen , publicat în 1971 [2] . Problema înmulțirii rapide a numerelor mari este de mare interes în domeniul criptografiei cu cheie publică .

Predecesorul algoritmului Fuhrer, algoritmul Schönhage-Strassen, a folosit transformata Fourier rapidă pentru a multiplica numere mari în timp , dar autorii săi, Arnold Schönhage ( germană: Arnold Schönhage ) și Volker Strassen , au presupus că există un algoritm care poate rezolva problema înmulțirii numerelor mari în . Algoritmul lui Fuhrer [1] a completat golul dintre aceste limite: poate fi folosit pentru a înmulți numere în timp , unde este logaritmul iterat al lui n . Cu toate acestea, diferența de timp dintre algoritmi devine vizibilă la numere înmulțite foarte mari (mai mari de 10.000.000.000.000). $O\stânga(n\log n\log \log n\dreapta)$ $O\stânga(n\log n\dreapta)$ $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $\log ^{*}n$ [3] cifre semnificative).

În 2008, Anindaya De, Shenden Saha, Pyush Kurur și Ramprasad Saptharishi au construit un algoritm similar bazat pe aritmetică modulară mai degrabă decât complexă, obținând în același timp același timp de rulare [4] .

Teorie

Convoluție

Să presupunem că înmulțim numerele 123 și 456 „în coloană”, dar fără a efectua transferul. Rezultatul va arăta astfel:

		unu	2	3
	×	patru	5	6

		6	12	optsprezece
	5	zece	cincisprezece
patru	opt	12

patru	13	28	27	optsprezece

Această secvență (4, 13, 28, 27, 18) se numește convoluția aciclică sau liniară a secvențelor (1,2,3) și (4,5,6). Cunoscând convoluția aciclică a două secvențe, nu este dificil să se calculeze produsul: este suficient să se efectueze transferul (de exemplu, în coloana din dreapta, lăsăm 8 și adăugăm 1 la coloana care conține 27). În exemplul nostru, rezultă 56088.

Există și alte tipuri de pliuri care pot fi utile. Să presupunem că secvențele de intrare conțin n elemente (în exemplu - 3). Atunci convoluția liniară rezultată conține n + n − 1 elemente; dacă luăm coloana din dreapta a n elemente și adăugăm coloana din stânga de n − 1 ', ajungem la o convoluție circulară:

	28	27	optsprezece
+		patru	13

	28	31	31

Dacă efectuăm împachetarea, rezultatul va fi același ca la înmulțirea numerelor modulo B n − 1 (în acest exemplu, este 10 3 − 1 = 999). Să efectuăm transferul (nu încă ciclic): (31+3=34, 28+3=31) și obținem 3141. Dacă adăugăm cele trei din stânga la cea dreaptă, obținem 144 ≡ 56088 (mod 999) (The transferul trebuie efectuat ciclic, adică 3 din cei 31 inferioare vor fi adăugate la 31 mai mari, 3 dintre cei 34 primiti vor fi adăugați la 28 și triplul celor 31 primiti va fi adăugat la ordinul inferior, adică la 1).

În schimb, dacă luăm coloana cea mai din dreapta de n elemente și scădem coloana din stânga de n - 1 elemente, ajungem la o depliere:

	28	27	optsprezece
−		patru	13

	28	23	5

Dacă efectuăm rollback-ul, rezultatul va fi același ca atunci când înmulțim numerele modulo B n + 1. În acest exemplu, 10 3 + 1 = 1001, efectuăm transferul (28, 23, 5) și obține 3035 , în timp ce 3035 ≡ 56088 (mod 1001). Pliul invers poate conține numere negative, care pot fi îndepărtate în timpul împachetarii folosind aceeași tehnică ca și pentru scăderile lungi.

Teorema de convoluție

Ca și alte metode bazate pe transformarea rapidă Fourier, algoritmul Fuhrer este dependent în mod fundamental de teorema de convoluție, care oferă o modalitate eficientă de a calcula convoluția ciclică a două secvențe. Ideea ei este:

Convoluția ciclică a doi vectori poate fi găsită prin transformarea Fourier discretă (DFT) a fiecăruia, prin înmulțirea vectorilor rezultați element cu element, urmată de transformata Fourier inversă (IDFT).

Sau prin formule:

Convoluție ciclică(X, Y) = IDFT(DFT(X) DFT(Y)), unde: CyclicConvolution - convoluție ciclică , DFT - transformată Fourier discretă , IDFT - Transformată Fourier discretă inversă .

Dacă calculăm DFT și ODFT folosind transformarea Fourier rapidă și apelăm recursiv algoritmul nostru de multiplicare pentru a multiplica intrările (?) ale vectorilor transformați DFT(X) și DFT(Y), ajungem la un algoritm eficient pentru calcularea ciclicului. convoluţie.

În acest algoritm, este mult mai eficient să se calculeze convoluția circulară inversă ; după cum se dovedește, o versiune ușor modificată a teoremei de convoluție poate face exact asta. Să presupunem că vectorii X și Y au lungimea n și a este o rădăcină primitivă de ordinul 2 n (ceea ce înseamnă că a 2 n = 1 și toate puterile mai mici ale lui a nu sunt egale cu 1). Astfel putem defini un al treilea vector A , numit vector de greutate , care are următoarele proprietăți:

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

Acum putem scrie:

Convoluție Negaciclică( X , Y ) = A −1 IDFT(DFT( A X ) DFT ( A Y )), unde NegacyclicConvolution — Convoluție ciclică inversă , DFT - transformată Fourier discretă , IDFT - Transformată Fourier discretă inversă .

Cu alte cuvinte, este același, cu excepția faptului că vectorii de intrare sunt înmulțiți cu A și rezultatul este înmulțit cu A -1 .

Selectarea soneriei

Transformata Fourier discretă este o operație abstractă care poate fi efectuată pe orice inel algebric ; este de obicei luat din domeniul numerelor complexe, dar folosirea de fapt a aritmeticii complexe cu suficientă precizie pentru a oferi rezultate precise este lentă și ineficientă. În schimb, putem folosi o transformare teoretică a numerelor care transformă câmpul numerelor întregi modulo N pentru un număr întreg N.

Așa cum există rădăcini de unitate primitive de orice ordin pe planul complex, pentru orice n dat putem alege un N potrivit astfel încât b este o rădăcină unitară primitivă de ordin n în câmpul numerelor întregi modulo N (cu alte cuvinte, b n ≡ 1 (mod N ), iar toate puterile mai mici ale lui b nu sunt egale cu 1 mod N).

Algoritmul își petrece cea mai mare parte a timpului executând recursiv produsul numerelor mai mici; într-o versiune simplă a algoritmului, acest lucru se întâmplă în mai multe locuri:

În cadrul algoritmului de transformare rapidă Fourier, rădăcina unității primitive b este ridicată în mod repetat la o putere și înmulțită cu alte numere.
Când ridicați o rădăcină primitivă a unității a la o putere pentru a obține un vector cu greutatea A și apoi înmulțiți vectorii A sau A -1 cu alți vectori.
La efectuarea înmulţirii secvenţiale a vectorilor transformaţi.

Punctul cheie este să alegeți N, modulo 2 n + 1 pentru un număr întreg n . Această metodă are o serie de avantaje într-un număr de sisteme standard în care numerele întregi mari sunt reprezentate în binar:

Orice număr poate fi redus rapid modulo 2 n + 1 folosind doar deplasare și adunare.
Orice rădăcină de unitate primitivă din acest inel poate fi scrisă sub forma 2 k ; în consecință, putem înmulți sau împărți orice număr cu rădăcina unității folosind o schimbare.
Înmulțirea recursivă element cu element a vectorilor transformați se poate face folosind deconvoluția, care este mai rapidă decât convoluția aciclică și are deja o reducere modulo 2 n + 1 a rezultatului.

Diferența față de predecesor

Principala diferență față de predecesorul său este execuția multiplă a compresiei numerelor, care oferă complexitate computațională, spre deosebire de o singură utilizare în algoritmul Schönhage-Strassen, care oferă complexitate. $n \log n\,2^{O(\log^* n)}$ $n\log n\log \log n$

Structura algoritmului

Produsul numerelor întregi

Produsul modular al numerelor întregi Descompunere FFT Produs explodat FFT inversă Compoziția rezultatului

Note

↑ 1 2 Furer, M. (2007). « Faster Integer Multiplication Arhivat din original pe 25 aprilie 2013. » în Proceedings of the39th annual ACM symposium on Theory of computing, 11-13 iunie 2007, San Diego, California, SUA
↑ A. Schönhage și V. Strassen, „Schnelle Multiplikation großer Zahlen”, Computing 7 (1971), pp. 281-292.
↑ Alexander J. Yee. Algoritmi în y-cruncher - cel mai rapid program pentru calcularea diferitelor constante cu precizie ridicată. (21 iunie 2014). Consultat la 24 iunie 2014. Arhivat din original la 30 martie 2014. (nedefinit)
↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Înmulțirea rapidă a întregilor folosind aritmetica modulară. Simpozion de teoria calculului (STOC) 2008. arXiv : 0801.1416

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin