Módulo número recíproco

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 20 de abril de 2022; las comprobaciones requieren 18 ediciones .

El inverso módulo an entero a es un entero x tal que el producto ax es congruente con 1 módulo m [1] . En notación aritmética modular estándar , esta equivalencia se escribe como:

hacha\equiv 1{\pmod {m)),

que es una forma abreviada de decir que m divide (sin resto) el valor ax − 1 , o, dicho de otro modo, el resto cuando ax se divide por el entero m es 1. Si a tiene un módulo inverso m , entonces hay un número infinito de soluciones para esta equivalencia, que forman la clase de residuos para este módulo. Además, cualquier número entero que sea equivalente a a (es decir, de la clase de equivalencia a ) tendrá como inverso cualquier elemento de la clase de equivalencia x . Usando la notación para una clase de equivalencia que contiene , la declaración anterior se puede escribir de la siguiente manera: el elemento inverso módulo una clase de equivalencia es una clase de equivalencia tal que $\sobrelínea {w}$ $w$ ${\overline {a}}$ $\overline{x}$

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

donde símbolo significa multiplicación de clases de equivalencia módulo m [2] . Este tipo de notación representa un análogo del concepto habitual de número inverso en el conjunto de los números racionales o reales , si reemplazamos los números con clases de equivalencia y definimos adecuadamente las operaciones binarias . ${\ estilo de visualización \ cdot _ {m}}$

El uso fundamental de esta operación es resolver una equivalencia lineal de la forma:

hacha\equiv b{\pmod {m)).

Encontrar el inverso modular tiene aplicaciones prácticas en el campo de la criptografía , como el criptosistema de clave pública y el algoritmo RSA [3] [4] [5] . La ventaja de implementar estas aplicaciones es que existe un algoritmo muy rápido (algoritmo de Euclid extendido ) que se puede utilizar para calcular inversas modulares.

Aritmética modular

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

a\equiv b{\pmod {m)).

Esta es una relación de equivalencia sobre el conjunto de enteros , y las clases de equivalencia se denominan clases de residuos módulo m . Dejemos denotar una clase de equivalencia que contenga un entero a [6] , entonces $\matemáticas {Z}$ ${\overline {a}}$

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

La comparación lineal es una comparación de módulo de la forma

hacha\equiv b{\pmod {m)).

A diferencia de las ecuaciones lineales en números enteros , una comparación lineal puede tener cero, una o más soluciones. Si x es una solución de una comparación lineal, entonces cualquier elemento de también es una solución, por lo que cuando hablamos del número de soluciones de una comparación lineal, nos referimos al número de clases de equivalencia diferentes que contienen estas soluciones. $\overline{x}$

Si d es el máximo común divisor de a y m , entonces la comparación lineal tiene soluciones si y sólo si d divide a b . Si d divide a b , entonces hay exactamente d soluciones [7] . $hacha\equiv b{\pmod {m))$

El módulo recíproco de un entero a módulo m es la solución a la comparación lineal

hacha\equiv 1{\pmod {m)).

Anteriormente se dijo que existe una solución si y solo si el máximo común divisor de a y m es 1, es decir, a y m deben ser números primos relativos . Además, si se cumple esta condición, hay exactamente una solución, es decir, si existe una solución, el inverso modular es único [8] .

Si tiene una solución, a menudo se denota de la siguiente manera $hacha\equiv 1{\pmod {m))$

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

sin embargo, esto puede considerarse un abuso de , ya que puede malinterpretarse como un recíproco normal (que, a diferencia del módulo recíproco, no es un número entero excepto cuando a es 1 o -1). La notación sería aceptable si a se interpretara como la notación de la clase de residuos , ya que el elemento inverso de la clase de residuos es nuevamente una clase de residuos con la operación de multiplicación definida en la siguiente sección. $a$ ${\overline {a}}$

Números enteros módulo m

La relación de equivalencia módulo m divide el conjunto de enteros en m clases de equivalencia. Las operaciones de suma y multiplicación se pueden definir sobre estos objetos de la siguiente manera: para la suma o multiplicación de clases de equivalencia, primero, se seleccionan representantes de estas clases de cualquier forma, luego se realiza la operación habitual sobre los números enteros seleccionados y, finalmente, el resultado de la operación se encuentra en la clase residual, que es el resultado de la operación sobre las clases. En forma simbólica, con y representando operaciones en clases de residuos, estas definiciones se pueden escribir como ${\ estilo de visualización + _ {m}}$ ${\ estilo de visualización \ cdot _ {m}}$

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

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

Estas operaciones están bien definidas (lo que significa que el resultado final no depende de la elección de los representantes).

Las clases de residuos módulo m con estas dos operaciones forman un anillo , llamado anillo de los enteros módulo m . Se utilizan varias notaciones para estas entidades algebraicas, siendo la más utilizada o , sin embargo, algunos libros de texto y aplicaciones elementales utilizan la notación simplificada a menos que entren en conflicto con otras entidades algebraicas. $\mathbb{Z}/m\mathbb{Z}$ $\mathbb {Z} /m$ $\mathbb {Z} _{m}$

Las clases de residuos de 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 equivalencia tienen el mismo residuo cuando se dividen por m . Cualquier conjunto de enteros m elegidos de diferentes clases de residuos módulo m se denomina sistema completo de residuos módulo m [9] . La división por una columna 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 mínimo de residuos módulo m . Cuando se trabaja con problemas aritméticos, a veces es más conveniente trabajar con el sistema completo de residuos y usar el lenguaje de equivalencia, mientras que en otros casos es más conveniente buscar en términos de clases de equivalencia en anillo [10] . $\mathbb{Z}/m\mathbb{Z}$

El grupo multiplicativo del anillo residual

No todo elemento del sistema completo de residuos módulo m tiene un elemento inverso, por ejemplo, el cero no tiene inverso. Después de eliminar los elementos del sistema completo de residuos que no son primos relativos a m , los elementos restantes, que se denominan el sistema reducido de residuos , tienen todos inversas. El número de elementos en el sistema reducido de residuos es , donde es la función de Euler , es decir, el número de enteros positivos menores que m que son primos relativos a m . ${\ estilo de visualización \ phi (m)}$ $\fi$

En un anillo con unidad general, no todos los elementos tienen inversa , y los que la tienen se llaman invertibles . Dado que el producto de elementos invertibles es invertible, los elementos invertibles de un anillo forman un grupo , el grupo de elementos invertibles de un anillo , y este grupo a menudo se denota como si R fuera el nombre de un anillo. El grupo de elementos invertibles del anillo de enteros módulo m se denomina grupo multiplicativo de enteros módulo m , y es isomorfo al sistema reducido de residuos. En particular, su orden (tamaño) es . ${\ Displaystyle R^ {\ veces}}$ ${\ estilo de visualización \ phi (m)}$

Cuando m es primo , digamos p , entonces todos los elementos distintos de cero tienen inversos, y entonces es un campo finito . En este caso, el grupo multiplicativo de enteros módulo p forma un grupo cíclico de orden p − 1 . ${\ estilo de visualización \ phi (p) = p-1}$ $\mathbb{Z}/p\mathbb{Z}$ $\mathbb{Z}/p\mathbb{Z}$

Ejemplo

Para ilustrar las definiciones anteriores, considere el ejemplo de los números módulo 10.

Dos números son equivalentes en 10 si y solo si su diferencia es divisible por 10, por ejemplo

32\equiv 12{\pmod {10}}

ya que 10 divide a 32 − 12 = 20,

111\equiv 1{\pmod {10}}

ya que 10 divide a 111 − 1 = 110.

Algunas de las clases de residuos para 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\))

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

La comparación lineal no tiene solución porque los enteros congruentes con 5 (es decir, los que están en ) son todos impares, mientras que 4x son todos pares. Sin embargo, la comparación lineal tiene dos soluciones, a saber, y . mcd(4, 10) = 2 y 2 no divide a 5 pero sí a 6. $4x\equiv 5{\pmod {10}}$ ${\sobrelínea {5}}$ $4x\equiv 6{\pmod {10}}$ ${\ estilo de visualización x = 4}$ ${\ estilo de visualización x = 9}$

Como mcd(3, 10) = 1, la comparación lineal tendrá soluciones, es decir, existirá el módulo recíproco de 3 módulo 10. 7 satisface esta ecuación (21 − 1 = 20). Sin embargo, otros enteros también satisfacen esta ecuación, como 17 y −3 (porque 3(17) − 1 = 50 y 3(−3) − 1 = −10). En particular, cualquier número entero de satisfará la ecuación, ya que estos números son de la forma 7 + 10 r para alguna r y es claro que $3x\equiv 1{\pmod {10}}$ ${\overline {7))$

3(7+10r)-1=21+30r-1=20+30r=10(2+3r),

es divisible por 10. Esta ecuación tiene solo una clase de residuos como soluciones. La solución en este caso puede obtenerse simplemente enumerando las posibles clases, pero se necesitan algoritmos sistemáticos para obtener una solución para módulos grandes, y se presentarán en las siguientes secciones.

El producto de las clases de residuos y puede obtenerse eligiendo un elemento de , digamos 25, y un elemento de , digamos −2, y su producto (25)(−2) = −50 está en la clase de equivalencia . Así, . La suma se define de manera similar. Las diez clases de residuos, junto con estas operaciones de suma y multiplicación de clases de residuos, forman un anillo de números enteros módulo 10, es decir, . ${\sobrelínea {5}}$ ${\sobrelínea {8}}$ ${\sobrelínea {5}}$ ${\sobrelínea {8}}$ $\sobrelínea {0}$ ${\overline {5}}\cdot_{10}{\overline {8}}={\overline {0}}$ ${\ estilo de visualización \ 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 pertenece a su propia clase de residuos módulo 10. El sistema de residuos mínimos módulo 10 sirve como {0, 1, 2, ..., 9}. El sistema reducido de residuos módulo 10 puede ser {1, 3, 7, 9}. El producto de dos clases de residuos cualesquiera representadas por estos números es nuevamente una de estas cuatro clases. Se sigue que estas cuatro clases de residuos forman un grupo, en este caso un grupo cíclico de orden 4, teniendo como generador 3 o 7. Las clases de residuos presentadas forman el grupo de elementos invertibles del anillo . Estas clases de residuos son exactamente aquellas que tienen recíprocos de módulo. ${\ estilo de visualización \ mathbb {Z} /10 \ mathbb {Z}}$

Cálculo

Algoritmo de Euclides extendido

El módulo inverso de un módulo m se puede encontrar usando el algoritmo euclidiano extendido.

El algoritmo de Euclides determina el máximo común divisor (mcd) de dos enteros, digamos a y m . Si a tiene el módulo m inverso , este mcd debe ser igual a 1. Las últimas igualdades obtenidas durante la operación del algoritmo se pueden resolver para encontrar el mcd. Luego, utilizando el método de "sustitución inversa", se puede obtener una expresión que vincule los parámetros originales y el GCD. En otras palabras, se pueden encontrar números enteros x e y que satisfagan la igualdad de Bézout ,

hacha+mi={\text{gcd }}(a,m)=1.

Reescribámoslo de la siguiente manera

ax-1=(-y)m,

eso es,

hacha\equiv 1{\pmod {m)),

y se calcula el módulo recíproco de a . Una versión más eficiente es el algoritmo de Euclides extendido, que reduce dos pases del algoritmo (se puede pensar que la sustitución hacia atrás es como pasar por el algoritmo en orden inverso) a uno usando igualdades adicionales.

En notación O grande, este algoritmo se ejecuta en el tiempo bajo el supuesto de que , y se considera muy rápido. Suele ser más eficiente que el algoritmo exponencial alternativo. $O(\log(m)^{2})$ ${\ estilo de visualización | un | <m}$

Usando el teorema de Euler

Como alternativa al algoritmo euclidiano extendido para calcular el elemento inverso modular, se puede considerar el uso del teorema de Euler [11] .

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

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

donde es la función de Euler . Esto se sigue del hecho de que a pertenece al grupo multiplicativo si y sólo si a es primo relativo a m . Entonces el inverso modular se puede encontrar directamente: $\fi$ ${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times ))$

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

En el caso especial donde m es primo y el inverso modular viene dado por ${\ estilo de visualización \ phi (m) = m-1}$

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

Este método es generalmente más lento que el algoritmo de Euclid extendido, pero a veces se usa si ya está disponible una implementación para la exponenciación modular. Desventajas de este método:

El valor debe conocerse y el método de cálculo más eficiente requiere m expansiones . La descomposición es bien conocida como un problema en el que el cálculo ocupa la mayor parte de la complejidad de la solución. Sin embargo, se puede calcular directamente si se conoce la descomposición en factores primos del número m . ${\ estilo de visualización \ phi (m)}$ ${\ estilo de visualización \ phi (m)}$
Costo relativamente alto de exponenciación. Aunque esto se puede hacer de manera más eficiente con la construcción modular , para valores grandes de m , el método del algoritmo de Montgomery es más eficiente . Este algoritmo en sí mismo requiere calcular el módulo inverso m . Sin el algoritmo de Montgomery, el algoritmo estándar de exponenciación binaria , que requiere módulo m en cada paso, es una operación lenta para m grande .

La notable ventaja 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 los criptosistemas de clave pública , puede protegerse de los ataques de canal lateral . Por esta razón, la implementación estándar de Curve25519 utiliza la técnica de cálculo del elemento inverso.

Cálculo de múltiples inversas

Es posible calcular los recíprocos de varios números módulo m utilizando un paso del algoritmo de Euclides y tres multiplicaciones para cada número de entrada adicional [12] . La idea básica es formar all , invertirlo y luego multiplicar por all , dejando solo . $ai}$ $ai}$ $a_{j}$ $j\neq i$ ${\displaystyle a_{i}^{-1))$

Algoritmo (toda la aritmética se hace módulo m ):

Calcule los productos de prefijo para todos . ${\textstyle b_{i}=\prod_{j=1}^{i}a_{j}=a_{i}b_{i-1))$ $i\leqslant n$
Calcula usando cualquier algoritmo disponible. ${\displaystyle b_{n}^{-1))$
Para i de n a 2 calculamos
- ${\displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1))$ y
- ${\displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i))$ .
Finalmente, . ${\displaystyle a_{1}^{-1}=b_{1}^{-1))$

Es posible implementar la multiplicación en forma de estructura de árbol, en lugar de lineal, para garantizar el paralelismo de los cálculos .

Aplicaciones

La búsqueda del inverso modular tiene muchas aplicaciones en algoritmos basados 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ápido y con menos requisitos de memoria, mientras que otras operaciones se vuelven más difíciles de realizar [13] . Ambas propiedades se pueden utilizar para el bien. En particular, en el algoritmo RSA , el cifrado y el proceso inverso de comunicación se realiza utilizando un par de números recíprocos entre sí en algún módulo cuidadosamente elegido. Uno de estos números se hace público y se puede utilizar en el procedimiento de cifrado rápido, mientras que el otro número se utiliza en el procedimiento de descifrado y no se divulga. Determinar una clave oculta de una pública se considera una tarea imposible, ya que su solución requiere más poder de cómputo que el que hay en la Tierra, lo que protege contra el acceso no autorizado [14] .

Como otro uso en un contexto diferente, considere el problema de división exacta en computadoras, donde se le da una lista de números impares del tamaño de una palabra de computadora, cada uno de los cuales es divisible por k , y necesita dividirlos por k . Una solución es la siguiente:

Usamos el algoritmo euclidiano extendido para calcular , el inverso modular de , donde w es igual al número de bits en la palabra. Este recíproco existe, ya que todos los números son impares y los residuos se consideran módulo, que no tiene divisores impares. $k^{{-1}}$ ${\displaystyle k{\pmod {2^{w))))$
Multiplicamos cada número de la lista por y seleccionamos los bits menos significativos del resultado (es decir, descartamos todos los bits fuera de la palabra de la computadora). $k^{{-1}}$

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 resultar en un aumento significativo de la velocidad. El primer paso es relativamente lento, pero solo debe realizarse una vez.

Los recíprocos modulares se utilizan para obtener una solución a un sistema de comparaciones lineales, lo cual está garantizado por el teorema chino del resto .

Por ejemplo, el sistema

{\begin{casos}X\equiv 4{\pmod {5}}\\X\equiv 4{\pmod {7}}\\X\equiv 6{\pmod {11}}\\\end {casos}}

tiene una solución general ya que 5, 7 y 11 son coprimos por pares . La solución viene dada por la fórmula

X=t_{1}(7\times 11)\times 4+t_{2}(5\times 11)\times 4+t_{3}(5\times 7)\times 6

dónde

{\ estilo de visualización t_ {1} = 3}

reverso modular ,

7\times 11{\pmod {5}}

{\ estilo de visualización t_ {2} = 6}

reverso modular ,

5\times 11{\pmod {7}}

{\ estilo de visualización t_ {3} = 6}

reversa modular .

5\times 7{\pmod {11}}

Después,

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

y en la forma dada

X\equiv 3504\equiv 39{\pmod {385}}

ya que 385 es el mínimo común múltiplo de 5, 7 y 11.

El inverso modular ocupa un lugar destacado en la definición de las sumas de Kloosterman .

Véase también

El método congruencial inverso es un algoritmo para generar números pseudoaleatorios que utiliza números inversos de módulo.
Recuperación de un número racional modulo it

Notas

↑ Rosen, 1993 , pág. 132.
↑ Schumacher, 1996 , pág. 88.
↑ Stinson, 1995 , pág. 124–128.
↑ Trappe, Washington, 2006 , pág. 164-169.
↑ Moriarty, K.; Kaliski, B.; Jonson, J.; Rusch, A. 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 (2016). Consultado el 21 de enero de 2017. Archivado desde el original el 12 de diciembre de 2018. (indefinido)
↑ A menudo se usan otras notaciones, incluidas [ a ] y [ a ] m .
↑ Irlanda, Rosen, 1990 , p. 32.
↑ Shoup, 2005 , pág. 15 Teorema 2.4.
↑ Rosen, 1993 , pág. 121.
↑ Irlanda, Rosen, 1990 , p. 31
↑ Koshy, 2007 , pág. 346.
↑ Brent, Zimmermann, 2010 , pág. 67–68.
↑ Trappe, Washington, 2006 , pág. 167.
↑ Trappe, Washington, 2006 , pág. 165.

Literatura

Douglas R. Stinson. Criptografía / Teoría y Práctica. - CRC Press, 1995. - ISBN 0-8493-8521-0 .
Tienda Víctor. Una introducción computacional a la teoría de números y al álgebra . - Prensa de la Universidad de Cambridge, 2005. - ISBN 9780521851541 .
Thomas Koshy. Teoría elemental de números con aplicaciones . — 2ª edición. - Prensa académica, 2007. - ISBN 978-0-12-372487-8 .
Richard P. Brent , Paul Zimmermann . §2.5.1 Varias inversiones a la vez // Teoría elemental de números con aplicaciones. Aritmética informática moderna . - Cambridge University Press, 2010. - V. 18. - (Monografías de Cambridge sobre Matemática Computacional y Aplicada). — ISBN 978-0-521-19469-3 .

Kenneth Irlanda, Michael Rosen. Una introducción clásica a la teoría de números moderna. — 2do. - Springer-Verlag, 1990. - ISBN 0-387-97329-X .
- C. Irlanda, M. Rosen. Introducción clásica a la teoría de números moderna / Traducido del inglés por S. P. Demushkin. - Moscú: Mir, 1987.

Kenneth H. Rosen. Teoría elemental de números y sus aplicaciones. — 3er. - Addison-Wesley, 1993. - ISBN 978-0-201-57889-8 .
Carol Schumacher. Capítulo Cero: Nociones Fundamentales de Matemática Abstracta . - Addison-Wesley, 1996. - ISBN 0-201-82653-4 .
Wade Trappe, Lawrence C. Washington. Introducción a la Criptografía con Teoría de Codificación. — 2do. - Prentice-Hall, 2006. - ISBN 978-0-13-186239-5 .

Enlaces

Weisstein, Eric W. Modular Inverse (inglés) en el sitio web de Wolfram MathWorld .
Guevara Vásquez, Fernando ofrece un ejemplo de cómo resolver el módulo inverso usando el algoritmo de Euclides.