Fuhrer-algoritmi

Führerin algoritmi on nopea menetelmä suurten kokonaislukujen kertomiseen . Algoritmin rakensi vuonna 2007 sveitsiläinen matemaatikko Martin Führer [1] Pennsylvanian yliopistosta asymptoottisesti nopeammaksi algoritmiksi kuin edeltäjänsä, vuonna 1971 julkaistu Schönhage-Strassen-algoritmi [2] . Suurien lukujen nopeasti moninkertaistuva ongelma on erittäin kiinnostava julkisen avaimen kryptografian alalla .

Fuhrer-algoritmin edeltäjä, Schönhage-Strassen-algoritmi, käytti nopeaa Fourier-muunnosta suurten lukujen kertomiseen ajassa , mutta sen kirjoittajat Arnold Schönhage ( saksa: Arnold Schönhage ) ja Volker Strassen olettivat , että on olemassa algoritmi, joka voi ratkaista ongelman kertoa suuria lukuja . Fuhrerin algoritmi [1] täytti näiden rajojen välisen aukon: sillä voidaan kertoa luvut ajassa , missä  on n : n iteroitu logaritmi . Algoritmien välinen aikaero tulee kuitenkin havaittavaksi erittäin suurilla kerrotuilla luvuilla (yli 10 000 000 000 000 [3] merkitsevää numeroa).  

Vuonna 2008 Anindaya De, Shenden Saha, Pyush Kurur ja Ramprasad Saptharishi rakensivat samanlaisen algoritmin, joka perustui pikemminkin modulaariseen kuin monimutkaiseen aritmetiikkaan, ja saavuttivat samalla ajoajan [4] .

Teoria

Convolution

Oletetaan, että kerromme luvut 123 ja 456 "sarakkeessa", mutta ilman siirtoa. Tulos näyttää tältä:

yksi 2 3
× neljä 5 6
6 12 kahdeksantoista
5 kymmenen viisitoista
neljä kahdeksan 12
neljä 13 28 27 kahdeksantoista

Tätä sekvenssiä (4, 13, 28, 27, 18) kutsutaan sekvenssien (1,2,3) ja (4,5,6) asykliseksi tai lineaariseksi konvoluutioksi . Kun tiedät kahden sekvenssin asyklisen konvoluution, tuotteen laskeminen ei ole vaikeaa: riittää, että suoritetaan siirto (esimerkiksi oikeimpaan sarakkeeseen jätetään 8 ja lisätään 1 sarakkeeseen, joka sisältää 27). Esimerkissämme tämä johtaa 56088:aan.

On muitakin taitoksia, joista voi olla hyötyä. Oletetaan, että syöttösekvenssit sisältävät n elementtiä (esimerkissä - 3). Tällöin tuloksena oleva lineaarinen konvoluutio sisältää n + n − 1 alkiota; jos otamme oikeanpuoleisen n elementin sarakkeen ja lisäämme n − 1 ':n vasemmanpuoleisen sarakkeen, tuloksena on ympyräkonvoluutio:

28 27 kahdeksantoista
+ neljä 13
28 31 31

Jos suoritamme rivityksen, tulos on sama kuin kerrottaessa lukuja modulo B n  − 1 (tässä esimerkissä se on 10 3  − 1 = 999). Suoritetaan siirto (ei vielä syklinen): (31+3=34, 28+3=31) ja saadaan 3141. Jos lisäämme vasen kolme oikeaan, saadaan 144 ≡ 56088 (mod 999) (The siirto on suoritettava syklisesti, eli 3 alemmasta 31:stä lisätään korkeampaan 31:een, 3 vastaanotetusta 34:stä lisätään 28:aan ja vastaanotetun 31:n kolminkerta lisätään alempaan luokkaan, eli kohtaan 1).

Kääntäen, jos otamme oikeanpuoleisimman n elementin sarakkeen ja vähennämme vasemmanpuoleisen n − 1 elementin sarakkeen, päädymme defoldiin:

28 27 kahdeksantoista
− neljä 13
28 23 5

Jos suoritamme palautuksen, tulos on sama kuin kertomalla luvut modulo B n  + 1. Tässä esimerkissä 10 3  + 1 = 1001 suoritetaan siirto (28, 23, 5) ja saa 3035 , kun taas 3035 ≡ 56088 (mod 1001). Käänteinen taitto voi sisältää negatiivisia lukuja, jotka voidaan poistaa käärimisen aikana samalla tekniikalla kuin pitkien vähennysten kohdalla.

Konvoluutiolause

Kuten muutkin nopeaan Fourier-muunnokseen perustuvat menetelmät, Fuhrer-algoritmi on pohjimmiltaan riippuvainen konvoluutiolauseesta, joka tarjoaa tehokkaan tavan laskea kahden sekvenssin syklinen konvoluutio. Hänen ideansa on:

Kahden vektorin syklinen konvoluutio voidaan löytää kunkin diskreetin Fourier-muunnoksen (DFT) kautta kertomalla tuloksena saadut vektorit elementti kerrallaan, minkä jälkeen seuraa käänteinen Fourier-muunnos (IDFT).

Tai kaavojen kautta:

