Multiplicación modular de Montgomery

En el cálculo aritmético modular , la multiplicación modular de Montgomery , más comúnmente conocida como multiplicación de Montgomery , es un método para realizar una multiplicación modular rápida. Fue introducido en 1985 por el matemático estadounidense Peter L. Montgomery . ^[1]^[2]

La multiplicación modular de Montgomery se basa en una representación especial de números llamada forma de Montgomery. El algoritmo utiliza las formas Montgomery de $una$ y $b$ para calcular de manera eficiente la forma Montgomery de $ab mod N$ . La eficiencia proviene de evitar costosas operaciones de división. La multiplicación modular clásica reduce el producto de doble ancho $ab$ usando la división por $N$ y manteniendo solo el resto. Esta división requiere estimación y corrección de dígitos del cociente. La forma de Montgomery, por el contrario, depende de una constante $R> N$ que es coprima de $N$ , y la única división necesaria en la multiplicación de Montgomery es la división por $R$ . La constante $R$ se puede elegir para que la división por $R$ sea fácil, mejorando significativamente la velocidad del algoritmo. En la práctica, $R$ es siempre una potencia de dos, ya que la división entre potencias de dos se puede implementar mediante desplazamiento de bits.

La necesidad de convertir $un$ y $b$ en forma de Montgomery y su producto de medios de formulario Montgomery que el cálculo de un solo producto por Montgomery multiplicación es más lento que los convencionales o de reducción de Barrett algoritmos. Sin embargo, cuando se realizan muchas multiplicaciones seguidas, como en la exponenciación modular , los resultados intermedios se pueden dejar en forma de Montgomery. Entonces, las conversiones inicial y final se convierten en una fracción insignificante del cálculo general. Muchos criptosistemas importantes, como RSA y el intercambio de claves Diffie-Hellman, se basan en operaciones aritméticas módulo un gran número impar, y para estos criptosistemas, cálculos que utilizan la multiplicación de Montgomery con $R$ una potencia de dos son más rápidas que las alternativas disponibles. ^[3]

Aritmética modular

Sea $N$ un módulo entero positivo. El anillo cociente $Z / N Z$ consta de clases de residuos módulo $N$ , es decir, sus elementos son conjuntos de la forma

{\ Displaystyle \ {a + kN \ dos puntos k \ in \ mathbf {Z} \},}

donde $a$ varía entre los números enteros. Cada clase de residuo es un conjunto de enteros de modo que la diferencia de dos enteros cualesquiera del conjunto es divisible por $N$ (y la clase de residuo es máxima con respecto a esa propiedad; los enteros no se dejan fuera de la clase de residuo a menos que violen la condición de divisibilidad). La clase de residuo correspondiente a $a$ se denota $a$ . La igualdad de clases de residuos se llama congruencia y se denota

{\ Displaystyle {\ bar {a}} \ equiv {\ bar {b}} {\ pmod {N}}.}

Es imposible almacenar una clase de residuo completa en una computadora porque la clase de residuo tiene infinitos elementos. En cambio, las clases de residuos se almacenan como representantes. Convencionalmente, estos representantes son los números enteros $a$ para los cuales $0 \leq a \leq N - 1$ . Si $un$ es un entero, entonces el representante de $una$ se escribe $un mod N$ . Al escribir congruencias, es común identificar un número entero con la clase de residuo que representa. Con esta convención, la igualdad anterior se escribe $un \equiv b mod N$ .

La aritmética de las clases de residuos se realiza realizando primero aritmética de enteros en sus representantes. La salida de la operación entera determina una clase de residuo, y la salida de la operación modular se determina calculando el representante de la clase de residuo. Por ejemplo, si $N = 17$ , entonces la suma de las clases de residuos $7$ y $15$ se calcula encontrando la suma entera $7 + 15 = 22$ , luego determinando $22 mod 17$ , el entero entre 0 y 16 cuya diferencia con 22 es un múltiplo de 17. En este caso, ese número entero es 5, por lo que $7 + 15 \equiv 5 mod 17$ .

