En matemáticas , particularmente en el área de la teoría de números , un inverso multiplicativo modular de un número entero a es un número 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
que es la forma abreviada de escribir el enunciado 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 módulo inverso m, 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 número entero que es congruente con un (es decir, en una 'clase de congruencia s) tendrá ningún elemento de x ' s congruencia clase como un inverso multiplicativo modular. Usando la notación depara indicar la clase de congruencia que contiene w , esto se puede expresar diciendo que el módulo inverso multiplicativo de la clase de congruencia es la clase de congruencia tal que:
donde el simbolo 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 un 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.
Al igual que con la operación análoga con los números reales, un uso fundamental de esta operación es resolver, cuando sea posible, congruencias lineales de la forma,
Encontrar inversos multiplicativos modulares también tiene aplicaciones prácticas en el campo de la criptografía , es decir, 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 inversas multiplicativas modulares.
Aritmética modular
Para un determinado número entero positivo m , dos enteros, un y b , se dice que son congruentes módulo m si m divide su diferencia. Esta relación binaria se denota por,
Ésta es una relación de equivalencia en el conjunto de enteros, ℤ , y las clases de equivalencia se denominan clases de congruencia módulo m o clases de residuos módulo m . Dejardenotar la clase de congruencia que contiene el entero a , [6] luego
Una congruencia lineal es una congruencia modular de la forma
A diferencia de las ecuaciones lineales sobre los 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 también es una solución, por lo que, cuando hablamos del número de soluciones de una congruencia lineal, nos estamos refiriendo al número de diferentes clases de congruencia que contienen soluciones.
Si d es el máximo común divisor de un y m entonces el lineal congruencia ax ≡ b (mod m ) tiene soluciones si y sólo si d divide 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
El resultado anterior dice que existe una solución si y sólo si gcd ( a , m ) = 1 , es decir, una y m deben ser relativamente primos (es decir primos entre sí). Además, cuando se cumple esta condición, hay exactamente una solución, es decir, cuando existe, un inverso multiplicativo modular es único. [8]
Cuando ax ≡ 1 (mod m ) tiene una solución, a menudo se denota de esta manera:
pero esto es un abuso de notación ya que un inverso multiplicativo modular es un número entero y a −1 no es un número entero cuando a es un número entero distinto de 1 o - 1. La notación sería apropiada si a se interpreta como un token que representa el 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.
Enteros módulo m
La relación de congruencia, módulo m , divide el conjunto de enteros en m clases de congruencia. Las operaciones de suma y multiplicación se pueden definir en estos m objetos de la siguiente manera: Para sumar o multiplicar dos clases de congruencia, primero elija un representante (de cualquier manera) de cada clase, luego realice la operación habitual para números enteros en los dos representantes. y finalmente tome la clase de congruencia en la que se encuentra el resultado de la operación entera como resultado de la operación en las clases de congruencia. En símbolos, con y representando las operaciones en clases de congruencia, estas definiciones son
y
Estas operaciones están bien definidas , lo que significa que el resultado final no depende de las elecciones de los representantes que se hicieron para obtener el resultado.
Las m clases de congruencia con estas dos operaciones definidas forman un anillo , llamado anillo de enteros módulo m . Hay varias notaciones que se utilizan para estos objetos algebraicos, la mayoría de las veces o , pero varios textos elementales y áreas de aplicación utilizan una notación simplificada cuando la confusión con otros objetos algebraicos es poco probable.
Las clases de congruencia de los enteros módulo m se conocían tradicionalmente como clases de residuos módulo m , lo que refleja el hecho de que todos los elementos de una clase de congruencia tienen el mismo resto (es decir, "residuo") al ser divididos por m . Cualquier conjunto de m 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} forman un sistema completo de residuos módulo m , conocido como el sistema de residuos mínimos módulo m . Al trabajar con problemas aritméticos, a veces es más conveniente trabajar con un sistema completo de residuos y usar el lenguaje de congruencias, mientras que otras veces el punto de vista de las clases de congruencias del anillo.es más útil. [10]
Grupo multiplicativo de enteros módulo m
No todos los elementos de un sistema de residuos completo módulo m tienen un inverso multiplicativo modular, por ejemplo, el cero nunca lo tiene. Después de eliminar los elementos de un sistema de residuos completo que no son relativamente primos am , lo que queda se llama un sistema de residuos reducido , todos cuyos elementos tienen inversos multiplicativos modulares. El número de elementos en un sistema de residuos reducidos es, dónde es la función totient de Euler , es decir, el número de enteros positivos menores que m que son relativamente primos am .
En un anillo general con unidad no todos los elementos tienen un inverso multiplicativo y los 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 denomina grupo multiplicativo de números enteros módulo m , y es isomorfo a un sistema de residuo reducido. En particular, tiene orden (tamaño),.
En el caso de que m sea primo , digamos p , entonces y todos los elementos distintos de cero de tienen inversos multiplicativos, por lo tanto es un campo finito . En este caso, el grupo multiplicativo de números enteros módulo p forma un grupo cíclico de orden p - 1 .
Ejemplo
Para ilustrar las definiciones anteriores, considere el siguiente ejemplo utilizando el módulo 10.
Dos enteros son congruentes mod 10 si y solo si su diferencia es divisible por 10, por ejemplo
- ya que 10 divide 32 - 12 = 20, y
- ya que 10 divide 111 - 1 = 110.
Algunas de las diez clases de congruencia con respecto a este módulo son:
- y
La congruencia lineal 4 x ≡ 5 (mod 10) no tiene soluciones ya que los enteros que son congruentes con 5 (es decir, aquellos en) 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 divide a 6.
Dado que 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 entero ensatisfará la congruencia ya que estos enteros tienen la forma 7 + 10 r para algún entero r y
es claramente divisible por 10. Esta congruencia sólo tiene esta clase de soluciones de congruencia. La solución en este caso podría haberse obtenido al verificar todos los casos posibles, pero se necesitarían algoritmos sistemáticos para módulos más grandes y estos se darán en la siguiente sección.
El producto de 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 suma se define de manera similar. Las diez clases de congruencia junto con estas operaciones de suma y multiplicación de clases de congruencia forman el anillo de números enteros módulo 10, es decir,.
Un sistema de residuos completo módulo 10 puede ser el conjunto {10, −9, 2, 13, 24, −15, 26, 37, 8, 9} donde cada número entero está en una clase de congruencia diferente módulo 10. El único sistema de residuos mínimos módulo 10 es {0, 1, 2, ..., 9}. Un sistema de residuo 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 inversas multiplicativas modulares.
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 una y m . Si a tiene un módulo inverso multiplicativo m , este mcd debe ser 1. La última de varias ecuaciones producidas por el algoritmo puede resolverse para este mcd. Luego, usando un método llamado "sustitución inversa", se puede obtener una expresión que conecta los parámetros originales y este mcd. En otras palabras, números enteros x e y se pueden encontrar para satisfacer la identidad de Bézout ,
Reescrito, esto es
es decir,
por 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 a través del algoritmo (se puede pensar que la sustitución hacia atrás pasa a través del algoritmo a la inversa) a solo una.
En notación O grande , este algoritmo se ejecuta en el tiempo O (log ( m ) 2 ) , asumiendo | a | < m , y se considera que es muy rápido y generalmente más eficiente que su alternativa, la exponenciación.
Usando el teorema de Euler
Como alternativa al algoritmo euclidiano extendido, el teorema de Euler puede usarse para calcular inversos modulares. [11]
De acuerdo con el teorema de Euler , si una es primos entre sí a m , es decir, gcd ( a , m ) = 1 , entonces
dónde es la función totient de Euler . Esto se sigue del hecho de que a pertenece al grupo multiplicativo× si y solo si a es coprime a m . Por lo tanto, un inverso multiplicativo modular se puede encontrar directamente:
En el caso especial donde m es primo, y un inverso modular viene dado por
Este método es generalmente más lento que el algoritmo euclidiano extendido, pero a veces se usa cuando una implementación para exponenciación modular ya está disponible. Algunas desventajas de este método incluyen:
- El valor debe ser conocido y el cálculo conocido más eficiente requiere la factorización de m . Se cree ampliamente que la factorización es un problema computacionalmente difícil. Sin embargo, calculandoes sencillo cuando se conoce la factorización prima de m .
- El costo relativo de exponenciación. Aunque se puede implementar de manera más eficiente usando 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 . Este algoritmo en sí mismo requiere un mod m inverso modular , que es lo que debía calcularse en primer lugar. Sin el método de Montgomery, la exponenciación binaria estándar , que requiere la división mod m en cada paso, es una operación lenta cuando m es grande.
Una ventaja notable de esta técnica es que no hay ramas condicionales que dependan del valor de a y, por lo tanto, el valor de a , que puede ser un secreto importante en la criptografía de clave pública , puede protegerse de los ataques de canal lateral . Por esta razón, la implementación estándar de Curve25519 usa esta técnica para calcular una inversa.
Múltiples inversos
Es posible calcular el inverso de varios números a i , módulo a m común , con una sola invocación del algoritmo euclidiano y tres multiplicaciones por entrada adicional. [12] La idea básica es para formar el producto de todos los a i , invertido que, a continuación, se multiplica por una j para todos j ≠ i para dejar sólo la deseada una−1
yo.
Más específicamente, el algoritmo es (toda la aritmética se realiza módulo m ):
- Calcular los productos de prefijo para todo i ≤ n .
- Calcular b−1
n utilizando cualquier algoritmo disponible. - Para i de n hasta 2, calcule
- a−1
yo= b−1
yob i −1 y - B−1
i −1= b−1
yoa i .
- a−1
- Finalmente, un−1
1= b−1
1.
Es posible realizar las multiplicaciones en una estructura de árbol en lugar de 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 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 con ventaja. 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. La determinación del número oculto 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:
- Utilice el algoritmo euclidiano extendido para calcular k −1 , el inverso multiplicativo modular de k mod 2 w , donde w es el número de bits en una palabra. Esta inversa existirá ya que los números son impares y el módulo no tiene factores impares.
- Para cada número de la lista, multiplíquelo por k −1 y tome la palabra menos significativa del resultado.
En muchas máquinas, particularmente aquellas sin 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 producir una aceleración considerable. El primer paso es relativamente lento, pero solo debe realizarse una vez.
Las inversas multiplicativas modulares se utilizan para obtener una solución de un sistema de congruencias lineales que está garantizado por el teorema chino del residuo .
Por ejemplo, el sistema
- X ≡ 4 (mod 5)
- X ≡ 4 (mod 7)
- X ≡ 6 (mod 11)
tiene soluciones comunes ya que 5, 7 y 11 son coprimos por pares . Una solución viene dada por
- X = t 1 (7 × 11) × 4 + t 2 (5 × 11) × 4 + t 3 (5 × 7) × 6
dónde
- t 1 = 3 es el inverso multiplicativo modular de 7 × 11 (mod 5),
- t 2 = 6 es el inverso multiplicativo modular de 5 × 11 (mod 7) y
- t 3 = 6 es el inverso multiplicativo modular de 5 × 7 (mod 11).
Por lo tanto,
- X = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504
y en su forma reducida única
- X ≡ 3504 ≡ 39 (mod 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 .
Ver también
- Generador de congruencia inversora : un generador de números pseudoaleatorios que utiliza inversos multiplicativos modulares
- Reconstrucción racional (matemáticas)
Notas
- ^ Rosen 1993 , p. 132
- ^ Schumacher 1996 , p. 88
- ^ Stinson, Douglas R. (1995), Criptografía / Teoría y práctica , CRC Press, págs. 124-128, ISBN 0-8493-8521-0
- ^ Trappe y Washington , 2006 , págs. 164-169
- ^ Moriarty, K .; Kaliski, B .; Jonsson, J .; Rusch, A. (2016). "PKCS # 1: Especificaciones de criptografía RSA versión 2.2" . Grupo de trabajo de ingeniería de Internet RFC 8017 . Grupo de trabajo de ingeniería de Internet . Consultado el 21 de enero de 2017 .
- ^ A menudo se utilizan otras notaciones, incluidas [ a ] y [ a ] m .
- ^ Irlanda y Rosen 1990 , p. 32
- ^ Shoup, Victor (2005), Una introducción computacional a la teoría de números y el álgebra , Cambridge University Press, Teorema 2.4, p. 15, ISBN 9780521851541
- ^ Rosen 1993 , p. 121
- ^ Irlanda y Rosen 1990 , p. 31
- ^ Thomas Koshy. Teoría elemental de números con aplicaciones , 2ª edición. ISBN 978-0-12-372487-8 . Pág. 346.
- ^ Brent, Richard P .; Zimmermann, Paul (diciembre de 2010). "§2.5.1 Varias inversiones a la vez" (PDF) . Aritmética informática moderna . Monografías de Cambridge sobre Matemática Computacional y Aplicada. 18 . Prensa de la Universidad de Cambridge. págs. 67–68. ISBN 978-0-521-19469-3.
- ^ Trappe y Washington , 2006 , p. 167
- ^ Trappe y Washington , 2006 , p. 165
Referencias
- Irlanda, Kenneth; Rosen, Michael (1990), Una introducción clásica a la teoría de números moderna (2a ed.), Springer-Verlag, ISBN 0-387-97329-X
- Rosen, Kenneth H. (1993), Teoría elemental de números y sus aplicaciones (3a ed.), Addison-Wesley, ISBN 978-0-201-57889-8
- Schumacher, Carol (1996). Capítulo cero: Nociones fundamentales de la matemática abstracta . Addison-Wesley. ISBN 0-201-82653-4.
- Trappe, Wade; Washington, Lawrence C. (2006), Introducción a la criptografía con teoría de la codificación (2a ed.), Prentice-Hall, ISBN 978-0-13-186239-5
enlaces externos
- Weisstein, Eric W. "Modular Inverse" . MathWorld .
- Guevara Vasquez, Fernando proporciona un ejemplo resuelto de cómo resolver el inverso módulo multiplicativo usando el algoritmo de Euclides