CyclicConvolution(X, Y) = IDFT(DFT(X) DFT(Y)), missä: CyclicConvolution - syklinen konvoluutio , DFT - Diskreetti Fourier-muunnos , IDFT - käänteinen diskreetti Fourier-muunnos .

Jos laskemme DFT:n ja ODFT:n käyttämällä nopeaa Fourier-muunnosta ja kutsumme kertolaskualgoritmiamme rekursiivisesti kertoaksemme muunnettujen vektorien DFT(X) ja DFT(Y) syötteet(?), saamme tehokkaan algoritmin syklisen laskentaan. konvoluutio.

Tässä algoritmissa on paljon tehokkaampaa laskea käänteinen ympyräkonvoluutio; Kuten käy ilmi, konvoluutiolauseen hieman muunneltu versio voi tehdä juuri sen. Oletetaan, että vektorit X ja Y ovat pituudeltaan n ja a  on 2 n :n primitiivinen juuri (mikä tarkoittaa, että a 2 n = 1 ja kaikki a :n pienemmät potenssit eivät ole yhtä suuria kuin 1). Siten voimme määritellä kolmannen vektorin A , jota kutsutaan painovektoriksi ja jolla on seuraavat ominaisuudet:

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

Nyt voimme kirjoittaa:

Negasyklinen konvoluutio( X , Y ) = A −1 IDFT(DFT( A X ) DFT ( A Y )), missä NegacyclicConvolution — Käänteinen syklinen konvoluutio , DFT - Diskreetti Fourier-muunnos , IDFT - käänteinen diskreetti Fourier-muunnos .

Toisin sanoen se on sama paitsi että syötevektorit kerrotaan A:lla ja tulos kerrotaan A −1 :llä .

Soiton valinta

Diskreetti Fourier-muunnos on abstrakti operaatio, joka voidaan suorittaa mille tahansa algebralliselle renkaalle ; se on yleensä otettu kompleksilukujen kentästä, mutta itse asiassa kompleksisen aritmeettisen menetelmän käyttäminen riittävän tarkasti tarkkojen tulosten saamiseksi on hidasta ja tehotonta. Sen sijaan voimme käyttää lukuteoreettista muunnosa, joka muuttaa kokonaislukukentän modulo N jollekin kokonaisluvulle N.

Aivan kuten kompleksitasolla on minkä tahansa asteen primitiivisiä yksikköjuuria, voidaan mille tahansa n : lle valita sopiva N siten, että b on kertaluvun n  primitiivinen yksikköjuuri kokonaislukujen kentässä modulo N (toisin sanoen b n ≡ 1 (mod N ), ja kaikki b :n pienemmät potenssit eivät ole yhtä suuria kuin 1 mod N).

Algoritmi käyttää suurimman osan ajastaan ​​pienempien lukujen tulon rekursiivisesti suorittamiseen; algoritmin yksinkertaisessa versiossa tämä tapahtuu useissa paikoissa:

  1. Fast Fourier Transform -algoritmin sisällä primitiivinen yksikköjuuri b nostetaan toistuvasti potenssiin ja kerrotaan muilla luvuilla.
  2. Kun nostetaan yksikön a primitiivijuuri potenssiin saadakseen painon A vektori, ja sitten kerrotaan vektorit A tai A −1 muilla vektoreilla.
  3. Kun suoritetaan muunnettujen vektorien peräkkäinen kertolasku.

Tärkeintä on valita N, modulo 2 n  + 1 jollekin kokonaisluvulle n . Tällä menetelmällä on useita etuja useissa vakiojärjestelmissä, joissa suuret kokonaisluvut esitetään binäärimuodossa:

Ero edeltäjään

Suurin ero edeltäjäänsä on lukujen pakkauksen moninkertainen suoritus, joka tekee laskennallisesta monimutkaisuudesta, toisin kuin Schönhage-Strassen-algoritmissa, joka tekee monimutkaisuudesta.

Algoritmin rakenne

Kokonaislukujen tulo

Kokonaislukujen modulotulo Hajoaminen FFT Räjähtynyt tuote Käänteinen FFT Tuloksen koostumus

Muistiinpanot

  1. ↑ 1 2 Furer, M. (2007). « Faster Integer Multiplication Arkistoitu alkuperäisestä 25. huhtikuuta 2013. » julkaisussa 39. vuotuisen ACM-symposiumin tietojenkäsittelyteoria, 11.-13.6.2007 San Diego, Kalifornia, USA
  2. ↑ A. Schönhage ja V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), s. 281-292.
  3. ↑ Alexander J. Yee. Algoritmit y-cruncherissa - nopein ohjelma erilaisten vakioiden laskemiseen suurella tarkkuudella. (21. kesäkuuta 2014). Haettu 24. kesäkuuta 2014. Arkistoitu alkuperäisestä 30. maaliskuuta 2014.
  4. ↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Nopea kokonaislukukertominen modulaarista aritmetiikkaa käyttämällä. Symposium on Theory of Computation (STOC) 2008. arXiv : 0801.1416


 Lukuteoreettiset algoritmit
Yksinkertaisuustestit
Alkulukujen löytäminen
Faktorisointi
Diskreetti
logaritmi
GCD:n löytäminen
Modulo-aritmetiikka
Lukujen kerto- ja jakolasku
Neliöjuuren laskeminen