Forma de Montgomery

Si $un$ y $b$ son números enteros en el intervalo $[0, N - 1]$ , entonces su suma está en el intervalo $[0, 2 N - 2]$ y su diferencia está en el intervalo $[- N + 1, N - 1]$ , así la determinación de la representación en $[0, N - 1]$ requiere como máximo una sustracción o adición (respectivamente) de $N$ . Sin embargo, el producto $ab$ está en el intervalo $[0, N 2 - 2 N + 1]$ . Almacenamiento del producto entero intermedio $ab$ requiere el doble de bits que $a$ o $b$ , y la determinación eficiente del representante en $[0, N - 1]$ requiere división. Matemáticamente, el número entero entre 0 y $N - 1$ que es congruente con $ab$ se puede expresar aplicando el teorema de la división euclidiana :

{\ Displaystyle ab = qN + r,}

donde $q$ es el cociente y $r$ , el resto, está en el intervalo $[0,$ $N$ $- 1]$ . El resto $R$ es $ab$ $mod$ $N$ . La determinación de $r$ se puede hacer calculando $q$ , luego restando $qN$ de $ab$ . Por ejemplo, el producto $7$ $\cdot$ $15$ se determina calculando , dividiendo y restando . ${\ Displaystyle \ lfloor ab / N \ rfloor}$ $7\cdot 15=105$ $\lfloor 105/17\rfloor =6$ $105-6\cdot 17=105-102=3$

Dado que el cálculo de $q$ requiere división, resulta indeseablemente caro en la mayoría de los equipos informáticos. La forma de Montgomery es una forma diferente de expresar los elementos del anillo en el que se pueden calcular productos modulares sin costosas divisiones. Si bien las divisiones siguen siendo necesarias, se pueden hacer con respecto a un divisor $R$ diferente . Este divisor se puede elegir para que sea una potencia de dos, para lo cual la división se puede reemplazar por desplazamiento, o un número entero de palabras de máquina, para lo cual la división se puede reemplazar omitiendo palabras. Estas divisiones son rápidas, por lo que la mayor parte del costo de computar productos modulares usando la forma de Montgomery es el costo de computar productos ordinarios.

El módulo auxiliar $R$ debe ser un número entero positivo tal que $mcd (R, N) = 1$ . Para fines de cálculo, también es necesario que la división y la reducción de módulo $R$ sean de bajo costo, y el módulo no es útil para la multiplicación modular a menos que $R > N$ . La forma de Montgomery de la clase de residuo $a$ con respecto a $R$ es $aR mod N$ , es decir, es la representativa de la clase de residuo $aR$ . Por ejemplo, suponga que $N = 17$ y que $R = 100$ . Las formas de Montgomery de 3, 5, 7 y 15 son $300 mod 17 = 11$ , $500 mod 17 = 7$ , $700 mod 17 = 3$ y $1500 mod 17 = 4$ .

La suma y la resta en forma de Montgomery son lo mismo que la suma y la resta modular ordinaria debido a la ley distributiva:

aR+bR=(a+b)R,

aR-bR=(a-b)R.

Esto es una consecuencia del hecho de que, debido a $gcd (R, N) = 1$ , la multiplicación por $R$ es un isomorfismo en el grupo aditivo $Z / N Z$ . Por ejemplo, $(7 + 15) mod 17 = 5$ , que en la forma de Montgomery se convierte en $(3 + 4) mod 17 = 7$ .

Sin embargo, la multiplicación en forma de Montgomery es aparentemente más complicada. El producto habitual de $aR$ y $bR$ no representa el producto de $una$ y $b$ , ya que tiene un factor adicional de $R$ :

(aR{\bmod {N}})(bR{\bmod {N}}){\bmod {N}}=(abR)R{\bmod {N}}.

