Inverso multiplicativo modular

Concepto en aritmética modular

En matemáticas , particularmente en el área de la aritmética , un inverso multiplicativo modular de un entero a es un entero x tal que el producto ax es congruente con 1 con respecto al módulo m . ^[1] En la notación estándar de la aritmética modular, esta congruencia se escribe como

${\displaystyle ax\equiv 1{\pmod {m}},}$

que es la forma abreviada de escribir la afirmación de que m divide (uniformemente) la cantidad ax − 1 , o, dicho de otra manera, el resto después de dividir ax por el entero m es 1. Si a tiene un inverso módulo m , entonces hay un número infinito de soluciones de esta congruencia, que forman una clase de congruencia con respecto a este módulo. Además, cualquier entero que sea congruente con a (es decir, en la clase de congruencia de a ) tiene cualquier elemento de la clase de congruencia de x como inverso multiplicativo modular. Usando la notación de para indicar la clase de congruencia que contiene a w , esto se puede expresar diciendo que el inverso multiplicativo módulo de la clase de congruencia es la clase de congruencia tal que: ${\displaystyle {\overline {w}}}$ ${\displaystyle {\overline {a}}}$ ${\displaystyle {\overline {x}}}$

${\displaystyle {\overline {a}}\cdot _{m}{\overline {x}}={\overline {1}},}$

donde el símbolo denota la multiplicación de clases de equivalencia módulo m . ^[2] Escrito de esta manera, se representa claramente la analogía con el concepto habitual de inverso multiplicativo en el conjunto de números racionales o reales , reemplazando los números por clases de congruencia y alterando la operación binaria apropiadamente. ${\displaystyle \cdot _{m}}$

Al igual que con la operación análoga sobre los números reales, un uso fundamental de esta operación es resolver, cuando sea posible, congruencias lineales de la forma

${\displaystyle ax\equiv b{\pmod {m}}.}$

Encontrar inversos multiplicativos modulares también tiene aplicaciones prácticas en el campo de la criptografía , por ejemplo, la criptografía de clave pública y el algoritmo RSA . ^{[3] [4] [5]} Un beneficio para la implementación informática de estas aplicaciones es que existe un algoritmo muy rápido (el algoritmo euclidiano extendido ) que se puede utilizar para el cálculo de inversos multiplicativos modulares.

Aritmética modular

Para un entero positivo dado m , se dice que dos enteros, a y b , son congruentes módulo m si m divide su diferencia. Esta relación binaria se denota por,

${\displaystyle a\equiv b{\pmod {m}}.}$

Esta es una relación de equivalencia en el conjunto de números enteros , y las clases de equivalencia se denominan clases de congruencia módulo m o clases de residuo módulo m . Sea la clase de congruencia que contiene el número entero a , ^[6] entonces ${\displaystyle \mathbb {Z} }$ ${\displaystyle {\overline {a}}}$

${\displaystyle {\overline {a}}=\{b\in \mathbb {Z} \mid a\equiv b{\pmod {m}}\}.}$

Una congruencia lineal es una congruencia modular de la forma

${\displaystyle ax\equiv b{\pmod {m}}.}$

A diferencia de las ecuaciones lineales sobre números reales, las congruencias lineales pueden tener cero, una o varias soluciones. Si x es una solución de una congruencia lineal entonces cada elemento en es también una solución, por lo que, cuando hablamos del número de soluciones de una congruencia lineal nos referimos al número de clases de congruencia diferentes que contienen soluciones. ${\displaystyle {\overline {x}}}$

Si d es el máximo común divisor de a y m entonces la congruencia lineal ax ≡ b (mod m ) tiene soluciones si y sólo si d divide a b . Si d divide a b , entonces hay exactamente d soluciones. ^[7]

Un inverso multiplicativo modular de un entero a con respecto al módulo m es una solución de la congruencia lineal

${\displaystyle ax\equiv 1{\pmod {m}}.}$

El resultado anterior dice que existe una solución si y solo si mcd( a , m ) = 1 , es decir, a y m deben ser primos entre sí (es decir, coprimos). Además, cuando se cumple esta condición, hay exactamente una solución, es decir, cuando existe, un inverso multiplicativo modular es único: ^[8] Si b y b' son ambos inversos multiplicativos modulares de a respecto del módulo m , entonces

${\displaystyle ab\equiv ab'\equiv 1{\pmod {m}},}$

por lo tanto

${\displaystyle a(b-b')\equiv 0{\pmod {m}}.}$

Si a ≡ 0 (mod m ) , entonces mcd( a , m ) = a , y a ni siquiera tendrá un inverso multiplicativo modular. Por lo tanto, b ≡ b' (mod m ) .

Cuando ax ≡ 1 (mod m ) tiene una solución, a menudo se denota de esta manera:

${\displaystyle x\equiv a^{-1}{\pmod {m}},}$

pero esto puede considerarse un abuso de notación ya que podría malinterpretarse como el recíproco de (que, al contrario del inverso multiplicativo modular, no es un entero excepto cuando a es 1 o -1). La notación sería adecuada si a se interpreta como un token que representa la clase de congruencia , ya que el inverso multiplicativo de una clase de congruencia es una clase de congruencia con la multiplicación definida en la siguiente sección. ${\displaystyle a}$ ${\displaystyle {\overline {a}}}$

Módulo de números enterosmetro

La relación de congruencia, módulo m , divide el conjunto de números enteros en m clases de congruencia. Las operaciones de adición y multiplicación se pueden definir en estos m objetos de la siguiente manera: para sumar o multiplicar dos clases de congruencia, primero se elige un representante (de cualquier manera) de cada clase, luego se realiza la operación habitual para números enteros en los dos representantes y finalmente se toma la clase de congruencia en la que se encuentra el resultado de la operación de números enteros como el resultado de la operación en las clases de congruencia. En símbolos, con y que representan las operaciones en las clases de congruencia, estas definiciones son ${\displaystyle +_{m}}$ ${\displaystyle \cdot _{m}}$

${\displaystyle {\overline {a}}+_{m}{\overline {b}}={\overline {a+b}}}$

y

${\displaystyle {\overline {a}}\cdot _{m}{\overline {b}}={\overline {ab}}.}$

Estas operaciones están bien definidas , lo que significa que el resultado final no depende de las elecciones que los representantes hicieron para obtener el resultado.

Las m clases de congruencia con estas dos operaciones definidas forman un anillo , llamado anillo de números enteros módulo m . Existen varias notaciones utilizadas para estos objetos algebraicos, la más frecuente es o , pero varios textos elementales y áreas de aplicación utilizan una notación simplificada cuando es poco probable que se produzcan confusiones con otros objetos algebraicos. ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /m}$ ${\displaystyle \mathbb {Z} _{m}}$

Las clases de congruencia de los números enteros módulo m se conocían tradicionalmente como clases de residuo módulo m , lo que refleja el hecho de que todos los elementos de una clase de congruencia tienen el mismo residuo (es decir, "residuo") al ser divididos por m . Cualquier conjunto de m números enteros seleccionados de modo que cada uno provenga de una clase de congruencia diferente módulo m se denomina sistema completo de residuos módulo m . ^[9] El algoritmo de división muestra que el conjunto de números enteros, {0, 1, 2, ..., m − 1} forma un sistema completo de residuos módulo m , conocido como el sistema de residuo mínimo módulo m . Al trabajar con problemas aritméticos, a veces es más conveniente trabajar con un sistema completo de residuos y utilizar el lenguaje de las congruencias, mientras que en otras ocasiones es más útil el punto de vista de las clases de congruencia del anillo . ^[10] ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Grupo multiplicativo de números enteros módulometro

No todos los elementos de un sistema de residuos completo módulo m tienen un inverso multiplicativo modular, por ejemplo, cero nunca lo tiene. Después de eliminar los elementos de un sistema de residuos completo que no son primos entre sí con m , lo que queda se llama sistema de residuos reducido , cuyos elementos tienen todos inversos multiplicativos modulares. El número de elementos en un sistema de residuos reducido es , donde es la función totient de Euler , es decir, el número de números enteros positivos menores que m que son primos entre sí con m . ${\displaystyle \phi (m)}$ ${\displaystyle \phi }$

En un anillo general con unidad no todos los elementos tienen un inverso multiplicativo y aquellos que lo tienen se llaman unidades . Como el producto de dos unidades es una unidad, las unidades de un anillo forman un grupo , el grupo de unidades del anillo y a menudo se denota por R ^× si R es el nombre del anillo. El grupo de unidades del anillo de números enteros módulo m se llama grupo multiplicativo de números enteros módulo m , y es isomorfo a un sistema de residuos reducidos. En particular, tiene orden (tamaño), . ${\displaystyle \phi (m)}$

En el caso de que m sea un primo , digamos p , entonces y todos los elementos distintos de cero de tienen inversos multiplicativos, por lo tanto es un cuerpo finito . En este caso, el grupo multiplicativo de números enteros módulo p forma un grupo cíclico de orden p − 1 . ${\displaystyle \phi (p)=p-1}$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$ ${\displaystyle \mathbb {Z} /p\mathbb {Z} }$

Ejemplo

Para cualquier entero , siempre se da el caso de que es el inverso multiplicativo modular de con respecto al módulo , ya que . Algunos ejemplos son , , y así sucesivamente. ${\displaystyle n>1}$ ${\displaystyle n^{2}-n+1}$ ${\displaystyle n+1}$ ${\displaystyle n^{2}}$ ${\displaystyle (n+1)(n^{2}-n+1)=n^{3}+1}$ ${\displaystyle 3\times 3\equiv 1{\pmod {4}}}$ ${\displaystyle 4\times 7\equiv 1{\pmod {9}}}$ ${\displaystyle 5\times 13\equiv 1{\pmod {16}}}$

El siguiente ejemplo utiliza el módulo 10: Dos números enteros son congruentes módulo 10 si y solo si su diferencia es divisible por 10, por ejemplo

${\displaystyle 32\equiv 2{\pmod {10}}}$ya que 10 divide 32 − 2 = 30, y

${\displaystyle 111\equiv 1{\pmod {10}}}$ya que 10 divide 111 − 1 = 110.

Algunas de las diez clases de congruencia con respecto a este módulo son:

${\displaystyle {\overline {0}}=\{\cdots ,-20,-10,0,10,20,\cdots \}}$

${\displaystyle {\overline {1}}=\{\cdots ,-19,-9,1,11,21,\cdots \}}$

${\displaystyle {\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}}$y

${\displaystyle {\overline {9}}=\{\cdots ,-11,-1,9,19,29,\cdots \}.}$

La congruencia lineal 4 x ≡ 5 (mod 10) no tiene soluciones ya que los números enteros que son congruentes con 5 (es decir, los de ) son todos impares mientras que 4 x es siempre par. Sin embargo, la congruencia lineal 4 x ≡ 6 (mod 10) tiene dos soluciones, a saber, x = 4 y x = 9 . El mcd(4, 10) = 2 y 2 no divide a 5, pero sí a 6. ${\displaystyle {\overline {5}}}$

Como mcd(3, 10) = 1 , la congruencia lineal 3 x ≡ 1 (mod 10) tendrá soluciones, es decir, existirán inversos multiplicativos modulares de 3 módulo 10. De hecho, 7 satisface esta congruencia (es decir, 21 − 1 = 20). Sin embargo, otros números enteros también satisfacen la congruencia, por ejemplo, 17 y −3 (es decir, 3(17) − 1 = 50 y 3(−3) − 1 = −10). En particular, cada número entero en satisfará la congruencia ya que estos números enteros tienen la forma 7 + 10 r para algún número entero r y ${\displaystyle {\overline {7}}}$

${\displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

es divisible por 10. Esta congruencia tiene solo esta clase de soluciones. La solución en este caso podría haberse obtenido comprobando todos los casos posibles, pero se necesitarían algoritmos sistemáticos para módulos mayores, que se darán en la siguiente sección.

El producto de las clases de congruencia y se puede obtener seleccionando un elemento de , digamos 25, y un elemento de , digamos −2, y observando que su producto (25)(−2) = −50 está en la clase de congruencia . Por lo tanto, . La adición se define de manera similar. Las diez clases de congruencia junto con estas operaciones de adición y multiplicación de clases de congruencia forman el anillo de números enteros módulo 10, es decir, . ${\displaystyle {\overline {5}}}$ ${\displaystyle {\overline {8}}}$ ${\displaystyle {\overline {5}}}$ ${\displaystyle {\overline {8}}}$ ${\displaystyle {\overline {0}}}$ ${\displaystyle {\overline {5}}\cdot _{10}{\overline {8}}={\overline {0}}}$ ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Un sistema de residuos completo módulo 10 puede ser el conjunto {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} donde cada entero está en una clase de congruencia diferente módulo 10. El único sistema de residuos mínimo módulo 10 es {0, 1, 2, ..., 9}. Un sistema de residuos reducido módulo 10 podría ser {1, 3, 7, 9}. El producto de dos clases de congruencia cualesquiera representadas por estos números es nuevamente una de estas cuatro clases de congruencia. Esto implica que estas cuatro clases de congruencia forman un grupo, en este caso el grupo cíclico de orden cuatro, que tiene 3 o 7 como generador (multiplicativo). Las clases de congruencia representadas forman el grupo de unidades del anillo . Estas clases de congruencia son precisamente las que tienen inversos multiplicativos modulares. ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$

Cálculo

Algoritmo euclidiano extendido

Se puede encontrar un inverso multiplicativo modular de un módulo m utilizando el algoritmo euclidiano extendido.

El algoritmo de Euclides determina el máximo común divisor (mcd) de dos números enteros, por ejemplo a y m . Si a tiene un inverso multiplicativo módulo m , este mcd debe ser 1. La última de varias ecuaciones producidas por el algoritmo puede resolverse para este mcd. Luego, utilizando un método llamado "sustitución hacia atrás", se puede obtener una expresión que conecta los parámetros originales y este mcd. En otras palabras, se puede encontrar que los números enteros x e y satisfacen la identidad de Bézout .

${\displaystyle ax+my=\gcd(a,m)=1.}$

Reescrito, esto es

${\displaystyle ax-1=(-y)m,}$

eso es,

${\displaystyle ax\equiv 1{\pmod {m}},}$

Por lo tanto, se ha calculado un inverso multiplicativo modular de a . Una versión más eficiente del algoritmo es el algoritmo euclidiano extendido, que, mediante el uso de ecuaciones auxiliares, reduce dos pasadas por el algoritmo (la sustitución hacia atrás puede considerarse como pasar por el algoritmo en sentido inverso) a solo una.

En notación O grande , este algoritmo se ejecuta en un tiempo O(log ² ( m )) , asumiendo | a | < m , y se considera muy rápido y generalmente más eficiente que su alternativa, la exponenciación.

Utilizando el teorema de Euler

Como alternativa al algoritmo euclidiano extendido, se puede utilizar el teorema de Euler para calcular inversas modulares. ^[11]

Según el teorema de Euler , si a es coprimo de m , es decir, mcd( a , m ) = 1 , entonces

${\displaystyle a^{\phi (m)}\equiv 1{\pmod {m}},}$

donde es la función totiente de Euler . Esto se deduce del hecho de que a pertenece al grupo multiplicativo ^× si y solo si a es coprimo con m . Por lo tanto, se puede encontrar directamente un inverso multiplicativo modular: ${\displaystyle \phi }$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )}$

${\displaystyle a^{\phi (m)-1}\equiv a^{-1}{\pmod {m}}.}$

En el caso especial donde m es un primo y un inverso modular está dado por ${\displaystyle \phi (m)=m-1}$

${\displaystyle a^{-1}\equiv a^{m-2}{\pmod {m}}.}$

Este método suele ser más lento que el algoritmo euclidiano extendido, pero a veces se utiliza cuando ya se dispone de una implementación para la exponenciación modular. Algunas desventajas de este método son:

• El valor debe conocerse y el cálculo conocido más eficiente requiere la factorización de m . Se cree ampliamente que la factorización es un problema computacional difícil. Sin embargo, el cálculo es sencillo cuando se conoce la factorización prima de m . ${\displaystyle \phi (m)}$ ${\displaystyle \phi (m)}$
• El costo relativo de la exponenciación. Aunque se puede implementar de manera más eficiente utilizando la exponenciación modular , cuando se involucran valores grandes de m , esto se calcula de manera más eficiente con el método de reducción de Montgomery , el cual, en sí mismo, requiere un inverso modular módulo m , que es lo que se debía calcular en primer lugar. Sin el método de Montgomery, la exponenciación binaria estándar , que requiere la división módulo m en cada paso, es una operación lenta cuando m es grande.

Una ventaja notable de esta técnica es que no hay ramificaciones condicionales que dependan del valor de a y, por lo tanto, el valor de a , que puede ser un secreto importante en criptografía de clave pública , puede protegerse de ataques de canal lateral . Por este motivo, la implementación estándar de Curve25519 utiliza esta técnica para calcular una inversa.

Inversas múltiples

Es posible calcular la inversa de números múltiples a _i , módulo un m común , con una única invocación del algoritmo euclidiano y tres multiplicaciones por entrada adicional. ^[12] La idea básica es formar el producto de todos los a _i , invertirlo, luego multiplicarlo por a _j para todos los j ≠ i para dejar solo el a deseado.^-1
_yo.

Más específicamente, el algoritmo es (toda la aritmética realizada módulo m ):

1. Calcular los productos de prefijo para todos los i ≤ n . ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$
2. Calcular b⁻¹
   _nutilizando cualquier algoritmo disponible.
3. Para i desde n hasta 2, calcule
   • a^-1
     _yo= b^-1
     _yob _{i −1} y
   • b^-1
     _{yo -1}= b^-1
     _youn _yo .
4. Por último, un^-1
   ₁= b^-1
   ₁.

Es posible realizar las multiplicaciones en una estructura de árbol en lugar de hacerlo linealmente para aprovechar la computación paralela .

Aplicaciones

Encontrar un inverso multiplicativo modular tiene muchas aplicaciones en algoritmos que se basan en la teoría de la aritmética modular. Por ejemplo, en criptografía, el uso de la aritmética modular permite que algunas operaciones se realicen más rápidamente y con menos requisitos de almacenamiento, mientras que otras operaciones se vuelven más difíciles. ^[13] Ambas características se pueden utilizar de forma ventajosa. En particular, en el algoritmo RSA, el cifrado y descifrado de un mensaje se realiza utilizando un par de números que son inversos multiplicativos con respecto a un módulo cuidadosamente seleccionado. Uno de estos números se hace público y se puede utilizar en un procedimiento de cifrado rápido, mientras que el otro, utilizado en el procedimiento de descifrado, se mantiene oculto. Determinar el número oculto a partir del número público se considera computacionalmente inviable y esto es lo que hace que el sistema funcione para garantizar la privacidad. ^[14]

Como otro ejemplo en un contexto diferente, considere el problema de división exacta en informática, donde tiene una lista de números impares del tamaño de una palabra, cada uno divisible por k , y desea dividirlos todos por k . Una solución es la siguiente:

1. Utilice el algoritmo euclidiano extendido para calcular k ⁻¹ , el inverso multiplicativo modular de k mod 2 ^w , donde w es la cantidad de bits en una palabra. Este inverso existirá ya que los números son impares y el módulo no tiene factores impares.
2. Para cada número de la lista, multiplíquelo por k ⁻¹ y tome la palabra menos significativa del resultado.

En muchas máquinas, en particular aquellas que no tienen soporte de hardware para la división, la división es una operación más lenta que la multiplicación, por lo que este enfoque puede generar una aceleración considerable. El primer paso es relativamente lento, pero solo es necesario realizarlo una vez.

Los inversos multiplicativos modulares se utilizan para obtener una solución de un sistema de congruencias lineales que está garantizada por el Teorema del Resto Chino .

Por ejemplo, el sistema

X ≡ 4 (mód 5)

X ≡ 4 (mód 7)

X ≡ 6 (mód 11)

tiene soluciones comunes ya que 5, 7 y 11 son primos entre sí . La solución viene dada por

X = t1 (7 _× 11)×4 + t2 (5× ₁₁ )×4 + t3 (5 _× 7)×6

dónde

t ₁ = 3 es el inverso multiplicativo modular de 7 × 11 (mod 5),

t ₂ = 6 es el inverso multiplicativo modular de 5 × 11 (mod 7) y

t ₃ = 6 es el inverso multiplicativo modular de 5 × 7 (mod 11).

De este modo,

X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504

y en su forma reducida única

X ≡ 3504 ≡ 39 (mód 385)

ya que 385 es el MCM de 5,7 y 11.

Además, el inverso multiplicativo modular ocupa un lugar destacado en la definición de la suma de Kloosterman .

Véase también

• Generador congruencial inverso : un generador de números pseudoaleatorios que utiliza inversos multiplicativos modulares
• Reconstrucción racional (matemáticas)

Notas

1. Rosen 1993, pág. 132.
2. Schumacher 1996, pág. 88.
3. Stinson, Douglas R. (1995), Criptografía / Teoría y práctica , CRC Press, págs. 124-128, ISBN 0-8493-8521-0
4. Trappe y Washington 2006, págs. 164-169.
5. Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. (2016). PKCS #1: Especificaciones de criptografía RSA. sec. 2.2. doi : 10.17487/RFC8017 . RFC 8017. Consultado el 21 de enero de 2017 .
6. A menudo se utilizan otras notaciones, incluidas [ a ] ​​y [ a ] _​​m .
7. Irlanda y Rosen 1990, pág. 32
8. Shoup, Victor (2005), Una introducción computacional a la teoría de números y al álgebra, Cambridge University Press, Teorema 2.4, pág. 15, ISBN 9780521851541
9. Rosen 1993, pág. 121
10. Irlanda y Rosen 1990, pág. 31
11. Thomas Koshy. Teoría elemental de números con aplicaciones, 2.ª edición. ISBN 978-0-12-372487-8 . Pág. 346. 
12. Brent, Richard P. ; Zimmermann, Paul (diciembre de 2010). "§2.5.1 Varias inversiones a la vez" (PDF) . Aritmética informática moderna. Cambridge Monographs on Computational and Applied Mathematics. Vol. 18. Cambridge University Press. págs. 67–68. ISBN 978-0-521-19469-3.
13. Trappe y Washington 2006, pág. 167
14. Trappe y Washington 2006, pág. 165

Referencias

• Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (2.ª ed.), Springer-Verlag, ISBN 0-387-97329-X
• Rosen, Kenneth H. (1993), Teoría de números elementales y sus aplicaciones (3.ª ed.), Addison-Wesley, ISBN 978-0-201-57889-8
• Schumacher, Carol (1996). Capítulo cero: Nociones fundamentales de las matemáticas abstractas . Addison-Wesley. ISBN 0-201-82653-4.
• Trappe, Wade; Washington, Lawrence C. (2006), Introducción a la criptografía con teoría de codificación (2.ª ed.), Prentice-Hall, ISBN 978-0-13-186239-5

Enlaces externos

• Weisstein, Eric W. "Inversa modular". MundoMatemático .
• Guevara Vasquez, Fernando proporciona un ejemplo resuelto de cómo resolver el inverso multiplicativo módulo utilizando el algoritmo de Euclides.