fbpx
Wikipedia

Inverso multiplicativo (aritmética modular)

En la aritmética modular, el inverso multiplicativo de un número entero n módulo p es otro entero m (módulo p) tal que el producto mn es congruente con 1 (módulo p). Esto significa que tal número m es el inverso multiplicativo en el anillo de los enteros módulo p, es decir, n-1 m (mod p). Se habla de inverso multiplicativo para distinguirlo del elemento inverso, tal y como es entendido en teoría de grupos.

El inverso multiplicativo de n módulo p existe si y sólo si n y p son coprimos, es decir, si mcd(n, p)=1. Si existe el inverso multiplicativo de un número n módulo p, entonces se puede definir la operación de división de cualquier otro número entre n módulo p, mediante la multiplicación de ese número por el inverso n-1. Si p es un número primo, entonces todos los números excepto el cero (y sus congruentes —los múltiplos de p) son invertibles, lo que convierte al anillo de los enteros módulo p en un cuerpo.

Explicación

A veces se pueden encontrar muchos valores de m para los cuales sea cierta esta congruencia. El m seleccionado como multiplicador modular inverso es generalmente el natural más pequeño posible (o simplemente el que sea miembro del conjunto Zn en el que n sea el módulo).

Por ejemplo:

la división gracias a que m (módulo) es la multiplicación o la prueba de la división

nos da

3m 1 (mod 11)

El m más pequeño que resuelve esta congruencia es 4; así pues, el multiplicador modular inverso de 3 (mod 11) es 4. Sin embargo, otro m que resuelve la congruencia es 15 (fácilmente determinable sumando p al inverso obtenido).[1]

Cálculo

Algoritmo Euclidiano Extendido

El inverso multiplicativo de n módulo p se puede obtener mediante el Algoritmo de Euclides. En particular, invocando el algoritmo extendido de Euclides con n y p como argumentos se obtiene una tripla (x,y,mcd(n,p)) tal que

 

Si MCD(n,p)=1 entonces

 

de donde   es el inverso modular de n módulo p. Si el MCD(n,p)≠ 1 entonces no existe el modular inverso. Este algoritmo se ejecuta en un tiempo O(log(p)2) (asumiendo que |n|<p).

Ejemplo

Por ejemplo, supongamos que queremos calcular el inverso de 117 módulo 244. Por tanto con nuestra nomenclatura (n módulo p), p=244 y n=117 Lo primero que hacemos es aplicar el algoritmo de Euclides para verificar que mcd(n,p)=1. Posteriormente aprovechamos los pasos intermedios para hallar el mcd(n,p) en términos de n y p y así obtener el inverso de n que notaremos por n-1.

  • Paso 1:Como |n| < p entonces podemos expresar p como p=qn+r. Es decir 244=2*117+10
  • Paso 2:Como 117>10 entonces 117=11*10+7
  • Paso 3:Como 10>7 entonces 10=1*7+3
  • Paso 4:Como 7>3 entonces 7=2*3+1
  • Paso 5:Como 3>1 entonces 3=1*3+0

De esta forma demostramos que mcd(244,117)=1

  • Paso 6: Del paso 4 despejo el resto (el número que queda a la derecha de la suma), quedando 1=7-3*2
  • Paso 7: Del paso 3 despejo el resto quedando 3=10-1*7. Si sustituimos en la ecuación del paso 6 tenemos 1=7-(10-1*7)*2=-2*10+3*7
  • Paso 8: Del paso 2 despejo el resto quedando 7=117-11*10. Si sustituimos en la ecuación del paso 7 tenemos 1=-2*10+3(117-11*10)=3*117-35*10
  • Paso 9: Del paso 1 despejo el resto quedando 10=244-2*117. Si sustituimos en la ecuación del paso 8 obtenemos 1=3*117-35*(244-2*117)=-35*244+73*117. De esta ecuación podemos decir que n-1=73 que es lo que queríamos calcular.
  • Paso 10: Si n-1 es negativo, el inverso n-1 se recalcula como n-1 + p.

