Inverso multiplicativo 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

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

que es la forma abreviada de escribir la afirmación de que $m$ divide (exactamente) la cantidad $ax - 1$ , o, dicho de otro modo, 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 ${\overline {w}}$ 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 ${\overline {a}}$ es la clase de congruencia ${\overline {x}}$ de tal manera que:

{\overline {a}}\cdot {\overline {x}}={\overline {1}},

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

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

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 ]} Una ventaja 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,

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

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

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

Una congruencia lineal es una congruencia modular de la forma

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

A diferencia de las ecuaciones lineales sobre los 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 ${\overline {x}}$ también es una solución, por lo que, cuando hablamos del número de soluciones de una congruencia lineal nos referimos al número de diferentes clases de congruencia que contienen soluciones.

Si $d$ es el máximo común divisor de $a$ y $m,$ entonces la congruencia lineal $ax \equiv b (mod m)$ tiene soluciones si y solo 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.

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

El resultado anterior indica que existe una solución si y solo si $mcd(a, m) = 1$ , es decir, $a$ y $m$ deben ser primos relativos (es decir, coprimos). Además, cuando se cumple esta condición, existe 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$ con respecto al módulo $m$ , entonces

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

por lo tanto

a(bb')\equiv 0{\pmod {m}}.

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

Cuando $ax \equiv 1 (mod m)$ tiene una solución, a menudo se denota de esta manera −

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 $a$ (que, a diferencia del inverso multiplicativo modular, no es un número entero excepto cuando $a$ es 1 o −1). La notación sería apropiada si $a$ se interpreta como un token que representa la clase de congruencia. ${\overline {a}}$ , 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 los enteros en $m$ clases de congruencia. Las operaciones de suma y multiplicación se pueden definir sobre estos $m$ objetos de la siguiente manera: Para sumar o multiplicar dos clases de congruencia, primero se elige un representante (de cualquier forma) de cada clase, luego se realiza la operación habitual para enteros sobre los dos representantes y finalmente se toma la clase de congruencia a la que pertenece el resultado de la operación con enteros como resultado de la operación sobre las clases de congruencia. En símbolos, estas definiciones son:

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

y

{\overline {a}}\cdot {\overline {b}}={\overline {ab}},

dónde $+$ y $\,\!\cdot$ A la izquierda se representan la suma y la multiplicación de clases de congruencia módulo $m$ . Estas operaciones están bien definidas , lo que significa que el resultado final no depende de la elección de los representantes utilizados para obtenerlo.

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

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 dividirse por $m$ . Cualquier conjunto de $m$ enteros seleccionados de manera 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 enteros ${0, 1, 2, ..., m - 1}$ forma un sistema completo de residuos módulo $m$ , conocido como el sistema de mínimos residuos 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 conveniente el punto de vista de las clases de congruencia del anillo. $\mathbb {Z} /m\mathbb {Z}$ 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 no lo tiene si $m > 1.$ Después de eliminar los elementos de un sistema de residuos completo que no son primos relativos con $m$ , lo que queda se llama un sistema de residuos reducido , cuyos elementos tienen inversos multiplicativos modulares. El número de elementos en un sistema de residuos reducido es $\phi (m)$ , dónde $\phi$ es la función totiente de Euler , es decir, el número de enteros positivos menores que $m$ que son primos relativos con $m$ .

En un anillo general con unidad, no todos los elementos tienen un inverso multiplicativo y aquellos que sí 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 \times$ si $R$ es el nombre del anillo. El grupo de unidades del anillo de enteros módulo $m$ se llama grupo multiplicativo de enteros módulo $m$ , y es isomorfo a un sistema de residuos reducido. En particular, tiene orden (tamaño), $\phi (m)$ .

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

Ejemplo

Para cualquier número entero $n>1$ , siempre es así que $n^{2}-n+1$ es el inverso multiplicativo modular de $n+1$ con respecto al módulo $n^{2}$ , desde $(n+1)(n^{2}-n+1)=n^{3}+1$ . Ejemplos son $3\times 3\equiv 1{\pmod {4}}$ , $4\times 7\equiv 1{\pmod {9}}$ , $5\times 13\equiv 1{\pmod {16}}$ etcétera.

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

32\equiv 2{\pmod {10}}

puesto que 10 divide a 32 − 2 = 30, y

111\equiv 1{\pmod {10}}

ya que 10 divide a 111 − 1 = 110.

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

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

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

{\overline {5}}=\{\cdots ,-15,-5,5,15,25,\cdots \}

y

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

La congruencia lineal $4 x \equiv 5 (mod 10)$ no tiene soluciones ya que los enteros que son congruentes con 5 (es decir, aquellos en ${\overline {5}}$ $Todos los mcd$ son impares, mientras que $4x$ $siempre$ es par. Sin embargo, la congruencia lineal $4x \equiv 6 (mod 10)$ tiene dos soluciones: $x = 4$ y $x = 9.$ El $mcd(4, 10) = 2$ y 2 no divide a 5, pero sí divide a 6.

Dado que $mcd(3, 10) = 1$ , la congruencia lineal $3 x \equiv 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 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 en ${\overline {7}}$ satisfarán la congruencia ya que estos enteros tienen la forma $7 + 10 r$ para algún entero $r$ y

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

es divisible por 10. Esta congruencia solo tiene 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, los cuales se presentarán en la siguiente sección.

El producto de clases de congruencia ${\overline {5}}$ y ${\overline {8}}$ se puede obtener seleccionando un elemento de ${\overline {5}}$ , digamos 25, y un elemento de ${\overline {8}}$ , digamos −2, y observando que su producto (25)(−2) = −50 está en la clase de congruencia ${\overline {0}}$ . De este modo, ${\overline {5}}\cdot {\overline {8}}={\overline {0}}$ . 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 enteros módulo 10, es decir, $\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ínimos módulo 10 es {0, 1, 2, ..., 9}. Un sistema de residuos reducidos módulo 10 podría ser {1, 3, 7, 9}. El producto de cualesquiera dos clases de congruencia 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 como generador (multiplicativo) 3 o 7. Las clases de congruencia representadas forman el grupo de unidades del anillo. $\mathbb {Z} /10\mathbb {Z}$ Estas clases de congruencia son precisamente las que tienen inversos multiplicativos 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 euclidiano determina el máximo común divisor (mcd) de dos enteros, digamos $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 con este mcd. En otras palabras, se pueden encontrar enteros $x$ $e y$ que satisfacen la identidad de Bézout .

ax+my=\gcd(a,m)=1.

Reescrito, esto es

ax-1=(-y)m,

eso es,

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

Así pues, se ha calculado el 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 tiempo $O(log₂ (m))$ , suponiendo $| a | < m$ , y se considera muy rápido y, en general, más eficiente que su alternativa, la exponenciación.

Por ejemplo, un inverso multiplicativo modular de $a=15$ con respecto al módulo $m=34$ es $-9$ pero también $-9+34=25,$ es decir, en el anillo $\mathbb {Z} /34\mathbb {Z} ,$ la clase de residuos ${\overline {15}}$ es invertible con el inverso

{\overline {15}}^{\!\ -1}={\overline {-9}}={\overline {25}}.

Porque

g=\mathrm {gcd} (m,a)=1=4m-9a,

según el cálculo adyacente. En el primer paso, correspondiente a la división euclidiana " $\;\!34\div 15$ es $2$ con el resto $4\!\$ ", $-2$ ecuación de veces $15=0m+1a$ se añade a la ecuación $34=1m+0a$ , lo que conduce a $4=1m-2a.$ Tan pronto como un resto a la izquierda es $0,$ $g$ se sitúa por encima de él (o generalmente $\pm g$ si también se permiten restos negativos). En la tabla correspondiente del extremo derecho con las operaciones de fila análogas, aparentemente se podría omitir la $m$ -columna. Finalmente, ${\overline {15}}{}^{\!\ -1}={\overline {-9}}$ se puede comprobar directamente:

{\overline {15}}\cdot {\overline {-9}}={\overline {-135}}={\overline {-135+4\cdot 34}}={\overline {1}}

en $\mathbb {Z} /34\mathbb {Z} .$

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 con $m$ , es decir, $mcd(a, m) = 1$ , entonces

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

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

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

En el caso especial en que $m$ es un número primo, $\phi (m)=m-1$ y una inversa modular viene dada por

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 $\phi (m)$ 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 computacionalmente difícil. Sin embargo, calcular $\phi (m)$ es sencillo cuando se conoce la factorización prima de $m .$
El costo relativo de la exponenciación. Si bien puede implementarse de manera más eficiente mediante la exponenciación modular , cuando se trata de valores grandes de $m , el método$ de reducción de Montgomery permite un cálculo más eficiente . Este método, a su vez, requiere una inversa modular módulo $m$ , que es precisamente lo que se debía calcular inicialmente. Sin el método de Montgomery, la exponenciación binaria estándar , que requiere una división módulo $m$ en cada paso, resulta una operación lenta cuando $m$ es grande.

Una ventaja notable de esta técnica es que no existen 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 ataques de canal lateral . Por esta razón, la implementación estándar de Curve25519 utiliza esta técnica para calcular una inversa.

Múltiples inversas

Es posible calcular el inverso de varios números $a i$ , módulo un $m$ común , con una sola invocación del algoritmo euclidiano y tres multiplicaciones por cada entrada adicional. ^{[ 12 ]} La idea básica es formar el producto de todos los $a i$ , invertirlo y luego multiplicarlo por $a j$ para todo $j \neq i$ para dejar solo el $a -1 i$ deseado .

Más específicamente, el algoritmo es (todas las operaciones aritméticas se realizan módulo $m$ ):

Calcular los productos de prefijo ${\textstyle b_{i}=\prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ para todo $i \leq n$ .
Calcula $b -1 n$ utilizando cualquier algoritmo disponible.
Para i desde n hasta 2, calcule
- $a -1 i = b -1 i b i -1$ y
- $b -1 i -1 = b -1 i a i$ .
Finalmente, $a -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 .

Inversos módulo potencias primas (incluidas las potencias de 2)

En el caso en que el módulo $M$ esté en la forma $p^{m}$ Para algún número primo $p$ y entero positivo $m$ , es posible calcular inversas multiplicativas modulares de manera eficiente utilizando la iteración de Newton-Raphson, lo que permite calcular la inversa con $O(\log m)$ multiplicaciones. Se puede demostrar que si

ax\equiv 1{\pmod {p^{k}}}

(es decir, $x$ es un inverso multiplicativo modular de $un$ módulo alguna potencia prima) $p^{k}$ ), entonces

ax\left(2-ax\right)\equiv 1{\pmod {p^{2k}}}

lo que significa que es posible realizar un cálculo de inverso modular calculando primero el inverso multiplicativo modular de $a$ módulo el número primo $p$ o una pequeña potencia del mismo, y luego realizando una serie de iteraciones de Newton-Raphson para calcular el inverso módulo potencias primas progresivamente mayores. $p^{2^{n}*k}$ $para valores de n$ progresivamente mayores . ^{[ 13 ]}^{[ 14 ]}

Un uso práctico de este método es calcular eficientemente los inversos multiplicativos modulares módulo potencias de 2. Para tal cálculo, se podría comenzar observando que todos los enteros impares son sus propios inversos multiplicativos modulares módulo 2. $2^{3}$ , como puede demostrarse mediante inspección:

$1*1=1\equiv 1{\pmod {8}}$ , $3*3=9\equiv 1{\pmod {8}}$ , $5*5=25\equiv 1{\pmod {8}}$ , $7*7=49\equiv 1{\pmod {8}}$ ,

y luego usar iterativamente iterativamente las iteraciones de Newton-Raphson para calcular el inverso modular módulo $2^{6}$ , $2^{12}$ , $2^{24}$ etcétera.

Por ejemplo, en el lenguaje de programación C , donde las sumas, restas y multiplicaciones en el uint64_ttipo de datos se realizan todas módulo $2^{64}$ , se podría calcular el inverso multiplicativo modular de un entero impar $a$ módulo $2^{64}$ utilizando la siguiente función que realiza cinco iteraciones de Newton-Raphson:

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { uint64_t x = a ; for ( int i = 0 ; i < 5 ; i ++ ) x *= 2 - a * x ; return x ; }

Dependiendo de la aplicación y la plataforma, puede tener sentido optimizar aún más esta rutina; por ejemplo, las primeras iteraciones se pueden omitir usando una tabla de búsqueda para proporcionar un módulo inverso una potencia de 2 mayor; además, en algunos sistemas, las multiplicaciones de 32 bits pueden ser más rápidas que las de 64 bits, en cuyo caso se puede obtener alguna mejora de velocidad usando solo multiplicaciones de 32 bits hasta que un módulo inverso $2^{32}$ se ha obtenido y luego cambia a multiplicaciones de 64 bits solo después de eso. Aplicando tales optimizaciones, una rutina C que calcula un inverso multiplicativo modular módulo $2^{64}$ se convierte en:

#include <stdint.h> uint64_t modinv64 ( uint64_t a ) { static const uint8_t tbl [ 256 ] = { 0 , 1 , 0 , 171 , 0 , 205 , 0 , 183 , 0 , 57 , 0 , 163 , 0 , 197 , 0 , 239 , 0 , 241 , 0 , 27 , 0 , 61 , 0 , 167 , 0 , 41 , 0 , 19 , 0 , 53 , 0 , 223 , 0 , 225 , 0 , 139 , 0 , 173 , 0 , 151 , 0 , 25 , 0 , 131 , 0 , 165 , 0 , 207 , 0 , 209 , 0 , 251 , 0 , 29 , 0 , 135 , 0 , 9 , 0 , 243 , 0 , 21 , 0 , 191 , 0 , 193 , 0 , 107 , 0 , 141 , 0 , 119 , 0 , 249 , 0 , 99 , 0 , 133 , 0 , 175 , 0 , 177 , 0 , 219 , 0 , 253 , 0 , 103 , 0 , 233 , 0 , 211 , 0 ,245 , 0 , 159 , 0 , 161 , 0 , 75 , 0 , 109 , 0 , 87 , 0 , 217 , 0 , 67 , 0 , 101 , 0 , 143 , 0 , 145 , 0 , 187 , 0 , 221 , 0 , 71 , 0 , 201 , 0 , 179 , 0 , 213 , 0 , 127 , 0 , 129 , 0 , 43 , 0 , 77 , 0 , 55 , 0 , 185 , 0 , 35 , 0 , 69 , 0 , 111 , 0 , 113 , 0 , 155 , 0 , 189 , 0 , 39 , 0 , 169 , 0 , 147 , 0 , 181 , 0 , 95 , 0 , 97 , 0 , 11 , 0 , 45 , 0 , 23 , 0 , 153 , 0 , 3 , 0 , 37 , 0 , 79 , 0 , 81 , 0 , 123 , 0 , 157 , 0 , 7 , 0 , 137 , 0 , 115 , 0 , 149 , 0 , 63 , 0 , 65 , 0 , 235 , 0 ,13 , 0 , 247 , 0 , 121 , 0 , 227 , 0 , 5 , 0 , 47 , 0 , 49 , 0 , 91 , 0 , 125 , 0 , 231 , 0 , 105 , 0 , 83 , 0 , 117 , 0 , 31 , 0 , 33 , 0 , 203 , 0 , 237 , 0 , 215 , 0 , 89 , 0 , 195 , 0 , 229 , 0 , 15 , 0 , 17 , 0 , 59 , 0 , 93 , 0 , 199 , 0 , 73 , 0 , 51 , 0 , 85 , 0 , 255 }; uint32_t a32 = ( uint32_t ) a ; uint32_t x = tbl [ a & 0xFF ]; // módulo inverso 2^8 x *= 2 - a32 * x ; // multiplicaciones de 32 bits x *= 2 - a32 * x ; // multiplicaciones de 32 bits return x * ( 2 - a * x ); // multiplicaciones de 64 bits }

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 realizar algunas operaciones más rápidamente y con menos requisitos de almacenamiento, mientras que otras se vuelven más difíciles. ^{[ 15 ]} Ambas características pueden aprovecharse. 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 puede usarse 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. ^{[ 16 ]}

Como otro ejemplo en un contexto diferente, consideremos el problema de la división exacta en informática, donde tenemos una lista de números impares de tamaño palabra, cada uno divisible por $k$ , y deseamos 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. Este inverso 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, sobre todo en aquellas sin soporte de hardware para la división, esta operación es más lenta que la multiplicación, por lo que este método puede acelerar considerablemente el proceso. 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 Chino del Resto .

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 dos a dos . 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).

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 (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 .

Véase también

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

Notas

↑ Rosen 1993 , pág. 132 .
↑ Schumacher 1996 , pág. 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 . IETF . sec. 2.2. doi : 10.17487/RFC8017 . RFC 8017. Consultado el 21 de enero de 2017 .
↑ A menudo se utilizan otras notaciones, incluidas $[a]$ y $[a] m$ .
↑ Ireland y Rosen 1990 , pág. 32
↑ Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra , Cambridge University Press, Teorema 2.4, pág. 15, ISBN 9780521851541
↑ Rosen 1993 , pág. 121
↑ Ireland y Rosen 1990 , pág. 31
↑ Thomas Koshy. Teoría elemental de números con aplicaciones , 2.ª edición. ISBN 978-0-12-372487-8Pág. 346.
↑ Brent, Richard P .; Zimmermann, Paul (diciembre de 2010). «§2.5.1 Varias inversiones a la vez» (PDF) . Modern Computer Arithmetic . Cambridge Monographs on Computational and Applied Mathematics. Vol. 18. Cambridge University Press. pp. 67–68 . ISBN 978-0-521-19469-3.
↑ Jean-Guillaume Dumas, Sobre la iteración de Newton-Raphson para inversos multiplicativos módulo potencias primas , 22 de abril de 2019, pág. 6
↑ Cryptography StackExchange, ¿Cómo determinar el inverso multiplicativo módulo 64 (u otra potencia de dos)? , 17 de mayo de 2017.
↑ Trappe y Washington 2006 , pág. 167
↑ Trappe y Washington 2006 , pág. 165

Referencias

Ireland, Kenneth; Rosen, Michael (1990), Introducción clásica a la teoría moderna de números (2.ª ed.), Springer-Verlag, ISBN 0-387-97329-X
Rosen, Kenneth H. (1993), Teoría elemental de números 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 la codificación (2.ª ed.), Prentice-Hall, ISBN 978-0-13-186239-5

Enlaces externos

Weisstein, Eric W. "Inversa modular" . MundoMatemático .
Guevara Vásquez, Fernando proporciona un ejemplo resuelto de cómo calcular el inverso multiplicativo módulo utilizando el algoritmo de Euclides.
El inverso multiplicativo entero mediante el método de Newton proporciona algoritmos rápidos para calcular inversos multiplicativos módulo potencias de 2.

[Rosen132-1] Rosen 1993 , pág. 132 .

[:1-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 . IETF . 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] Ireland y Rosen 1990 , pág. 32

[8] Shoup, Victor (2005), A Computational Introduction to Number Theory and Algebra , Cambridge University Press, Teorema 2.4, pág. 15, ISBN 9780521851541

[9] Rosen 1993 , pág. 121

[10] Ireland 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-8Pág. 346.

[12] Brent, Richard P .; Zimmermann, Paul (diciembre de 2010). «§2.5.1 Varias inversiones a la vez» (PDF) . Modern Computer Arithmetic . Cambridge Monographs on Computational and Applied Mathematics. Vol. 18. Cambridge University Press. pp. 67–68 . ISBN 978-0-521-19469-3.

[13] Jean-Guillaume Dumas, Sobre la iteración de Newton-Raphson para inversos multiplicativos módulo potencias primas , 22 de abril de 2019, pág. 6

[14] Cryptography StackExchange, ¿Cómo determinar el inverso multiplicativo módulo 64 (u otra potencia de dos)? , 17 de mayo de 2017.

[15] Trappe y Washington 2006 , pág. 167

[16] Trappe y Washington 2006 , pág. 165

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]