[AleBD]

Buenos días,

¿me podría ayudar alguien a entender cómo se haría el inverso de \( y^a \text{ módulo } p \), por favor? Lo necesito calcular para \( y=13,a=5 \text{ y }p=53 \) pero me gustaría aprender el proceso.

Gracias

[energy]

Vale, te explico:

Encontrar ese inverso se reduce a resolver la congruencia \( y^a x\equiv{1} mod(p) \) entonces tienes que encontrar una Identidad de Bezout de \( y^a \) y \( p \) para que

\( y^a x- p z=1 \) y pasando al otro lado \( y^a x -1=pz \) es decir un múltiplo de p que es equivalente a la congruencia, pero claro, la identida de Bezout existe pero es igual a 1 si y solo si \( mcd(y^a,p)=1 \)

Spoiler

En tu caso \( mcd(13^5,53)=1 \) por ser 13 primo y 53 primo

[cerrar]

[Luis Fuentes]

Hola

Vale, te explico:

Encontrar ese inverso se reduce a resolver la congruencia \( y^a x\equiv{1} mod(p) \) entonces tienes que encontrar una Identidad de Bezout de \( y^a \) y \( p \) para que

\( y^a x- p z=1 \) y pasando al otro lado \( y^a x -1=pz \) es decir un múltiplo de p que es equivalente a la congruencia, pero claro, la identida de Bezout existe pero es igual a 1 si y solo si \( mcd(y^a,p)=1 \)

Spoiler

En tu caso \( mcd(13^5,53)=1 \) por ser 13 primo y 53 primo

[cerrar]

El procedimiento explicado por energy está desarrollado aquí con un ejemplo concreto:

http://rinconmatematico.com/foros/index.php?topic=86019.msg344860#msg344860

Otra opción es tener en cuenta que por el pequeño Teorema de Fermat, \( y^{p-1}=1 \) mod \( p \). Por tanto \( (y^a)^{-1}=y^{p-1-a} \) mod \( p \). En tu caso:

\( (13^5)^{-1}=13^{53-1-5}=13^{47} \) mod \( 53 \)

Fíjate que aunque esto pueda parecer más rápido que lo propuesto por energy, en la práctica no  lo es (o no tiene porqué serlo). Todavía nos queda calcular de manera efectiva esa potencia módulo \( 53.  \) Sobre esto último puedes leer por aquí:

http://ai.eecs.umich.edu/people/rounds/Winter02Slides/LectureApril4.pdf

Saludos.