Exponenciación Modular Directa

El método de exponenciación modular directa como alternativa al algoritmo euclidiano extendido es el siguiente:

De acuerdo con el Teorema de Euler, si n es coprimo con p, es decir, MCD(n,p)=1, entonces,

nφ(p) 1 (mod p)

Esto se deduce del Teorema de Lagrange y del hecho de que n pertenece al grupo multiplicativo de enteros módulo n   si y sólo si n es coprimo con p.

Así pues,

nφ(p)-1 n-1 (mod p)

donde φ(p) es la Función φ de Euler.

De esta forma se puede obtener el multiplicador modular inverso de n módulo p de forma directa:

nφ(p)-1 m (mod p)

En el caso especial en que p es primo,

φ(p) = p - 1

Se puede usar la Exponenciación binaria para ejecutar este método de forma eficiente para lo cual se requieren solamente O(log(p)) operaciones modulares.

Si se utiliza el método escolar tradicional, el tiempo de ejecución es O(log(p)3).

Cuando se usa la multiplicación basada en FFT de Strassen, el tiempo de ejecución es O(log(p)2 log(log(p))log(log(log(p)))). Este método es generalmente más lento que el algoritmo euclidiano extendido pero se usa a veces cuando ya existe una implementación de la exponenciación modular. Una desventaja de este método es que necesita φ(p) porque la única forma de computación eficiente requiere el conocimiento de los factores de p.

Implementación en C

//Calculador de inversos modulares (CIM) //Uso: cim a m //El programa (cim) hallará b siendo esta expresión: (a * b)(mod m) = 1 . //Si al ejecutarse no muestra nada, el 'a' introducido no tiene inverso para ese módulo ('m'). #include <stdio.h> #include <stdlib.h> int main(int argc, char** argv) { if(argc == 1)exit(-1); int b, //Almacena el valor de b en (a * b)(mod m) x, //Almacena el resultado de la op. a = atoi(argv[1]), //Almacena a m = atoi(argv[2]); //Almacena m for(b = 0; b < m; b++) { x = (a * b) % m; if(x == 1)  printf("%i", b); } return 0; } 

Implementación en Java

 /* CREADO POR JLCY 17-1-2016  APLICANDO EL LEMA DE BEZOUT SE CONSIGUE LLEGAR AL MCD DE "a" Y "p" COMO UNA COMBINACION LINEAL DE "a" y "p" CON EL ALGORITMO DE EUCLIDES. YA CON ESTO SI EL MCD ES 1 , "a" y "p" son primos relativos y existe el inverso de "a" modulo "m" ESTA SOLUCION ES MAS OPTIMA YA QUE NO PARA SOBRE TODOS LOS POSIBLES INVERSOS  */ public void obtenerInverso(int a,int m) { int c1 = 1; int c2 = -(m/a); //coeficiente de a y b respectivamente int t1 = 0; int t2 = 1; //coeficientes penultima corrida int r = m % a; //residuo, asignamos 1 como condicion de entrada  int x=a,y=r,c; while(r!=0) { c = x/y;//cociente r = x%y;//residuo //guardamos valores temporales de los coeficientes //multiplicamos los coeficiente por -1*cociente de la division c1*=-c; c2*=-c; //sumamos la corrida anterior c1+=t1; c2+=t2; //actualizamos corrida anterior t1=-(c1-t1)/c; t2=-(c2-t2)/c; x=y; y=r; } if(x==1)//residuo anterior es 1 , son primos relativos y el inverso existe  System.out.println(""+t2); else  System.out.println("No hay inverso"); } 

Véase también

Referencias

  1. «Inverso multiplicativo modular». Consultado el 14 de febrero de 2021. 

Enlaces externos

  •   Datos: Q2741788

inverso, multiplicativo, aritmética, modular, este, artículo, sección, sobre, matemáticas, necesita, wikificado, favor, edítalo, para, cumpla, convenciones, estilo, este, aviso, puesto, abril, 2011, aritmética, modular, inverso, multiplicativo, número, entero,. Este articulo o seccion sobre matematicas necesita ser wikificado por favor editalo para que cumpla con las convenciones de estilo Este aviso fue puesto el 16 de abril de 2011 En la aritmetica modular el inverso multiplicativo de un numero entero n modulo p es otro entero m modulo p tal que el producto mn es congruente con 1 modulo p Esto significa que tal numero m es el inverso multiplicativo en el anillo de los enteros modulo p es decir n 1 m mod p Se habla de inverso multiplicativo para distinguirlo del elemento inverso tal y como es entendido en teoria de grupos El inverso multiplicativo de n modulo p existe si y solo si n y p son coprimos es decir si mcd n p 1 Si existe el inverso multiplicativo de un numero n modulo p entonces se puede definir la operacion de division de cualquier otro numero entre n modulo p mediante la multiplicacion de ese numero por el inverso n 1 Si p es un numero primo entonces todos los numeros excepto el cero y sus congruentes los multiplos de p son invertibles lo que convierte al anillo de los enteros modulo p en un cuerpo Indice 1 Explicacion 2 Calculo 2 1 Algoritmo Euclidiano Extendido 2 1 1 Ejemplo 2 2 Exponenciacion Modular Directa 3 Implementacion en C 4 Implementacion en Java 5 Vease tambien 6 Referencias 7 Enlaces externosExplicacion EditarA veces se pueden encontrar muchos valores de m para los cuales sea cierta esta congruencia El m seleccionado como multiplicador modular inverso es generalmente el natural mas pequeno posible o simplemente el que sea miembro del conjunto Zn en el que n sea el modulo Por ejemplo la division gracias a que m modulo es la multiplicacion o la prueba de la divisionnos da 3m 1 mod 11 El m mas pequeno que resuelve esta congruencia es 4 asi pues el multiplicador modular inverso de 3 mod 11 es 4 Sin embargo otro m que resuelve la congruencia es 15 facilmente determinable sumando p al inverso obtenido 1 Calculo EditarAlgoritmo Euclidiano Extendido Editar El inverso multiplicativo de n modulo p se puede obtener mediante el Algoritmo de Euclides En particular invocando el algoritmo extendido de Euclides con n y p como argumentos se obtiene una tripla x y mcd n p tal que x n y p m c d n p displaystyle xn yp mcd n p Si MCD n p 1 entonces x n 1 mod p displaystyle xn equiv 1 pmod p de donde x displaystyle x es el inverso modular de n modulo p Si el MCD n p 1 entonces no existe el modular inverso Este algoritmo se ejecuta en un tiempo O log p 2 asumiendo que n lt p Ejemplo Editar Por ejemplo supongamos que queremos calcular el inverso de 117 modulo 244 Por tanto con nuestra nomenclatura n modulo p p 244 y n 117 Lo primero que hacemos es aplicar el algoritmo de Euclides para verificar que mcd n p 1 Posteriormente aprovechamos los pasos intermedios para hallar el mcd n p en terminos de n y p y asi obtener el inverso de n que notaremos por n 1 Paso 1 Como n lt p entonces podemos expresar p como p qn r Es decir 244 2 117 10 Paso 2 Como 117 gt 10 entonces 117 11 10 7 Paso 3 Como 10 gt 7 entonces 10 1 7 3 Paso 4 Como 7 gt 3 entonces 7 2 3 1 Paso 5 Como 3 gt 1 entonces 3 1 3 0De esta forma demostramos que mcd 244 117 1 Paso 6 Del paso 4 despejo el resto el numero que queda a la derecha de la suma quedando 1 7 3 2 Paso 7 Del paso 3 despejo el resto quedando 3 10 1 7 Si sustituimos en la ecuacion del paso 6 tenemos 1 7 10 1 7 2 2 10 3 7 Paso 8 Del paso 2 despejo el resto quedando 7 117 11 10 Si sustituimos en la ecuacion del paso 7 tenemos 1 2 10 3 117 11 10 3 117 35 10 Paso 9 Del paso 1 despejo el resto quedando 10 244 2 117 Si sustituimos en la ecuacion del paso 8 obtenemos 1 3 117 35 244 2 117 35 244 73 117 De esta ecuacion podemos decir que n 1 73 que es lo que queriamos calcular Paso 10 Si n 1 es negativo el inverso n 1 se recalcula como n 1 p Exponenciacion Modular Directa Editar El metodo de exponenciacion modular directa como alternativa al algoritmo euclidiano extendido es el siguiente De acuerdo con el Teorema de Euler si n es coprimo con p es decir MCD n p 1 entonces nf p 1 mod p Esto se deduce del Teorema de Lagrange y del hecho de que n pertenece al grupo multiplicativo de enteros modulo n Z p Z displaystyle mathbb Z p mathbb Z si y solo si n es coprimo con p Asi pues nf p 1 n 1 mod p donde f p es la Funcion f de Euler De esta forma se puede obtener el multiplicador modular inverso de n modulo p de forma directa nf p 1 m mod p En el caso especial en que p es primo f p p 1Se puede usar la Exponenciacion binaria para ejecutar este metodo de forma eficiente para lo cual se requieren solamente O log p operaciones modulares Si se utiliza el metodo escolar tradicional el tiempo de ejecucion es O log p 3 Cuando se usa la multiplicacion basada en FFT de Strassen el tiempo de ejecucion es O log p 2 log log p log log log p Este metodo es generalmente mas lento que el algoritmo euclidiano extendido pero se usa a veces cuando ya existe una implementacion de la exponenciacion modular Una desventaja de este metodo es que necesita f p porque la unica forma de computacion eficiente requiere el conocimiento de los factores de p Implementacion en C Editar Calculador de inversos modulares CIM Uso cim a m El programa cim hallara b siendo esta expresion a b mod m 1 Si al ejecutarse no muestra nada el a introducido no tiene inverso para ese modulo m include lt stdio h gt include lt stdlib h gt int main int argc char argv if argc 1 exit 1 int b Almacena el valor de b en a b mod m x Almacena el resultado de la op a atoi argv 1 Almacena a m atoi argv 2 Almacena m for b 0 b lt m b x a b m if x 1 printf i b return 0 Implementacion en Java Editar CREADO POR JLCY 17 1 2016 APLICANDO EL LEMA DE BEZOUT SE CONSIGUE LLEGAR AL MCD DE a Y p COMO UNA COMBINACION LINEAL DE a y p CON EL ALGORITMO DE EUCLIDES YA CON ESTO SI EL MCD ES 1 a y p son primos relativos y existe el inverso de a modulo m ESTA SOLUCION ES MAS OPTIMA YA QUE NO PARA SOBRE TODOS LOS POSIBLES INVERSOS public void obtenerInverso int a int m int c1 1 int c2 m a coeficiente de a y b respectivamente int t1 0 int t2 1 coeficientes penultima corrida int r m a residuo asignamos 1 como condicion de entrada int x a y r c while r 0 c x y cociente r x y residuo guardamos valores temporales de los coeficientes multiplicamos los coeficiente por 1 cociente de la division c1 c c2 c sumamos la corrida anterior c1 t1 c2 t2 actualizamos corrida anterior t1 c1 t1 c t2 c2 t2 c x y y r if x 1 residuo anterior es 1 son primos relativos y el inverso existe System out println t2 else System out println No hay inverso Vease tambien EditarGenerador inversivo congruente Aritmetica modular Teoria de numeros Criptografia de clave publicaReferencias Editar Inverso multiplicativo modular Consultado el 14 de febrero de 2021 Enlaces externos EditarWeisstein Eric W Modular Inverse En Weisstein Eric W ed MathWorld en ingles Wolfram Research Datos Q2741788Obtenido de https es wikipedia org w index php title Inverso multiplicativo aritmetica modular amp oldid 133211834, wikipedia, wiki, leyendo, leer, libro, biblioteca,

español

, española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos