Aparentemente, un método alternativo (para simplemente usar el algoritmo euclidiano extendido) de obtener el exponente para descifrar es hacer d = e ** (phi (phi (n)) - 1) mod (phi (n)). ¿Por qué funciona esto?RSA: ¿por qué funciona phi (phi (n))?
El requisito general para que la operación RSA funcione correctamente es e*d = 1 mod X, donde X es típicamente (p-1)*(q-1).
En este caso, X es phi(n), e es e, y d es e^[phi(phi(n))-1] = e^[phi(X)-1].
Observe que e*d mod X es e*e^[phi(X)-1] mod X = e^phi(X) mod X.
Euler's Theorem establece que a^phi(X) = 1 mod X, para cualquier a que es primo relativo a X, por tanto, el requisito se mantiene.
+1 solo por el hecho de que irradias inteligencia. – Marty
Todo verdadero, excepto que X no es p * q. X es (p-1) * (q-1) donde n = pq yp y q son ambos primos. –