Montgomerys algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 maj 2018; kontroller kräver 5 redigeringar .

Montgomery-algoritmen är en teknik som gör att du kan påskynda multiplikations- och kvadreringsoperationerna som krävs när du höjer ett tal till en effektmodul när modulen är stor (i storleksordningen hundratals bitar). Föreslogs 1985 av Peter Montgomery .

Givet heltal a, b < n , r , GCD beräknar Montgomery-algoritmen $(r,n)=1$

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

I applikationer tas det vanligtvis , eftersom i det här fallet är division med en rest och multiplikation med inuti algoritmen snabba. $r=2^{k}$ $r$

Montgomery multiplikation

Låt oss definiera n -resten ( n -resten) av talet som . $a<n$ ${\bar {a}}=a\cdot r\mod {n}$

Montgomerys algoritm använder egenskapen att mängden är ett komplett restsystem , det vill säga den innehåller alla tal från 0 till n-1 . $\{a\cdot r\mod {n}\mid 0\leqslant a\leqslant n-1\}$

MonPro beräknar . Resultatet är n-resten av , eftersom ${\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}$

Låt oss definiera n' så att . och kan beräknas med den utökade euklidiska algoritmen . $r\cdot r^{{-1}}-n\cdot n'=1$ $r^{{-1}}$ $n'$

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

1. 2. 3. medan 4. återvända

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

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

(u>=n)u=un

u

När multiplikation och division med utförs mycket snabbt, eftersom de bara är bitförskjutningar, och när slingan på rad 3 inte kommer att utföras mer än en gång. Således är Montgomerys algoritm snabbare än den vanliga beräkningen , vilket innebär att dividera med n. Beräkningen av n' och omvandlingen av tal till n-rester och vice versa är dock tidskrävande operationer, som ett resultat av vilka det verkar orimligt att använda Montgomery-algoritmen när man beräknar produkten av två tal en gång. $r=2^{{k}}$ $r$ $r>n$ $a\cdot b\mod {n}$

Exponentiering av Montgomery

Att använda Montgomery-algoritmen motiverar sig själv när man höjer ett tal till en effektmodul . $a^{{e}}\mod {n}$

Fungera $ModExp(a,e,n)$

1. 2.

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

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

3. för i=j-1 ner till 0

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

om då 4. återvända

e_{{i}}=1

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

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

Att höja ett tal till en potens av bitlängd k med algoritmen "kvadrat och multiplicera" involverar multiplikationer av k till 2k, där k är i storleksordningen hundratals eller tusentals bitar. När du använder Montgomerys exponentieringsalgoritm, är mängden ytterligare beräkningar fast (beräkningar , , i början och i slutet), och MonPro-operationen är snabbare än den vanliga modulo multiplikationen [1] , så Montgomerys exponentieringsalgoritm kommer att ge en prestandavinst jämfört med algoritmen "kvaddra och multiplicera . " $n'$ ${\bar {a}}$ ${\bar {x}}$ $MonPro({\bar {x)),1)$

Implementering av algoritmen i JavaScript

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; } annat { e = e-1; r = (r * a) % m; } } console.log('A='+a+', E='+e+', R='+r); returnera r; }

Anteckningar

↑ Analysera och jämföra Montgomery Multiplication Algoritms Arkiverad 1 juli 2010.

Litteratur

Analysera och jämföra Montgomery Multiplikationsalgoritmer
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Kapitel 14. Effektiv implementering // Handbook of Applied Cryptography (engelska) - CRC Press , 1996. - 816 sid. — ( Diskret matematik och dess tillämpningar ) — ISBN 978-0-8493-8523-0