[juaninf]

Buenas noches, miren quisiera saber por qué se usa el algoritmo de Euclides Extendido para hallar el inverso multiplicativo de un número en módulo n, quisiera saber esto para seguir avanzando y entendiendo mejor mi algoritmo RSA.

[Ked]

Se usa porque es una manera de hallar el inverso multiplicativo de un número módulo n (como dices ).

Procedo asumiendo que ya sabes aplicarle el algoritmo a dos números cualesquiera para escribir su máximo común divisor como combinación lineal.

Decimos que \( a \) es un inverso modular de \( b \) módulo \( n \) si \( ab\equiv 1\ (\mbox{mod}\ n) \)
Se prueba fácilmente que \( a \) tiene inverso módulo n \( \Leftrightarrow \) \( \mbox{mcd}(a,n) = 1 \)
De hecho la prueba del recíproco la podemos hacer usando el algoritmo de Euclides extendido:

Si \( \mbox{mcd}(a,n) = 1 \) entonces por AEE podemos hallar \( x,y \in \mathbb{Z} \;/\; xa + yn = 1 \) (es el mcd como combinación lineal)
Ahora en esta última ecuación tomamos congruencia módulo n:
\( 1 = xa + yn \equiv xa (\mbox{mod}\ n) \) (pues yn es múltiplo de n, por lo tanto congruente con 0)

Obtuvimos \( xa \equiv 1 (\mbox{mod}\ n) \), es decir, \( x \) es un inverso modular de \( a \).


Otra forma de calcular el inverso multiplicativo es usando la función \( \varphi \) de Euler.
Sabemos que: \( \displaystyle a^{\varphi(n)} \equiv 1 (\mbox{mod}\ n) \)
Aplicando propiedad de los exponentes, lo podemos escribir como: \( \displaystyle a^{\varphi(n)-1}\cdot a \equiv 1 (\mbox{mod}\ n) \)
Por lo tanto \( \displaystyle a^{\varphi(n)-1} \) es un inverso modular de a.

Este último método puede no ser tan eficiente para un algoritmo como RSA (se trabajan con números muy grandes y para calcular la \( \varphi \) es necesario tener la descomposición en primos del número), sin embargo el algoritmo de Euclides es muy eficiente.

Saludos

[juaninf]

Muchas gracias por tu respuesta amigo, me sirve mucho,pero esta parte no entendi mucho : \( 1=xa+yn\equiv{xa{(modn)}} \),existe alguna propiedad donde pueda expresar una ecuacion con modulos y cambiar el \(  = por \equiv{} \), grax por tu respuesta

[Ked]

En realidad no estoy cambiando el igual, simplemente me estoy ahorrando un paso

Tenemos: \( 1 = xa + yn \)
Y también \( xa + yn \equiv xa \ (\mbox{mod}\ n) \)

El último paso es por definición de congruencia. Hay dos definiciones que conozco y son ambas equivalentes.
1) \( a \equiv b \ (\mbox{mod}\ n) \) si a y b dejan el mismo resto en la división por n
2) \( a \equiv b \ (\mbox{mod}\ n) \) si \( a-b \) es múltiplo de n

Aplicando la segunda definición tenemos que \( (xa+yn)-xa = yn \) es múltiplo de n, por lo tanto \( xa + yn \equiv xa \ (\mbox{mod}\ n) \)

Pero como \( xa + yn = 1 \), entonces tenemos que \( 1 \equiv xa \ (\mbox{mod}\ n) \)
Que es lo que queríamos

Saludos

[argentinator]

existe alguna propiedad donde pueda expresar una ecuacion con modulos y cambiar el \(  = por \equiv{} \)

La congruencia tiene las siguientes propiedades de la igualdad:
Reflexividad, Simetría, Transitividad
Eso ocurre porque la congruencia es una relacion de equivalencia:
\( a\equiv{a} \)
\( a\equiv{b}\Rightarrow{}b\equiv{a} \)
\( a\equiv{b},b\equiv{c}\Rightarrow{}a\equiv{c} \)

Con respecto a las operaciones aritméticas, la congruencia es coherente miembro a miembro con las operaciones de suma, resta y multiplicación (siempre hablando de sumandos y factores estrictamente enteros):

Supongamos que \( a\equiv{a'} \) y \( b\equiv{b'} \)
Entonces valen las congruencias:
\( a+b\equiv{a'+b'} \)
\( a-b\equiv{a'-b'} \)
\( a\cdot b\equiv{a'\cdot b'} \)

Pero cuidado con la división. En general no se puede dividir miembro a miembro, ni siquiera aunque las divisiones sean enteras.
Para poder dividir hay que trabajar con cuidado, y estudiar bien las exigencias de coprimalidad que aparecen, aunque esto parece ser parte de lo que están discutiendo, así que no lo agrego.