Montgomeryn algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. toukokuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Montgomery-algoritmi on tekniikka, jonka avulla voit nopeuttaa kerto- ja neliöintioperaatioita, joita tarvitaan nostettaessa lukua tehomoduuliin , kun moduuli on suuri (satojen bittien luokkaa). Sen ehdotti vuonna 1985 Peter Montgomery .

Montgomeryn algoritmi laskee kokonaisluvut a, b < n , r , GCD $(r,n) = 1$

$MonPro(a,b)=a\cdot b\cdot r^{{-1}}\mod {n}$

Sovelluksissa se yleensä otetaan , koska tässä tapauksessa jako jäännösjäännöksellä ja kertominen algoritmin sisällä ovat nopeita. $r=2^{k}$ $r$

Montgomeryn kertolasku

Määritellään luvun n -jäännös ( n -jäännös) muodossa . $a<n$ ${\bar {a}}=a\cdot r\mod {n}$

Montgomeryn algoritmi käyttää ominaisuutta, että joukko on täydellinen jäännösjärjestelmä , eli se sisältää kaikki luvut 0 - n-1 . $\{a\cdot r\mod {n}\mid 0\leqslant a\leqslant n-1\}$

MonPro laskee . Tuloksena on n-jäännös , koska ${\bar {c}}={\bar {a}}\cdot {\bar {b}}\cdot r^{{-1}}\mod {n}$ $c=a\cdot b\mod {n}$

${\bar {c}}={\bar {a}}\cdot {\bar {b}}\cdot r^{{-1}}\mod {n}=a\cdot r\cdot b\cdot r \cdot r^{{-1}}\mod {n}=c\cdot r\mod {n}$

Määritellään n' niin että . ja voidaan laskea käyttämällä laajennettua euklidista algoritmia . $r\cdot r^{{-1}}-n\cdot n'=1$ $r^{{-1}}$ $n'$

Toiminto $MonPro({\bar {a)],{\bar {b)))$

1. 2. 3. kun taas 4. palaa

t={\bar {a}}\cdot {\bar {b}}

u=(t+(t\cdot n'\mod {r})\cdot n)/r

(u>=n)u=un

u

Kun kertominen ja jako suoritetaan erittäin nopeasti, koska ne ovat vain bittisiirtoja, ja kun rivin 3 silmukka suoritetaan vain kerran. Siten Montgomeryn algoritmi on nopeampi kuin tavallinen laskenta , joka sisältää jakamisen n:llä. Kuitenkin n':n laskeminen ja lukujen muuntaminen n-jäännöksiksi ja päinvastoin ovat aikaa vieviä operaatioita, minkä seurauksena Montgomeryn algoritmin käyttäminen kahden luvun tuloa kerran laskettaessa vaikuttaa kohtuuttomalta. $r=2^{{k}}$ $r$ $r>n$ $a\cdot b\mod {n}$

Exponentiation by Montgomery

Montgomeryn algoritmin käyttäminen oikeuttaa itsensä nostettaessa lukua tehomoduuliin . $a^{{e}}\mod {n}$

Toiminto $ModExp(a,e,n)$

1. 2.

{\bar {a}}=a\cdot r\mod {n}

{\bar {x}}=1\cdot r\mod {n}

3. kun i=j-1 arvoon 0

{\bar {x}}=MonPro({\bar {x}},{\bar {x}})

jos sitten 4. paluu

e_{{i}}=1

{\bar {x}}=MonPro({\bar {x}},{\bar {a}})

x=MonPro({\bar {x)),1)

Luvun nostaminen potenssiin, jonka bittipituus on k "neliö ja kerro" -algoritmilla, sisältää k - 2k kertolaskua, jossa k on satojen tai tuhansien bittien luokkaa. Montgomeryn eksponentiointialgoritmia käytettäessä lisälaskutoimien määrä on kiinteä (laskelmat , , alussa ja lopussa), ja MonPro-operaatio on nopeampi kuin tavallinen modulo-kertolasku [1] , joten Montgomeryn eksponentioalgoritmi antaa suorituskyvyn lisäys verrattuna "neliö ja kerro" -algoritmiin . $n'$ ${\bar {a}}$ ${\bar {x}}$ $MonPro({\bar {x)),1)$

Algoritmin toteutus JavaScriptissä

powMod(a, e, m) { var r = 1; while (e > 0) { console.log('A='+a+', E='+e+', R='+r); if ((e & 1) == 0) { e = e >> 1; a = (a*a) % m; } muu { e = e - 1; r = (r*a) % m; } } console.log('A='+a+', E='+e+', R='+r); palauttaa r; }

Muistiinpanot

↑ Montgomeryn kertolaskualgoritmien analysointi ja vertailu Arkistoitu 1. heinäkuuta 2010.

Kirjallisuus

Montgomeryn kertolaskualgoritmien analysointi ja vertailu
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Luku 14. Tehokas toteutus // Handbook of Applied Cryptography (englanti) - CRC Press , 1996. - 816 s. — ( Diskreetti matematiikka ja sen sovellukset ) — ISBN 978-0-8493-8523-0