El cálculo de los productos en forma de Montgomery requiere eliminar el factor adicional de $R$ . Si bien la división por $R$ es barata, el producto intermedio $(aR mod N) (bR mod N)$ no es divisible por $R$ porque la operación de módulo ha destruido esa propiedad. Así, por ejemplo, el producto de las formas Montgomery de 7 y 15 de módulo 17 es el producto de 3 y 4, que es 12. Puesto que 12 no es divisible por 100, se requiere un esfuerzo adicional para eliminar el factor adicional de $R$ .

Extracción del factor de extra de $R$ se puede hacer mediante la multiplicación por un número entero $R'$ tal que $RR' \equiv 1 (mod N)$ , es decir, por un $R'$ cuya clase residuo es el inverso modular de $R$ mod $N$ . Luego, trabajando módulo $N$ ,

(aR{\bmod {N}})(bR{\bmod {N}})R'\equiv (aR)(bR)R^{-1}\equiv (ab)R{\pmod {N}}.

El número entero $R'$ existe debido a la suposición de que $R$ y $N$ son coprimos. Puede construirse utilizando el algoritmo euclidiano extendido . El algoritmo euclidiano extendido determina eficientemente los números enteros $R'$ y $N'$ que satisfacen la identidad de Bézout : $0 < R' < N$ , $0 < N' < R$ , y:

RR'-NN'=1.

Esto muestra que es posible hacer la multiplicación en forma de Montgomery. Por tanto, un algoritmo sencillo a los números se multiplican en forma Montgomery es multiplicar $aR mod N$ , $bR mod N$ , y $R'$ como enteros y reducir modulo $N$ .

Por ejemplo, para multiplicar 7 y 15 módulo 17 en forma de Montgomery, nuevamente con $R = 100$ , calcule el producto de 3 y 4 para obtener 12 como se indicó anteriormente. El algoritmo euclidiano extendido implica que $8\cdot100 - 47\cdot17 = 1$ , entonces $R' = 8$ . Multiplica 12 por 8 para obtener 96 y reduce módulo 17 para obtener 11. Esta es la forma de Montgomery de 3, como se esperaba.

El algoritmo REDC

Mientras que el algoritmo anterior es correcta, es más lento que la multiplicación en la representación estándar debido a la necesidad de multiplicar por $R'$ y dividir por $N$ . La reducción de Montgomery , también conocida como REDC, es un algoritmo que calcula simultáneamente el producto por $R'$ y reduce el módulo $N$ más rápidamente que el método ingenuo. A diferencia de la reducción modular convencional, que se centra en hacer que el número menor que $N$ , la reducción de Montgomery se centra en hacer el número más divisible por $R$ . Lo hace agregando un pequeño múltiplo de $N$ que se elige para cancelar el residuo módulo $R$ . Dividir el resultado por $R$ produce un número mucho menor. Este número es mucho más pequeño que es casi el módulo de reducción $N$ , y calcular el módulo de reducción $N$ requiere sólo una resta condicional final. Debido a que todos los cálculos se realizan utilizando solo la reducción y las divisiones con respecto a $R$ , no a $N$ , el algoritmo se ejecuta más rápido que una simple reducción modular por división.

función REDC es  de entrada: Los enteros R y N con gcd ( R , N ) = 1 , Entero N ′ en [0, R - 1] tal que NN ′ ≡ −1 mod R , Entero T en el rango [0, RN - 1] . salida: Entero S en el rango [0, N - 1] tal que S ≡ TR ⁻¹ mod N m ← (( T mod R ) N ′) mod R  t ← ( T + mN ) / R  si  t ≥ N  entonces  retorna  t - N de lo  contrario  retorna  t  end if end función

Para ver que este algoritmo es correcto, primero observar que $m$ se elige precisamente de modo que $T + mN$ es divisible por $R$ . Un número es divisible por $R$ si y solo si es congruente con cero mod $R$ , y tenemos:

T+mN\equiv T+(((T{\bmod {R}})N'){\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}.

Por tanto, $t$ es un número entero. En segundo lugar, la salida es $t$ o $t - N$ , los cuales son congruentes con $t mod N$ , de modo que para demostrar que la salida es congruente con $TR -1 mod N$ , basta con demostrar que $t lo$ es. Modulo $N$ , $t$ satisface:

t\equiv (T+mN)R^{-1}\equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}}.

Por lo tanto, la salida tiene la clase de residuo correcta. En tercer lugar, $m$ está en $[0, R - 1]$ y, por lo tanto, $T + mN$ está entre 0 y $(RN - 1) + (R - 1) N <2 RN$ . Por tanto, $t$ es menor que $2 N$ , y como es un número entero, esto pone $t$ en el rango $[0, 2 N - 1]$ . Por lo tanto, reducir $t$ al rango deseado requiere como máximo una única resta, por lo que la salida del algoritmo se encuentra en el rango correcto.

Para usar REDC para calcular el producto de 7 y 15 módulo 17, primero conviértalo a la forma de Montgomery y multiplique como números enteros para obtener 12 como se indicó anteriormente. Luego aplique REDC con $R = 100$ , $N = 17$ , $N' = 47$ y $T = 12$ . El primer paso establece $m$ en $12 \cdot 47 mod 100 = 64$ . El segundo paso establece $t$ en $(12 + 64 \cdot 17) / 100$ . Observe que $12 + 64 \cdot 17$ es 1100, un múltiplo de 100 como se esperaba. $t$ se establece en 11, que es menor que 17, por lo que el resultado final es 11, que concuerda con el cálculo de la sección anterior.

Como otro ejemplo, considere el producto $7 \cdot 15 mod 17$ pero con $R = 10$ . Usando el algoritmo euclidiano extendido, calcule $-5 \cdot 10 + 3 \cdot 17 = 1$ , entonces $N'$ será $-3 mod 10 = 7$ . Las formas de Montgomery de 7 y 15 son $70 mod 17 = 2$ y $150 mod 17 = 14$ , respectivamente. Su producto 28 es la entrada $T$ para REDC, y dado que $28 < RN = 170$ , se satisfacen los supuestos de REDC. Para ejecutar REDC, establezca $m$ en $(28 mod 10) \cdot 7 mod 10 = 196 mod 10 = 6$ . Entonces $28 + 6 \cdot 17 = 130$ , entonces $t = 13$ . Como $30 mod 17 = 13$ , esta es la forma de Montgomery de $3 = 7 \cdot 15 mod 17$ .

Aritmética en forma de Montgomery

Muchas operaciones de interés módulo $N$ se pueden expresar igualmente bien en forma de Montgomery. La suma, la resta, la negación, la comparación por igualdad, la multiplicación por un número entero que no está en la forma de Montgomery y los máximos divisores comunes con $N$ pueden realizarse con los algoritmos estándar. El símbolo de Jacobi se puede calcular siempre que esté almacenado. ${\big (}{\tfrac {a}{N}}{\big )}={\big (}{\tfrac {aR}{N}}{\big )}/{\big (}{\tfrac {R}{N}}{\big )}$ ${\big (}{\tfrac {R}{N}}{\big )}$

Cuando $R > N$ , la mayoría de las demás operaciones aritméticas se pueden expresar en términos de REDC. Este supuesto implica que el producto de dos representantes mod $N$ es menor que $RN$ , la hipótesis exacta necesaria para que REDC genere una salida correcta. En particular, el producto de $aR mod N$ y $bR mod N$ es $REDC ((aR mod N) (bR mod N))$ . La operación combinada de multiplicación y REDC a menudo se denomina multiplicación de Montgomery .

La conversión a la forma de Montgomery se realiza calculando $REDC ((a mod N) (R 2 mod N))$ . La conversión fuera de la forma de Montgomery se realiza calculando $REDC (aR mod N)$ . El inverso modular de $aR mod N$ es $REDC ((aR mod N) -1 (R 3 mod N))$ . La exponenciación modular se puede hacer usando exponenciación elevando al cuadrado inicializando el producto inicial a la representación de Montgomery de 1, es decir, a $R mod N$ , y reemplazando los pasos de multiplicar y cuadrar por multiplicaciones de Montgomery.

La realización de estas operaciones requiere el conocimiento de al menos $N'$ y $R 2 mod N$ . Cuando $R$ es una potencia de un pequeño entero positivo $b$ , $N'$ puede calcularse mediante el lema de Hensel : el inverso de $N$ módulo $b$ se calcula mediante un algoritmo ingenuo (por ejemplo, si $b = 2,$ entonces el inverso es 1), y el de Hensel lemma se usa repetidamente para encontrar el módulo inverso mayor y mayores potencias de $b$ , deteniéndose cuando se conoce el módulo inverso $R$ ; $N'$ es la negación de esta inversa. Las constantes $R mod N$ y $R 3 mod N$ se pueden generar como $REDC (R 2 mod N)$ y como $REDC ((R 2 mod N) (R 2 mod N))$ . La operación fundamental es calcular la REDC de un producto. Cuando se necesita REDC independiente, que puede calcularse como REDC de un producto con $1 mod N$ . El único lugar donde es necesario un módulo de reducción directa $N$ es en el cálculo previo de $R 2 mod N$ .

Aritmética de Montgomery en números enteros de multiprecisión

La mayoría de las aplicaciones criptográficas requieren números de cientos o incluso miles de bits. Estos números son demasiado grandes para almacenarlos en una sola palabra de máquina. Por lo general, el hardware realiza la multiplicación en cierta base $B$ , por lo que realizar multiplicaciones más grandes requiere combinar varias multiplicaciones pequeñas. La base $B$ es típicamente 2 para aplicaciones microelectrónicas, 2 ⁸ para firmware de 8 bits, ^[4] o 2 ³² o 2 ⁶⁴ para aplicaciones de software.

El algoritmo REDC requiere productos módulo $R$ , y típicamente $R > N$ para que REDC pueda usarse para calcular productos. Sin embargo, cuando $R$ es una potencia de $B$ , hay una variante de REDC que requiere productos solo de números enteros del tamaño de una palabra de máquina. Suponga que los enteros positivos de precisión múltiple se almacenan little endian , es decir, $x$ se almacena como una matriz $x [0], ..., x [ℓ - 1]$ tal que $0 \leq x [i] < B$ para todo $i$ y $x = \sum x [i] B i$ . El algoritmo comienza con un número entero de precisión múltiple $T$ y lo reduce una palabra a la vez. En primer lugar un múltiplo adecuado de $N$ se añade para hacer $T$ divisible por $B$ . Luego se suma un múltiplo de $N$ para hacer que $T sea$ divisible por $B 2$ , y así sucesivamente. Finalmente, $T$ es divisible por $R$ , y después de la división por $R,$ el algoritmo está en el mismo lugar que REDC después del cálculo de $t$ .

La función MultiPrecisionREDC es  Entrada: Entero N con gcd ( B , N ) = 1 , almacenado como una matriz de p palabras, Entero R = B ^r , --esto, r = log _B  R Entero N ′ en [0, B - 1] tal que NN ′ ≡ −1 (mod B ) , Entero T en el rango 0 ≤ T < RN , almacenado como una matriz de r + p palabras. Salida: Entero S en [0, N - 1] tal que TR ⁻¹ ≡ S (mod N ) , almacenado como una matriz de p palabras. Establezca T [ r + p ] = 0  (palabra de transporte adicional)  para  0 ≤ i < r  do  --loop1- Haga que T sea divisible por B ^{i + 1} c ← 0 m ← T [ i ] ⋅ N ′ mod B  para  0 ≤ j < p  do  --loop2- Agrega la palabra baja de m ⋅ N [j] y el acarreo de antes, y encuentra el nuevo acarreo x ← T [ i + j ] + m ⋅ N [ j ] + c  T [ i + j ] ← x mod B  c ← ⌊ x / B ⌋  fin para  para  p ≤ j ≤ r + p - yo  hago -  bucle3 - Continuar llevando x ← T [ i + j ] + c  T [ i + j ] ← x mod B  c ← ⌊ x / B ⌋  fin para  fin para para  0 ≤ i < p  hacer  S [ i ] ← T [ i + r ] final para si  S ≥ N  entonces  regresa  S - N de lo  contrario  regresa  S  end si finaliza la función

La comparación y resta final se realiza mediante los algoritmos estándar.

El algoritmo anterior es correcto esencialmente por las mismas razones por las que REDC es correcto. Cada vez que a través de la $i$ de bucle, $m$ se elige de manera que $T [i] + mN [0]$ es divisible por $B$ . Entonces $MNB i$ se añade a $T$ . Debido a que esta cantidad es cero mod $N$ , añadiendo que no afecta el valor de $T mod N$ . Si $m i$ denota el valor de $m$ calculado en la $i-$ ésima iteración del ciclo, entonces el algoritmo establece $S$ en $T + (\sum m i b i) N$ . Debido a que MultiPrecisionREDC y REDC producen el mismo resultado, esta suma es la misma que la elección de $m$ que haría el algoritmo REDC.

La última palabra de $T$ , $T [r + p]$ (y consecuentemente $S [p]$ ), se usa solo para mantener un acarreo, ya que el resultado de reducción inicial está ligado a un resultado en el rango de $0 \leq S < 2N$ . De ello se deduce que esta palabra de acarreo adicional se puede evitar por completo si se sabe de antemano que $R \geq 2N$ . En una implementación binaria típica, esto equivale a decir que esta palabra de acarreo se puede evitar si el número de bits de $N$ es menor que el número de bits de $R$ . De lo contrario, el acarreo será cero o uno. Dependiendo del procesador, es posible almacenar esta palabra como una bandera de acarreo en lugar de una palabra de tamaño completo.

Es posible combinar la multiplicación de precisión múltiple y REDC en un solo algoritmo. Este algoritmo combinado generalmente se llama multiplicación de Montgomery. Koç, Acar y Kaliski describen varias implementaciones diferentes. ^[5] El algoritmo puede usar tan solo $p + 2$ palabras de almacenamiento (más un bit de acarreo).

Como ejemplo, sea $B = 10$ , $N = 997$ y $R = 1000$ . Suponga que $a = 314$ y $b = 271$ . Las representaciones Montgomery de $un$ y $b$ son $314000 mod 997 = 942$ y $271 000 mod 997 = 813$ . Calcule $942 \cdot 813 = 765846$ . La entrada inicial $T$ para MultiPrecisionREDC será [6, 4, 8, 5, 6, 7]. El número $N$ se representará como [7, 9, 9]. El algoritmo euclidiano extendido dice que $-299 \cdot 10 + 3 \cdot 997 = 1$ , entonces $N'$ será 7.

yo ← 0
m ← 6 ⋅ 7 mod 10 = 2j T c
- ------- -
0 0485670 2 (Después de la primera iteración del primer bucle)1 0485670 2
2 0485670 2
3 0487670 0 (después de la primera iteración del segundo bucle)4 0487670 0
5 0487670 0
6 0487670 0
yo ← 1
m ← 4 ⋅ 7 mod 10 = 8j T c
- ------- -
0 0087670 6 (Después de la primera iteración del primer bucle)1 0067670 8
2 0067670 8
3 0067470 1 (Después de la primera iteración del segundo bucle)4 0067480 0
5 0067480 0
yo ← 2
m ← 6 ⋅ 7 mod 10 = 2j T c
- ------- -
0 0007480 2 (después de la primera iteración del primer bucle)1 0007480 2
2 0007480 2
3 0007400 1 (después de la primera iteración del segundo bucle)4 0007401 0

Por lo tanto, antes de la comparación y resta final, $S = 1047$ . La resta final produce el número 50. Dado que la representación de Montgomery de $314 \cdot 271 mod 997 = 349$ es $349000 mod 997 = 50$ , este es el resultado esperado.

