Inverso multiplicativo (aritmética modular)

Inverso multiplicativo (aritmética modular)

El multiplicador modular inverso de un entero n módulo p es un entero m tal que

n-1 m (mod p)

Esto significa que es el inverso multiplicativo en el anillo de los enteros módulo p. Es equivalente a

mn 1 (mod p)

El multiplicador inverso 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 multiplicador modular inverso de n módulo p, se puede definir la operación de división entre n módulo p mediante la multiplicación por el inverso.

Contenido

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 division gracias a que m ( modulo) es la multiplicacion o la prueba de la division

)

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

Cálculo

Algoritmo Euclidiano Extendido

El multiplicador modular inverso 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,gcd(n,p)) tal que

xn + yp = \gcd(n,p)\,.

Si MCD(n,p)=1 entonces

xn \equiv 1 \pmod{p},

de donde x 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).


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 (\mathbb{Z}/p\mathbb{Z})^{*} 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 O(log(p)) operaciones modulares, de donde el tiempo de ejecución es O(log(p)3) cuando se usa el método escolar y O(log(p)2 log(log(p))log(log(log(p)))) cuando se usa la multiplicación basada en FFT de Strassen.

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.

Véase también


Wikimedia foundation. 2010.

См. также в других словарях:

  • Aritmética modular — Saltar a navegación, búsqueda Cubierta de la edición original de Disquisitiones arithmeticae de Gauss, libro fundamental de la aritmética modular. En matemática, la aritmética modular es un sistema aritmético para clases de equivalencia((Clase de …   Wikipedia Español

  • Inverso multiplicativo — Para otros usos de este término, véase Función recíproca. La función recíproca y = 1/x. Para cada valor de x (eje horizontal) excepto el 0, y (eje vertical) representa su inverso multiplicativo. En matemática, el inverso multiplicativo, recíproco …   Wikipedia Español

  • Multiplicador modular inverso — Saltar a navegación, búsqueda El multiplicador modular inverso de un entero n módulo p es un entero m tal que n 1 ≡ m (mod p) Esto significa que es el multiplicador inverso en el anillo de los enteros módulo p. Es equivalente a mn ≡ 1 (mod p) El… …   Wikipedia Español

  • Algoritmo de Euclides — El algoritmo de Euclides es un método antiguo y eficaz para calcular el máximo común divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos. El algoritmo de Euclides extendido es una ligera modificación que permite además… …   Wikipedia Español

  • Teorema de Wilson — En matemáticas, el teorema de Wilson es un teorema clásico relacionado con la divisibilidad. Se enuncia de la siguiente manera: Si p es un número primo, entonces (p − 1)!+1 ≡ 0 (mod p) John Wilson El recíproco también es cierto, por lo que puede… …   Wikipedia Español

  • Cuerpo (matemática) — Saltar a navegación, búsqueda Para otros usos de este término, véase Cuerpo. Un cuerpo o campo es un anillo de división conmutativo, es decir, un anillo conmutativo en el que todo elemento distinto de cero (todo elemento no nulo) es invertible… …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»