multiplicación modular de Montgomery

En aritmética modular , la multiplicación modular de Montgomery , más conocida como multiplicación de Montgomery , es un método para realizar multiplicaciones modulares rápidas. Fue introducida 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 los números llamada forma de Montgomery. El algoritmo utiliza las formas de Montgomery de a y b para calcular eficientemente la forma de 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 conservando solo el resto. Esta división requiere estimación y corrección de dígitos del cociente. La forma de Montgomery, en cambio, depende de una constante R > N que es coprima con 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 de manera que la división por R sea fácil, mejorando significativamente la velocidad del algoritmo. En las computadoras binarias, R siempre es una potencia de dos , ya que la división por potencias de dos se puede implementar mediante desplazamiento de bits .

La necesidad de convertir a y b a la forma de Montgomery y su producto fuera de la forma de Montgomery implica que calcular un solo producto mediante la multiplicación de Montgomery es más lento que los algoritmos convencionales o de reducción de Barrett . Sin embargo, al realizar muchas multiplicaciones seguidas, como en la exponenciación modular , los resultados intermedios pueden dejarse en la forma de Montgomery. Entonces, las conversiones inicial y final se convierten en una fracción insignificante del cálculo total. Muchos criptosistemas importantes, como RSA y el intercambio de claves Diffie-Hellman, se basan en operaciones aritméticas módulo un número impar grande, y para estos criptosistemas, los cálculos que utilizan la multiplicación de Montgomery con R una potencia de dos son más rápidos que las alternativas disponibles. ^{[ 3 ]}

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 abarca los enteros. Cada clase de residuo es un conjunto de enteros tal que la diferencia de cualesquiera dos enteros en el conjunto es divisible por N (y la clase de residuo es máxima con respecto a esa propiedad; los enteros no se excluyen 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 residuo se llama congruencia y se denota

${\displaystyle {\bar {a}}\equiv {\bar {b}}{\pmod {N}}.}$

Almacenar una clase de residuo completa en una computadora es imposible porque la clase de residuo tiene infinitos elementos. En cambio, las clases de residuo se almacenan como representantes. Por convención, estos representantes son los enteros a para los cuales 0 ≤ a ≤ N − 1 . Si a es un entero, entonces el representante de a se escribe a mod N . Al escribir congruencias, es común identificar un entero con la clase de residuo que representa. Con esta convención, la igualdad anterior se escribe a ≡ b mod N .

La aritmética sobre clases de residuos se realiza aplicando primero operaciones aritméticas enteras a sus representantes. El resultado de la operación entera determina una clase de residuo, y el resultado de la operación modular se determina calculando el representante de la clase de residuo. Por ejemplo, si N = 17 , la suma de las clases de residuos 7 y 15 se calcula hallando la suma entera 7 + 15 = 22 , y 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 entero es 5, por lo que 7 + 15 ≡ 5 mod 17 .

Si a y b son enteros en el intervalo [0, N − 1] , entonces su suma está en el intervalo [0, 2N − 2] y su diferencia está en el intervalo [−N + 1, N − 1] , por lo que determinar el representante en [0, N − 1] requiere como máximo una resta o una suma (respectivamente) de N. Sin embargo, el producto ab está en el intervalo [0, N² − 2N + 1] . Almacenar el producto entero intermedio ab requiere el doble de bits que a o ^b , y determinar eficientemente el representante en [0, N − 1] requiere una división. Matemáticamente, el 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. r se puede determinar calculando q y luego restando qN de ab . Por ejemplo, nuevamente con , el producto 7 ⋅ 15 se determina calculando , dividiendo y restando . ${\displaystyle \lfloor ab/N\rfloor }$${\displaystyle N=17}$${\displaystyle 7\cdot 15=105}$${\displaystyle \lfloor 105/17\rfloor =6}$${\displaystyle 105-6\cdot 17=105-102=3}$

Debido a que el cálculo de q requiere división, resulta excesivamente costoso en la mayoría de los equipos informáticos . La notación de Montgomery es una forma diferente de expresar los elementos del anillo en la que los productos modulares pueden calcularse sin divisiones costosas. Si bien las divisiones siguen siendo necesarias, pueden realizarse con respecto a un divisor diferente R. Este divisor puede elegirse como una potencia de dos, para la cual la división puede reemplazarse por un desplazamiento, o como un número entero de palabras de máquina, para el cual la división puede reemplazarse por la omisión de palabras. Estas divisiones son rápidas, por lo que la mayor parte del costo de calcular productos modulares usando la notación de Montgomery es el costo de calcular productos ordinarios.

El módulo auxiliar R debe ser un entero positivo tal que mcd( R , N ) = 1 . Para fines computacionales también es necesario que la división y la reducción módulo R sean económicas, 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 el representante de la clase de residuo aR . Por ejemplo, supongamos 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 iguales a la suma y la resta modular ordinarias debido a la ley distributiva:

${\displaystyle aR+bR=(a+b)R,}$

${\displaystyle aR-bR=(ab)R.}$

Nótese que realizar la operación en forma de Montgomery no pierde información en comparación con realizarla en el anillo cociente Z / N Z . Esto es consecuencia del hecho de que, dado que mcd( 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 forma de Montgomery se convierte en (3 + 4) mod 17 = 7 .

Sin embargo, la multiplicación en forma de Montgomery parece más complicada. El producto habitual de aR y bR no representa el producto de a y b porque tiene un factor adicional de R :

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

El cálculo de productos en forma de Montgomery requiere eliminar el factor adicional de R. Si bien la división por R es sencilla, 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. Por ejemplo, el producto de las formas de Montgomery de 7 y 15 módulo 17, con R = 100 , es el producto de 3 y 4, que es 12. Como 12 no es divisible por 100, se requiere un esfuerzo adicional para eliminar el factor adicional de R.

Eliminar el factor extra de R se puede hacer multiplicando por un entero R ′ tal que RR ′ ≡ 1 (mod N ) , es decir, por un R ′ cuya clase de residuo es el inverso modular de R mod N . Luego, trabajando módulo N ,

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

El entero R ′ existe debido a la suposición de que R y N son coprimos. Se puede construir utilizando el algoritmo euclidiano extendido . El algoritmo euclidiano extendido determina eficientemente los enteros R ′ y N ′ que satisfacen la identidad de Bézout : 0 < R ′ < N , 0 < N ′ < R , y:

${\displaystyle RR'-NN'=1.}$

Esto demuestra que es posible realizar multiplicaciones en forma de Montgomery. Por lo tanto, un algoritmo sencillo para multiplicar números en forma de Montgomery consiste en multiplicar aR mod N , bR mod N y R ′ como enteros y reducir módulo N.

Por ejemplo, para multiplicar 7 y 15 módulo 17 en forma de Montgomery, nuevamente con R = 100 , calculamos el producto de 3 y 4 para obtener 12 como se indicó anteriormente. El algoritmo euclidiano extendido implica que 8⋅100 − 47⋅17 = 1 , por lo que R ′ = 8. Multiplicamos 12 por 8 para obtener 96 y reducimos módulo 17 para obtener 11. Esta es la forma de Montgomery de 3, como se esperaba.

Si bien el algoritmo anterior es correcto, 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 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 sea menor que N , la reducción de Montgomery se centra en hacer que el número sea más divisible por R. Esto se logra sumando un pequeño múltiplo de N elegido sofisticadamente para cancelar el residuo módulo R. Al dividir el resultado por R se obtiene un número mucho menor. Este número es tan pequeño que es casi la reducción módulo N , y calcular la reducción módulo N solo requiere una resta condicional final. Dado que todos los cálculos se realizan utilizando únicamente reducción y división con respecto a R , no a N , el algoritmo se ejecuta más rápido que una reducción modular directa por división.

La función REDC es la entrada: Enteros R y N con mcd( 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 −1 mod Nm ← (( T mod R ) N ′) mod R t ← ( T + mN ) / R si t ≥ N entonces devolver t − N sino devolver t fin si fin función

Para comprobar que este algoritmo es correcto, observemos primero que m se elige precisamente de manera que T + mN sea divisible por R. Un número es divisible por R si y solo si es congruente con cero módulo R , y tenemos:

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

Por lo tanto, t es un número entero. En segundo lugar, la salida es t o t − N , ambas congruentes con t mod N , así que para demostrar que la salida es congruente con TR ⁻¹ mod N , basta con demostrar que t es TR ⁻¹ mod N , t satisface:

${\displaystyle 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 lo tanto, t es menor que 2 N , y como es un entero, esto coloca a t en el rango [0, 2 N − 1] . Por lo tanto, reducir t al rango deseado requiere como máximo una sola 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 Montgomery y multiplíquelo como 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 ⋅ 47 mod 100 = 64. El segundo paso establece t en (12 + 64 ⋅ 17) / 100. Observe que 12 + 64 ⋅ 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 coincide con el cálculo de la sección anterior.

Como otro ejemplo, consideremos el producto 7 ⋅ 15 mod 17 pero con R = 10. Usando el algoritmo euclidiano extendido, calculamos −5 ⋅ 10 + 3 ⋅ 17 = 1 , por lo que 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 como 28 < RN = 170 , se cumplen los supuestos de REDC. Para ejecutar REDC, establecemos m en (28 mod 10) ⋅ 7 mod 10 = 196 mod 10 = 6. Entonces 28 + 6 ⋅ 17 = 130 , por lo que t = 13 . Como 30 mod 17 = 13 , esta es la forma de Montgomery de 3 = 7 ⋅ 15 mod 17 .

Fuente: ^{[ 4 ]}

Dado el módulo N y la base de Montgomery R utilizados en una reducción de Montgomery, considere el anillo residual.

${\displaystyle \mathbb {Z} /(NR)\mathbb {Z} \;\cong \;\mathbb {Z} /N\mathbb {Z} \;\times \;\mathbb {Z} /R\mathbb {Z} ,}$

un isomorfismo que se deduce del Teorema Chino del Resto (TCR) .

Para un entero con (como es típico cuando surge de la multiplicación de dos residuos), tome sus reducciones ${\displaystyle T}$${\displaystyle 0\leq T<NR}$${\displaystyle T}$

${\displaystyle T_{N}=T{\bmod {N}},\qquad T_{R}=T{\bmod {R}}.}$

La CRT proporciona la fórmula de reconstrucción explícita.

${\displaystyle T\equiv T_{N}{\bigl (}R^{-1}{\bmod {N}}{\bigr )}\,R\;+T_{R}{\bigl (}N^{-1}{\bmod {R}}{\bigr )}\,N{\pmod {NR}}.}$

Como el lado derecho ya está tomado módulo , esto también se puede escribir como ${\displaystyle NR}$

${\displaystyle T\equiv {\bigl (}T_{N}R^{-1}{\bmod {N}}{\bigr )}R\;+{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N{\pmod {NR}}.}$

Ambos sumandos se encuentran en el intervalo semiabierto : ${\displaystyle [0,NR)}$

${\displaystyle 0\leq {\bigl (}T_{N}R^{-1}{\bmod {N}}{\bigr )}R<NR,\qquad 0\leq {\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N<NR.}$

Por lo tanto, como ecuaciones enteras (no meramente congruencias) tenemos

${\displaystyle T={\bigl (}T_{N}R^{-1}{\bmod {N}}{\bigr )}R\;+{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N,}$

o,

${\displaystyle T+NR={\bigl (}T_{N}R^{-1}{\bmod {N}}{\bigr )}R\;+{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N.}$

Para resolverlo , aísle el primer sumando: ${\displaystyle T_{N}}$

${\displaystyle {\bigl (}T_{N}R^{-1}{\bmod {N}}{\bigr )}R={\begin{cases}T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N,\\T+NR-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N.\end{cases}}}$

Cada cantidad anterior es un número entero, y el lado izquierdo es un múltiplo de ; por lo tanto, cada lado derecho es divisible por . Dividiendo por se obtiene ${\displaystyle R}$${\displaystyle R}$${\displaystyle R}$

${\displaystyle T_{N}R^{-1}{\bmod {N}}={\begin{cases}{\dfrac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}},\\[8pt]{\dfrac {T+NR-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}\,=\,{\dfrac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}+N.\end{cases}}}$

Como consecuencia,

${\displaystyle {\dfrac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}={\begin{cases}T_{N}R^{-1}{\bmod {N}},\\T_{N}R^{-1}{\bmod {N}}\;-\;N.\end{cases}}}$

Esto nos da dos datos clave:

• Congruencia

${\displaystyle {\frac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}\;\equiv \;T_{N}R^{-1}{\pmod {N}}.}$

• Límite numérico

${\displaystyle -N\;\leq \;{\frac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}\;<\;N.}$

Por lo tanto, al reducir

${\displaystyle {\frac {T-{\bigl (}T_{R}N^{-1}{\bmod {R}}{\bigr )}N}{R}}}$

Una vez más, módulo N , se obtiene el residuo no negativo que representa . ${\displaystyle T_{N}R^{-1}{\bmod {N}}}$

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

Cuando R > N , la mayoría de las demás operaciones aritméticas pueden expresarse en términos de REDC. Esta suposición implica que el producto de dos representantes módulo N es menor que RN , la hipótesis exacta necesaria para que REDC genere un resultado correcto. En particular, el producto de aR módulo N y bR módulo N es REDC(( aR módulo N )( bR módulo N )) . La operación combinada de multiplicación y REDC se suele denominar multiplicación de Montgomery .

La conversión a la forma de Montgomery se realiza calculando REDC(( a mod N )( R ² mod N )) . La conversión de la forma de Montgomery se realiza calculando REDC( aR mod N ) . El inverso modular de aR mod N es REDC(( aR mod N ) ⁻¹ ( R ³ mod N )) . La exponenciación modular se puede realizar utilizando la exponenciación por cuadrado , inicializando el producto inicial a la representación de Montgomery de 1, es decir, a R mod N , y reemplazando los pasos de multiplicación y elevación al cuadrado por multiplicaciones de Montgomery.

Realizar estas operaciones requiere conocer al menos N ′ y R ² mod N . Cuando R es una potencia de un entero positivo pequeño b , N ′ se puede calcular 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 lema de Hensel se usa repetidamente para encontrar el inverso módulo potencias cada vez mayores de b , deteniéndose cuando se conoce el inverso módulo R ; N ′ es la negación de este inverso. Las constantes R mod N y R ³ mod N se pueden generar como REDC( R ² mod N ) y como REDC(( R ² mod N )( R ² mod N )) . La operación fundamental es calcular REDC de un producto. Cuando se necesita REDC independiente, se puede calcular como REDC de un producto con 1 mod N . El único lugar donde es necesaria una reducción directa módulo N es en el precálculo de R ² mod 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 almacenarse en una sola palabra de máquina. Normalmente, el hardware realiza la multiplicación módulo alguna base B , por lo que realizar multiplicaciones mayores requiere combinar varias multiplicaciones pequeñas. La base ^B suele ser 2 para aplicaciones microelectrónicas, ^{2⁸ para} firmware de 8 bits ^{[ 5 ]} o 2³² o ^2⁶⁴ para aplicaciones de software.

El algoritmo REDC requiere productos módulo R , y normalmente 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 enteros del tamaño de una palabra de máquina. Supongamos 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 ≤ x [ i ] < B para todo i y x = ∑ x [ i ] B ⁱ . El algoritmo comienza con un entero de precisión múltiple T y lo reduce palabra por palabra. Primero se agrega un múltiplo apropiado de N para que T sea divisible por B . Luego se agrega un múltiplo de N para que T sea divisible por B ² , 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 mcd( B , N ) = 1 , almacenado como una matriz de p palabras, Entero R = B r , --por lo tanto, 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 −1 ≡ S (mod N ) , almacenado como una matriz de p palabras. Establecer T [ r + p ] = 0 (palabra de acarreo adicional) para 0 ≤ i < r hacer --bucle1- Hacer que T sea divisible por B i+1c ← 0 m ← T [ i ] ⋅ N ′ mod B para 0 ≤ j < p hacer --loop2- Sumar m ⋅ N[j] y el acarreo anterior, y encontrar el nuevo acarreox ← T [ i + j ] + m ⋅ N [ j ] + c T [ i + j ] ← x mod B c ← ⌊ x / B ⌋ fin para para p ≤ j ≤ r + p − i hacer --bucle3- Continuar llevandox ← T [ i + j ] + c T [ i + j ] ← x mod B c ← ⌊ x / B ⌋ fin para fin parapara 0 ≤ i ≤ p hacer S [ i ] ← T [ i + r ] fin paraSi S ≥ N, entonces devuelve S − N; de lo contrario, devuelve S. Fin de la función.

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

El algoritmo anterior es correcto esencialmente por las mismas razones que REDC. En cada iteración del bucle i , se elige m de modo que T [ i ] + mN [0] sea divisible por B. Luego, ^se suma mNBi a T. Como esta cantidad es cero módulo N , sumarla no afecta el valor de T módulo N. Si mi denota el valor de _m calculado en la i - ésima iteración del bucle, entonces el algoritmo establece S como T + (∑ mi _Bi ⁾ N . Dado que MultiPrecisionREDC y REDC producen la misma salida, 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, por consiguiente , S [ p ] ), se utiliza únicamente para almacenar un acarreo, ya que el resultado de la reducción inicial está limitado a un resultado en el rango de 0 ≤ S < 2N . De ello se deduce que esta palabra de acarreo adicional puede evitarse por completo si se sabe de antemano que R ≥ 2N . En una implementación binaria típica, esto equivale a decir que esta palabra de acarreo puede evitarse 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, puede ser posible almacenar esta palabra como un indicador 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 único algoritmo. Este algoritmo combinado se suele denominar multiplicación de Montgomery. Koç, Acar y Kaliski describen varias implementaciones diferentes. ^{[ 6 ]} El algoritmo puede utilizar tan solo p + 2 palabras de almacenamiento (más un bit de acarreo).

Como ejemplo, sea B = 10 , N = 997 y R = 1000. Supongamos que a = 314 y b = 271. Las representaciones de Montgomery de a y b son 314000 mod 997 = 942 y 271000 mod 997 = 813. Calculamos 942 ⋅ 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 ⋅ 10 + 3 ⋅ 997 = 1 , por lo que N ′ será 7.

yo ← 0 m ← 6 ⋅ 7 mod 10 = 2 j 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 = 8 j 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 = 2 j 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 da como resultado el número 50. Dado que la representación de Montgomery de 314 ⋅ 271 mod 997 = 349 es 349000 mod 997 = 50 , este es el resultado esperado.

Al trabajar en base 2, determinar el valor correcto de m en cada etapa es particularmente fácil: si el bit actual es par, m es cero, y si es impar, m es uno. Además, dado que cada paso de MultiPrecisionREDC requiere conocer solo el bit menos significativo, la multiplicación de Montgomery se puede combinar fácilmente con un sumador con acarreo guardado .

Debido a que la reducción de Montgomery evita los pasos de corrección necesarios en la división convencional cuando las estimaciones de los dígitos del cociente son inexactas, está prácticamente libre de las bifurcaciones condicionales que son los principales objetivos de los ataques de canal lateral de temporización y potencia ; la secuencia de instrucciones ejecutadas es independiente de los valores de los operandos de entrada. La única excepción es la resta condicional final del módulo, pero se puede modificar fácilmente (para restar siempre algo, ya sea el módulo o cero) para hacerla resistente. ^{[ 5 ]} Por supuesto, es necesario asegurar que el algoritmo de exponenciación construido alrededor de la primitiva de multiplicación también sea resistente. ^{[ 5 ] [ 7 ]}

• Reducción de Barrett

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