Fuhrer algoritm

Führers algoritm är en snabb metod för att multiplicera [ stora heltal. Algoritmen byggdes 2007 av den schweiziske matematikern Martin Führer [1] vid University of Pennsylvania som en asymptotiskt snabbare algoritm än dess föregångare, Schönhage-Strassen-algoritmen , publicerad 1971 [2] . Problemet med att snabbt multiplicera ett stort antal är av stort intresse inom området för kryptografi med offentliga nyckel .

Föregångaren till Fuhrer-algoritmen, Schönhage-Strassen-algoritmen, använde den snabba Fourier-transformen för att multiplicera stora tal i tid , men dess författare, Arnold Schönhage ( tyska: Arnold Schönhage ) och Volker Strassen , gjorde antagandet att det finns en algoritm som kan lösa problemet med att multiplicera stora tal i . Fuhrers algoritm [1] fyllde i gapet mellan dessa gränser: den kan användas för att multiplicera tal i tid , där är den itererade logaritmen av n . Skillnaden i tid mellan algoritmerna blir dock märkbar vid mycket stora multiplicerade tal (större än 10 000 000 000 000 [3] signifikanta siffror). $O\vänster(n\logg n\logg\logg n\höger)$ $O\vänster(n\logg n\höger)$ $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $\log ^{*}n$

2008 byggde Anindaya De, Sheenden Saha, Pyush Kurur och Ramprasad Saptharishi en liknande algoritm baserad på modulär snarare än komplex aritmetik, samtidigt som de uppnådde samma körtid [4] .

Teori

Convolution

Låt oss säga att vi multiplicerar siffrorna 123 och 456 "i en kolumn", men utan att utföra överföringen. Resultatet kommer att se ut så här:

		ett	2	3
	×	fyra	5	6

		6	12	arton
	5	tio	femton
fyra	åtta	12

fyra	13	28	27	arton

Denna sekvens (4, 13, 28, 27, 18) kallas den acykliska eller linjära faltningen av sekvenserna (1,2,3) och (4,5,6). Genom att känna till den acykliska faltningen av två sekvenser är det inte svårt att beräkna produkten: det räcker för att utföra överföringen (till exempel i kolumnen längst till höger lämnar vi 8 och lägger till 1 till kolumnen som innehåller 27). I vårt exempel resulterar detta i 56088.

Det finns andra typer av veck som kan vara användbara. Låt oss säga att inmatningssekvenserna innehåller n element (i exemplet - 3). Då innehåller den resulterande linjära faltningen n + n − 1 element; om vi tar kolumnen längst till höger av n element och lägger till kolumnen längst till vänster av n − 1 ', får vi en cirkulär faltning:

	28	27	arton
+		fyra	13

	28	31	31

Om vi utför lindningen blir resultatet detsamma som vid multiplicering av tal modulo B n − 1 (i detta exempel är det 10 3 − 1 = 999). Låt oss genomföra överföringen (ännu inte cyklisk): (31+3=34, 28+3=31) och få 3141. Om vi lägger till de tre vänstra till den högra får vi 144 ≡ 56088 (mod 999) (The överföring måste utföras cykliskt, det vill säga 3 av de lägre 31 kommer att läggas till de högre 31, 3 av de mottagna 34 kommer att läggas till 28 och trippeln av de mottagna 31 kommer att läggas till den låga ordningen, det vill säga, till 1).

Omvänt, om vi tar kolumnen längst till höger med n element och subtraherar kolumnen längst till vänster med n − 1 element, slutar vi med en defoldning:

	28	27	arton
−		fyra	13

	28	23	5

Om vi genomför återställningen blir resultatet detsamma som när vi multiplicerar talen modulo B n + 1. I det här exemplet, 10 3 + 1 = 1001, utför vi överföringen (28, 23, 5) och få 3035 , medan 3035 ≡ 56088 (mod 1001). Det omvända vecket kan innehålla negativa tal, som kan tas bort under lindningen med samma teknik som för långa subtraktioner.

Konvolutionsteorem

Liksom andra metoder baserade på den snabba Fourier-transformen är Fuhrer-algoritmen i grunden beroende av faltningssatsen, vilket ger ett effektivt sätt att beräkna den cykliska faltningen av två sekvenser. Hennes idé är:

Den cykliska faltningen av två vektorer kan hittas genom den diskreta Fouriertransformen (DFT) för var och en, genom att multiplicera de resulterande vektorerna element för element, följt av den inversa Fouriertransformen (IDFT).

Eller genom formler:

CyclicConvolution(X, Y) = IDFT(DFT(X) DFT(Y)), där: CyclicConvolution - cyklisk faltning , DFT - Diskret Fourier Transform , IDFT - Inverse Discrete Fourier Transform .

Om vi beräknar DFT och ODFT med den snabba Fouriertransformen och anropar vår multiplikationsalgoritm rekursivt för att multiplicera ingångarna(?) för de transformerade vektorerna DFT(X) och DFT(Y), får vi en effektiv algoritm för att beräkna den cykliska veck.

I denna algoritm är det mycket mer effektivt att beräkna den inversa cirkulära faltningen; som det visar sig kan en något modifierad version av faltningssatsen göra just det. Antag att vektorerna X och Y har längden n och a är en primitiv rot av ordningen 2 n (vilket betyder att a 2 n = 1 och alla mindre potenser av a inte är lika med 1). Således kan vi definiera en tredje vektor A , kallad viktvektorn , som har följande egenskaper:

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

Nu kan vi skriva:

NegacyclicConvolution( X , Y ) = A −1 IDFT(DFT( A X ) DFT ( A Y )), där NegacyclicConvolution — Omvänd cyklisk faltning , DFT - Diskret Fourier Transform , IDFT - Inverse Discrete Fourier Transform .

Med andra ord, det är detsamma förutom att ingångsvektorerna multipliceras med A och resultatet multipliceras med A −1 .

Ringval

Den diskreta Fouriertransformen är en abstrakt operation som kan utföras på vilken algebraisk ring som helst ; det är vanligtvis hämtat från området komplexa tal, men att faktiskt använda komplex aritmetik med tillräcklig precision för att ge korrekta resultat är långsam och ineffektiv. Istället kan vi använda en talteoretisk transformation som transformerar fältet för heltal modulo N för något heltal N.

Precis som det finns primitiva enhetsrötter av vilken ordning som helst på det komplexa planet, för varje givet n kan vi välja ett lämpligt N så att b är en primitiv enhetsrot av ordningen n i fältet heltal modulo N (med andra ord, b n ≡ 1 (mod N ), och alla mindre potenser av b är inte lika med 1 mod N).

Algoritmen ägnar det mesta av sin tid åt att rekursivt exekvera produkten av mindre tal; i en enkel version av algoritmen händer detta på ett antal ställen:

Inuti Fast Fourier Transform-algoritmen höjs den primitiva enhetens rot b upprepade gånger till en potens och multipliceras med andra tal.
När man höjer en primitiv rot av enhet a till en potens för att erhålla en vektor med vikt A, och sedan multiplicerar vektorerna A eller A −1 med andra vektorer.
När man utför sekventiell multiplikation av de transformerade vektorerna.

Nyckelpunkten är att välja N, modulo 2 n + 1 för något heltal n . Denna metod har ett antal fördelar i ett antal standardsystem där stora heltal representeras i binärt:

Vilket antal som helst kan snabbt reduceras modulo 2 n + 1 med endast skift och addition.
Alla primitiva enhetsrötter i denna ring kan skrivas i formen 2 k ; därför kan vi multiplicera eller dividera vilket tal som helst med roten av enhet genom att använda en skiftning.
Element-för-element rekursiv multiplikation av de transformerade vektorerna kan göras med hjälp av deconvolution, som är snabbare än acyklisk faltning och redan har en modulo 2 n + 1 reduktion av resultatet.

Skillnad från föregångaren

Den största skillnaden från sin föregångare är den multipla exekveringen av talkomprimering, vilket ger beräkningskomplexitet, i motsats till en engångsanvändning i Schönhage-Strassen-algoritmen, vilket ger komplexitet $n \log n\,2^{O(\log^* n)}$ $n\log n\log \log n$

Algoritmstruktur

Produkt av heltal

Moduloprodukt av heltal Sönderfall FFT Exploderad produkt Omvänd FFT Resultatsammansättning

Anteckningar

↑ 1 2 Furer, M. (2007). « Snabbare heltalsmultiplikation Arkiverad från originalet den 25 april 2013. » i Proceedings of the trettionionth årliga ACM-symposium on Theory of computing, 11-13 juni 2007, San Diego, Kalifornien, USA
↑ A. Schönhage och V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), s. 281-292.
↑ Alexander J. Yee. Algoritmer i y-cruncher - det snabbaste programmet för att beräkna olika konstanter med hög noggrannhet. (21 juni 2014). Hämtad 24 juni 2014. Arkiverad från originalet 30 mars 2014. (obestämd)
↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Snabb heltalsmultiplikation med modulär aritmetik. Symposium on Theory of Computation (STOC) 2008. arXiv : 0801.1416

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm