En el cálculo aritmético 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.Martin Kochanski, "Montgomery Multiplication" a colloquial explanation.

Se basa en una representación especial de los números, llamada forma de Montgomery. El algoritmo utiliza las formas de Montgomery de y para calcular eficientemente la forma de Montgomery de . La eficiencia se debe a que se evitan costosas operaciones de división. La multiplicación modular clásica reduce el producto de doble ancho mediante la división por , conservando solo el resto. Esta división requiere la estimación y corrección de los dígitos del cociente. La forma de Montgomery, en cambio, depende de una constante que es coprima con , y la única división necesaria es la división por . La constante se puede elegir de forma que la división por sea sencilla, lo que mejora significativamente la velocidad del algoritmo. En las computadoras binarias, siempre es una potencia de dos, ya que la división por potencias de dos se puede implementar desplazando bits.

La necesidad de convertir y a la forma de Montgomery y pasar su producto desde la forma Montgomery a la base usual implica que calcular un solo producto mediante la multiplicación de Montgomery es más lento que los algoritmos convencionales o que la 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 pasan a ser una fracción insignificante del cálculo total. Muchos criptosistemas importantes, como RSA y el intercambio de claves de 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 una potencia de dos son más rápidos que las alternativas disponibles. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. , chapter 14.

Aritmética modular Sea un módulo entero positivo. El anillo cociente consta de clases de residuos módulo , es decir, sus elementos son conjuntos de la forma:

donde abarca los enteros. Cada clase de residuos es un conjunto de enteros tal que la diferencia entre dos enteros cualesquiera del conjunto es divisible por (y la clase de residuos es máxima con respecto a esta propiedad. Los enteros no se excluyen de la clase de residuos a menos que violen la condición de divisibilidad. La clase de residuos correspondiente a se denota como . La igualdad de clases de residuos se denomina congruencia y se denota como:

Almacenar una clase de residuos completa en un ordenador es imposible, porque la clase de residuos tiene infinitos elementos. En cambio, las clases de residuo se almacenan como representantes. Por convención, estos representantes son los enteros para los cuales . Si es un entero, entonces el representante de se escribe . 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 como .

Las operaciones aritméticas con clases de residuo se realizan aplicando primero operaciones aritméticas con enteros a sus representantes. El resultado de la operación con enteros 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 , entonces la suma de las clases de residuo y se calcula hallando la suma entera , y luego determinando , 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 .

Forma de Montgomery Si y son enteros en el rango , entonces su suma está en el rango y su diferencia está en el rango , por lo que determinar el representante en requiere como máximo una resta o la suma (respectivamente) de . Sin embargo, el producto está en el rango . Almacenar el producto entero intermedio requiere el doble de bits que o , y determinar eficientemente el representante en requiere división. Matemáticamente, el entero entre 0 y que es La función congruente con se puede expresar aplicando el teorema de la división euclídea:

donde es el cociente y , el resto, se encuentra en el intervalo . El resto es . Para determinar , se calcula y luego se resta de . Por ejemplo, nuevamente con , el producto se determina calculando , dividiendo y restando .

Dado que el cálculo de requiere división, resulta excesivamente costoso en la mayoría de los casos de hardware. La notación de Montgomery es una forma diferente de expresar los elementos del anillo en la que se pueden calcular productos modulares sin divisiones costosas. Si bien las divisiones siguen siendo necesarias, se pueden realizar con respecto a un divisor diferente, . Este divisor puede ser una potencia de dos, para la que la división se puede reemplazar por un desplazamiento de bits, o un número entero de palabras de máquina, para el cual la división se puede reemplazar 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 debe ser un entero positivo tal que . Para fines computacionales, también es necesario que la división y la reducción módulo sean económicas, y el módulo no es útil para la multiplicación modular a menos que . La forma de Montgomery de la clase de residuos con respecto a es , es decir, es el representante de la clase de residuos . Por ejemplo, supóngase que y . Las formas de Montgomery de 3, 5, 7 y 15 son , , y , respectivamente.

La suma y la resta en la forma de Montgomery son iguales a la suma y la resta modular ordinarias debido a la propiedad distributiva:

Téngase en cuenta que realizar la operación en la forma de Montgomery no pierde información en comparación con realizarla en el anillo cociente . Esto es consecuencia de que, debido a que , la multiplicación por es un isomorfismo en el grupo aditivo (. Por ejemplo, , que en forma de Montgomery se convierte en .

Sin embargo, la multiplicación en forma de Montgomery es aparentemente más complicada. El producto usual de y no representa el producto de y porque tiene un factor adicional de :

El cálculo de productos en forma de Montgomery requiere eliminar el factor adicional de . Si bien la división por es sencilla, el producto intermedio no es divisible por porque la operación módulo ha destruido esa propiedad. Así, por ejemplo, el producto de las formas de Montgomery de 7 y 15 módulo 17, con , 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 extra de .

Eliminar el factor extra de se puede hacer multiplicando por un entero tal que , es decir, por un cuya clase de residuo sea el inverso de módulo . Luego, trabajando en módulo ,

El entero existe debido a la suposición de que y son coprimos. Se puede construir usando el algoritmo euclídeo extendido. El algoritmo euclídeo extendido determina eficientemente los enteros y que satisfacen la identidad de Bézout , y:

Esto demuestra que es posible realizar multiplicaciones en forma de Montgomery. Un algoritmo sencillo para multiplicar números en forma de Montgomery consiste, por lo tanto, en multiplicar , y como enteros y reducir al módulo .

Por ejemplo, para multiplicar 7 y 15 módulo 17 en forma de Montgomery, nuevamente con , se calcula el producto de 3 y 4 para obtener 12, como se indicó anteriormente. El algoritmo euclídeo extendido implica que , por lo tanto . Se multiplica 12 por 8 para obtener 96 y se reduce módulo 17 para obtener 11. Esta es la forma de Montgomery de 3, como se esperaba.

Algoritmo REDC 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 y dividir por . La reducción de Montgomery, también conocida como REDC, es un algoritmo que calcula simultáneamente el producto por y reduce módulo más rápidamente que el método intuitivo convencional. A diferencia de la reducción modular convencional, que se centra en hacer que el número sea menor que , la reducción de Montgomery se centra en hacer que el número sea más divisible por . Esto se logra sumando un múltiplo pequeño de que se elige sofisticadamente para cancelar el residuo módulo . Dividir el resultado por produce un número mucho menor. Este número es tan mucho menor que es casi la reducción módulo , y calcular la reducción módulo solo requiere una resta condicional final. Dado que todos los cálculos se realizan utilizando únicamente reducciones y divisiones con respecto a , y no a , el algoritmo se ejecuta más rápido que una reducción modular directa por división.

function REDC is input: Integers R and N with , Integer N′ in such that , Integer T in the range . output: Integer S in the range such that

m ← ((T mod R)N′) mod R t ← (T + mN) / R if t ≥ N then return else return t end if end function

Para comprobar la corrección de este algoritmo, obsérvese primero que se elige precisamente de manera que sea divisible por . Un número es divisible por si y solo si es congruente con módulo cero, y se tiene:

Por lo tanto, es un entero. En segundo lugar, la salida es o , ambas congruentes con . Para demostrar que la salida es congruente con , basta con probar que es , y que satisface:

Por consiguiente, la salida tiene la clase de residuo correcta. En tercer lugar, pertenece a , por lo que se encuentra entre 0 y . Por lo tanto, es menor que , y como es un entero, esto sitúa a en el rango de . En consecuencia, reducir al rango deseado requiere como máximo una sola resta, por lo que el resultado del algoritmo se encuentra dentro del rango correcto.

Para usar REDC y calcular el producto de 7 y 15 módulo 17, primero se convierte a la forma de Montgomery y se multiplica como enteros para obtener 12, como se indicó anteriormente. A continuación, se aplica REDC con , , y . El primer paso establece en . El segundo paso asigna a el valor de . Nótese que es 1100, un múltiplo de 100, como se esperaba. se establece en 11, que es menor que 17, por lo que el resultado final es 11, lo cual coincide con el cálculo de la sección anterior.

Como otro ejemplo, considérese el producto con . Utilizando el algoritmo euclídeo extendido, se calcula , de modo que será . Las formas de Montgomery de 7 y 15 son y , respectivamente. Su producto, 28, es la entrada para REDC, y dado que , se cumplen los supuestos de REDC. Para ejecutar REDC, se asigna a . Luego, , por lo que . Dado que , esta es la forma de Montgomery de .

Interpretación mediante el teorema chino del resto Fuente:

Dado el módulo y la base de Montgomery utilizada en una reducción de Montgomery, considérese el anillo de residuos

y el isomorfismo que se deduce del teorema chino del resto (TCR).

Reconstrucción según el TCR para un producto intermedio Para un entero con (como suele ocurrir cuando surge de la multiplicación de dos residuos), tómense sus reducciones:

El teorema chino del resto (TCR) proporciona la fórmula de reconstrucción explícita:

Como el lado derecho ya se ha calculado módulo , también se puede escribir como:

Ambos sumandos se encuentran en el intervalo semiabierto :

Por lo tanto, como ecuaciones enteras (no meras congruencias), se tiene que:

o bien,

Aislar el término que contiene T mod N Para resolver , se aísla el primer sumando:

Cada cantidad anterior es un entero, y el lado izquierdo es un múltiplo de ; por lo tanto, cada lado derecho es divisible por . Dividiendo por , se obtiene:

Relaciones resultantes En consecuencia,

Esto evidencia dos hechos clave:

Congruencia

Límite numérico

Por lo tanto, al reducir