Cuando se trabaja en base 2, determinar el $m$ correcto en cada etapa es particularmente fácil: si el bit de trabajo actual es par, entonces $m$ es cero y si es impar, entonces $m$ es uno. Además, debido a que cada paso de MultiPrecisionREDC requiere conocer solo el bit más bajo, la multiplicación de Montgomery se puede combinar fácilmente con un sumador de acarreo y ahorro .

Ataques de canal lateral

Debido a que la reducción de Montgomery evita los pasos de corrección requeridos en la división convencional cuando las estimaciones de los dígitos del cociente son inexactas, en su mayoría está libre de las ramas condicionales que son los objetivos principales de los ataques de canal lateral de potencia y sincronización ; la secuencia de instrucciones ejecutadas es independiente de los valores del operando de entrada. La única excepción es la resta condicional final del módulo, pero se modifica fácilmente (para restar siempre algo, ya sea el módulo o cero) para hacerlo resistente. ^[4] Por supuesto, es necesario asegurarse de que el algoritmo de exponenciación construido alrededor de la primitiva de multiplicación también sea resistente. ^[4]^[6]

Ver también

Reducción de Barrett

Referencias

^ Montgomery, Peter (abril de 1985). "Multiplicación modular sin división de prueba" (PDF) . Matemáticas de la Computación . 44 (170): 519–521. doi : 10.1090 / S0025-5718-1985-0777282-X .
^ Martin Kochanski, "Multiplicación de Montgomery" Archivado el 27 de marzo de 2010 en la Wayback Machine, una explicación coloquial.
^ Alfred J. Menezes , Paul C. van Oorschot y Scott A. Vanstone . Manual de criptografía aplicada . CRC Press, 1996. ISBN 0-8493-8523-7 , capítulo 14.
^ a b c Liu, Zhe; Großschädl, Johann; Kizhvatov, Ilya (29 de noviembre de 2010). Implementación de RSA eficiente y resistente al canal lateral para microcontroladores AVR de 8 bits (PDF) . 1er Taller Internacional sobre Seguridad en Internet de las Cosas . Tokio. ( Diapositivas de presentación .)
^ Çetin K. Koç; Tolga Acar; Burton S. Kaliski, Jr. (junio de 1996). "Análisis y comparación de algoritmos de multiplicación de Montgomery" (PDF) . IEEE Micro . 16 (3): 26–33. CiteSeerX 10.1.1.26.3120 . doi : 10.1109 / 40.502403 .
^ Marc Joye y Sung-Ming Yen. "La escalera de potencia Montgomery" . 2002.

enlaces externos

Henry S. Warren, Jr. (julio de 2012). "Teoría y práctica de la multiplicación de Montgomery" (PDF) .

[montg1985-1] Montgomery, Peter (abril de 1985). "Multiplicación modular sin división de prueba" (PDF) . Matemáticas de la Computación . 44 (170): 519–521. doi : 10.1090 / S0025-5718-1985-0777282-X .

[kochanski-2] Martin Kochanski, "Multiplicación de Montgomery" Archivado el 27 de marzo de 2010 en la Wayback Machine, una explicación coloquial.

[3] Alfred J. Menezes , Paul C. van Oorschot y Scott A. Vanstone . Manual de criptografía aplicada . CRC Press, 1996. ISBN 0-8493-8523-7 , capítulo 14.

[kizhvatov-4] Liu, Zhe; Großschädl, Johann; Kizhvatov, Ilya (29 de noviembre de 2010). Implementación de RSA eficiente y resistente al canal lateral para microcontroladores AVR de 8 bits (PDF) . 1er Taller Internacional sobre Seguridad en Internet de las Cosas . Tokio. ( Diapositivas de presentación .)

[5] Çetin K. Koç; Tolga Acar; Burton S. Kaliski, Jr. (junio de 1996). "Análisis y comparación de algoritmos de multiplicación de Montgomery" (PDF) . IEEE Micro . 16 (3): 26–33. CiteSeerX 10.1.1.26.3120 . doi : 10.1109 / 40.502403 .

[6] Marc Joye y Sung-Ming Yen. "La escalera de potencia Montgomery" . 2002.

[1]