Algoritmul lui Montgomery

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 21 mai 2018; verificările necesită 5 modificări .

Algoritmul Montgomery este o tehnică care vă permite să accelerați operațiile de înmulțire și pătrare necesare la ridicarea unui număr la o putere modulo atunci când modulul este mare (de ordinul a sute de biți). A fost propusă în 1985 de Peter Montgomery .

Având în vedere numere întregi a, b < n , r , GCD algoritmul Montgomery calculează $(r,n)=1$

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

În aplicații, de obicei se ia , deoarece în acest caz, împărțirea cu rest și înmulțirea cu utilizate în interiorul algoritmului sunt rapide. $r=2^{k}$ $r$

Înmulțirea Montgomery

Să definim n -residue ( n -residue) al numărului ca . $a<n$ ${\bar {a}}=a\cdot r\mod {n}$

Algoritmul lui Montgomery folosește proprietatea că mulțimea este un sistem complet de reziduuri , adică conține toate numerele de la 0 la n-1 . $\{a\cdot r\mod {n}\mid 0\leqslant a\leqslant n-1\}$

MonPro calculează . Rezultatul este n-restul lui , deoarece ${\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}$

Să definim n' astfel încât . și poate fi calculat folosind algoritmul euclidian extins . $r\cdot r^{{-1}}-n\cdot n'=1$ $r^{{-1}}$ $n'$

Funcţie $MonPro({\bar {a)],{\bar {b)))$

1. 2. 3. în timp ce 4. întoarcere

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

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

(u>=n)u=un

u

Când înmulțirea și împărțirea cu sunt efectuate foarte rapid, deoarece sunt doar deplasări de biți, și când bucla din linia 3 va fi executată nu mai mult de o dată. Astfel, algoritmul lui Montgomery este mai rapid decât calculul obișnuit , care implică împărțirea la n. Cu toate acestea, calculul lui n’ și conversia numerelor în n-rămăși și invers sunt operații care consumă timp, drept urmare nu pare nerezonabil să se folosească algoritmul Montgomery atunci când se calculează produsul a două numere o dată. $r=2^{{k}}$ $r$ $r>n$ $a\cdot b\mod {n}$

Exponentiation de Montgomery

Folosirea algoritmului Montgomery se justifică atunci când ridică un număr la o putere modulo . $a^{{e}}\mod {n}$

Funcţie $ModExp(a,e,n)$

1. 2.

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

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

3. pentru i=j-1 până la 0

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

dacă atunci 4. întoarcere

e_{{i}}=1

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

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

Ridicarea unui număr la o putere cu lungimea de biți k prin algoritmul „pătrat și înmulțire” implică înmulțiri de la k la 2k, unde k este de ordinul a sute sau mii de biți. Când se folosește algoritmul de exponențiere Montgomery, cantitatea de calcule suplimentare este fixă (calcule , , la început și la sfârșit), iar operația MonPro este mai rapidă decât înmulțirea modulo obișnuită [1] , astfel încât algoritmul de exponențiere Montgomery va da o câștig de performanță în comparație cu algoritmul „pătrat și înmulțire ” . $n'$ ${\bar {a}}$ ${\bara {x}}$ $MonPro({\bar {x)),1)$

Implementarea algoritmului în JavaScript

powMod(a, e, m) { var r = 1; în timp ce (e > 0) { console.log('A='+a+', E='+e+', R='+r); dacă ((e & 1) == 0) { e = e >> 1; a = (a * a) % m; } altfel { e = e - 1; r = (r * a) % m; } } console.log('A='+a+', E='+e+', R='+r); întoarce r; }

Note

↑ Analizarea și compararea algoritmilor de multiplicare Montgomery Arhivat la 1 iulie 2010.

Literatură

Analizarea și compararea algoritmilor de multiplicare Montgomery
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Capitolul 14. Implementare eficientă // Handbook of Applied Cryptography (engleză) - CRC Press , 1996. - 816 p. — ( Matematică discretă și aplicațiile sale ) — ISBN 978-0-8493-8523-0