Montgomery algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2018. május 21-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Montgomery-algoritmus egy olyan technika, amely lehetővé teszi a szorzási és négyzetesítési műveletek felgyorsítását, amikor egy számot teljesítménymodulussá emelünk, amikor a modulus nagy (több száz bites nagyságrendben). 1985-ben Peter Montgomery javasolta .

Adott a, b < n , r , GCD egész számok esetén a Montgomery algoritmus kiszámítja $(r,n)=1$

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

Alkalmazásokban általában ezt veszik , mivel ebben az esetben a maradékkal való osztás és az algoritmuson belüli szorzás gyors. $r=2^{k}$ $r$

Montgomery szorzás

Határozzuk meg a szám n - maradékát ( n - maradékát) így . $a<n$ ${\bar {a}}=a\cdot r\mod {n}$

A Montgomery-algoritmus azt a tulajdonságot használja, hogy a halmaz egy teljes maradékrendszer , azaz minden számot tartalmaz 0 - tól n-1- ig . $\{a\cdot r\mod {n}\mid 0\leqslant a\leqslant n-1\}$

A MonPro kiszámolja . Az eredmény az n-maradék , mivel ${\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}$

Határozzuk meg úgy, hogy . és kiszámítható a kiterjesztett euklideszi algoritmus segítségével . $r\cdot r^{{-1}}-n\cdot n'=1$ $r^{{-1}}$ $n'$

Funkció $MonPro({\bar {a)],{\bar {b)))$

1. 2. 3. míg 4. vissza

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

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

(u>=n)u=un

u

Amikor a szorzást és az osztást nagyon gyorsan hajtják végre, mivel ezek csak biteltolások, és amikor a 3. sorban lévő ciklus legfeljebb egyszer kerül végrehajtásra. Így a Montgomery-algoritmus gyorsabb, mint a szokásos számítás , amely n-nel való osztással jár. Az n' számítása és a számok n-es maradékmá alakítása és fordítva azonban időigényes műveletek, aminek következtében két szám egyszeri szorzatának kiszámításakor indokolatlannak tűnik a Montgomery-algoritmus alkalmazása. $r=2^{{k}}$ $r$ $r>n$ $a\cdot b\mod {n}$

Montgomery hatványozása

A Montgomery-algoritmus használata igazolja magát, amikor egy számot hatványmodulra emelünk . $a^{{e}}\mod {n}$

Funkció $ModExp(a,e,n)$

1. 2.

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

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

3. i=j-1 esetén 0-ra

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

ha akkor 4. vissza

e_{{i}}=1

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

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

Egy szám k bithosszúságú hatványra emelése a „négyzet és szorzás” algoritmussal k-tól 2k-ig terjedő szorzást tartalmaz, ahol k száz vagy több ezer bit nagyságrendje. A Montgomery hatványozási algoritmus használatakor a további számítások mennyisége rögzített (számítások , , elején és végén), és a MonPro művelet gyorsabb, mint a szokásos modulo szorzás [1] , így a Montgomery hatványozási algoritmus egy teljesítménynövekedés a "négyzet és szorzás" algoritmushoz képest . $n'$ ${\bár {a}}$ ${\bár {x}}$ $MonPro({\bar {x)),1)$

Az algoritmus implementációja JavaScriptben

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

Jegyzetek

↑ Montgomery szorzási algoritmusok elemzése és összehasonlítása Archiválva : 2010. július 1.

Irodalom

Montgomery szorzási algoritmusok elemzése és összehasonlítása
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Chapter 14. Efficient Implementation // Handbook of Applied Cryptography (angol) - CRC Press , 1996. - 816 p. — ( Diszkrét matematika és alkalmazásai ) — ISBN 978-0-8493-8523-0