Algoritmo de Montgomery

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 21 de mayo de 2018; las comprobaciones requieren 5 ediciones .

El algoritmo de Montgomery es una técnica que le permite acelerar las operaciones de multiplicación y elevación al cuadrado necesarias para elevar un número a un módulo de potencia cuando el módulo es grande (del orden de cientos de bits). Fue propuesta en 1985 por Peter Montgomery .

Dados los números enteros a, b < n , r , GCD , el algoritmo de Montgomery calcula $(r,n)=1$

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

En las aplicaciones se suele tomar , ya que en este caso, la división con resto y la multiplicación por usadas dentro del algoritmo son rápidas. $r=2^{k}$ $r$

Multiplicación de Montgomery

Definamos el n -residuo ( n -residuo) del número como . $un$ ${\bar {a}}=a\cdot r\mod {n}$

El algoritmo de Montgomery utiliza la propiedad de que el conjunto es un sistema de residuos completo , es decir, contiene todos los números del 0 al n-1 . $\{a\cdot r\mod {n}\mid 0\leqslant a\leqslant n-1\}$

MonPro calcula . El resultado es el n-resto de , ya que ${\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}$

Definamos n' de modo que . y se puede calcular utilizando el algoritmo euclidiano extendido . $r\cdot r^{{-1}}-n\cdot n'=1$ $r^{{-1}}$ $norte'$

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

1. 2. 3. mientras 4. volver

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

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

{\ estilo de visualización (u> = n) u = un}

tu

Cuando la multiplicación y la división por se realizan muy rápidamente, ya que son solo cambios de bits, y cuando el bucle en la línea 3 se ejecutará no más de una vez. Así, el algoritmo de Montgomery es más rápido que el cálculo habitual , que consiste en dividir por n. Sin embargo, el cálculo de n' y la conversión de números a n-restos y viceversa son operaciones que consumen mucho tiempo, por lo que no parece razonable utilizar el algoritmo de Montgomery al calcular el producto de dos números una vez. $r=2^{{k}}$ $r$ ${\ estilo de visualización r> n}$ $a\cdot b\mod {n}$

Exponenciación por Montgomery

Usar el algoritmo de Montgomery se justifica al elevar un número a un módulo de potencia . $a^{{e}}\mod{n}$

Función $ExpMod(a,e,n)$

1. 2.

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

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

3. para i=j-1 hasta 0

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

si entonces 4. volver

e_{{i}}=1

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

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

Elevar un número a una potencia de longitud de bits k mediante el algoritmo "cuadrar y multiplicar" implica k a 2k multiplicaciones, donde k es del orden de cientos o miles de bits. Cuando se usa el algoritmo de exponenciación de Montgomery, la cantidad de cálculos adicionales es fija (cálculos , , al principio y al final), y la operación MonPro es más rápida que la multiplicación de módulo habitual [1] , por lo que el algoritmo de exponenciación de Montgomery dará un ganancia de rendimiento en comparación con el algoritmo "cuadrar y multiplicar " . $norte'$ ${\ barra {a}}$ ${\ barra {x}}$ $MonPro({\bar {x)),1)$

Implementación del algoritmo en JavaScript

powMod(a, e, m) { var r = 1; mientras (e > 0) { consola.log('A='+a+', E='+e+', R='+r); si ((e & 1) == 0) { mi = mi >> 1; a = (a * a) % m; } más { e = e - 1; r = (r * a) % m; } } consola.log('A='+a+', E='+e+', R='+r); devolver r; }

Notas

↑ Análisis y comparación de algoritmos de multiplicación de Montgomery Archivado el 1 de julio de 2010.

Literatura

Análisis y comparación de algoritmos de multiplicación de Montgomery
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Capítulo 14. Implementación eficiente // Manual de criptografía aplicada (inglés) - CRC Press , 1996. - 816 p. - ( Matemáticas discretas y sus aplicaciones ) - ISBN 978-0-8493-8523-0