Invers multiplicativo (aritmètica modular)

En l'aritmètica modular, el invers multiplicativo d'un número sancer n mòdul p és un atre sancer m (mòdul p) tal que el producte mn és congruent en 1 (mòdul p). Açò significa que tal número m és l'invers multiplicativo en l'anell dels sancers mòdul p, és dir, n^-1 ≡ m (mod p). Es parla d'invers multiplicativo per a distinguir-ho del element invers, tal i com és entés en teoria de grups.

L'invers multiplicativo de n mòdul p existix si i solament si n i p són coprimos, és dir, si mcd(n, p)=1. Si existix l'invers multiplicativo d'un número n mòdul p, llavors es pot definir l'operació de divisió de qualsevol atre número entre n mòdul p, per mig de la multiplicació d'eixe número per l'invers n^-1. Si p és un número primo, llavors tots els números llevat el zero (i els seus congruents —els múltiples de p) són invertibles, lo que convertix a l'anell dels sancers mòdul p en un cos.

Explicació

A voltes es poden trobar molts valors de m per als quals siga certa esta congruència. El m seleccionat com a multiplicador modular invers és generalment el natural més chicotet possible (o simplement el que siga membre del conjunt Z_n en el que n siga el mòdul).

Per eixemple:

la divisió gràcies a que m (mòdul) és la multiplicació o la prova de la divisió

nos dona

3m ≡ 1 (mod 11)

El m més chicotet que resol esta congruència és 4; aixina que, el multiplicador modular invers de 3 (mod 11) és 4. No obstant, un atre m que resol la congruència és 15 (fàcilment determinable sumant p a l'invers obtingut).

Càlcul

Algoritme Euclidiano Estés

L'invers multiplicativo de n mòdul p es pot obtindre per mig del Algoritme de Euclides. En particular, invocant l'algoritme estés de Euclides en n i p com a arguments s'obté una tripla (x,i,mcd(n,p)) tal que

$xn+yp=mcd(n,p).$

Si MCD(n,p)=1 llavors

$xn\equiv 1(\mathrm{mod}p),$

d'a on $x$ és l'invers modular de n mòdul p. Si el MCD(n,p)≠ 1 llavors no existix el modular invers. Este algoritme s'eixecuta en un temps O(log(p)²) (assumint que |n|<p).

Eixemple

Per eixemple, supongam que volem calcular l'invers de 117 mòdul 244. Per tant en la nostra nomenclatura (n mòdul p), p=244 i n=117 Lo primer que fem és aplicar l'algoritme de Euclides per a verificar que mcd(n,p)=1. Posteriorment aprofitem els passos intermijos per a trobar el mcd(n,p) en térmens de n i p i aixina obtindre l'invers de n que notarem per n^-1.

• Pas 1:Com a |n| < p llavors podem expressar p com a p=qn+r. És dir 244=2*117+10
• Pas 2:Com 117>10 llavors 117=11*10+7
• Pas 3:Com 10>7 llavors 10=1*7+3
• Pas 4:Com 7>3 llavors 7=2*3+1
• Pas 5:Com 3>1 llavors 3=1*3+0

D'esta forma vàrem demostrar que mcd(244,117)=1

• Pas 6: Del pas 4 rebuge el restant (el número que queda a la dreta de la suma), quedant 1=7-3*2
• Pas 7: Del pas 3 rebuge el restant quedant 3=10-1*7. Si substituïm en l'equació del pas 6 tenim 1=7-(10-1*7)*2=-2*10+3*7
• Pas 8: Del pas 2 rebuge el restant quedant 7=117-11*10. Si substituïm en l'equació del pas 7 tenim 1=-2*10+3(117-11*10)=3*117-35*10
• Pas 9: Del pas 1 rebuge el restant quedant 10=244-2*117. Si substituïm en l'equació del pas 8 obtenim 1=3*117-35*(244-2*117)=-35*244+73*117. D'esta equació podem dir que n^-1=73 que és lo que volíem calcular.
• Pas 10: Si n^-1 és negatiu, l'invers n^-1 es recalcula com a n^-1 + p.

Exponenciación Modular Directa

El método d'exponenciación modular directa com a alternativa a l'algoritme euclidiano estés és el següent:

D'acort en el Teorema de Euler, si n és coprimo en p, és dir, MCD(n,p)=1, llavors,

n^φ(p) ≡ 1 (mod p)

Açò es deduïx del Teorema de Lagrange i del fet de que n pertany al grup multiplicativo de sancers mòdul n $(\mathbb{Z}/p\mathbb{Z}{)}^{*}$ si i només si n és coprimo en p.

Aixina que,

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

a on φ(p) és la Funció φ de Euler.

D'esta forma es pot obtindre el multiplicador modular invers de n mòdul p de forma directa:

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

En el cas especial en que p és primer,

φ(p) = p - 1

Es pot usar l'Exponenciación binaria per a eixecutar este método de forma eficient per ad açò es requerixen solament O(log(p)) operacions modular.

Si s'utilisa el método escolar tradicional, el temps d'eixecució és O(log(p)³).

Quan s'usa la multiplicació basada en FFT de Strassen, el temps d'eixecució és O(log(p)² log(log(p))log(log(log(p)))). Este método és generalment més llent que l'algoritme euclidiano estés pero s'usa a voltes quan ya existix una implementació de la exponenciación modular. Una desventaja d'este método és que necessita φ(p) perque l'única forma de computació eficient requerix el coneiximent dels factors de p.

Vore també

• Generador inversivo congruent
• Aritmètica modular
• Teoria de números
• Criptografia de clau pública