Demostración del correcto funcionamiento del sistema RSA
Tenemos p,q primos; N=p*q; phi(N)=(p-i)*(q-1); e*d=1 mod phi(N)
La función de codificación es f(X)=x^e mod N
La función de decodificación es g(X)=x^d mod N
El funcionamiento correcto se dará sólo si g(f(x))=i(x), i.e. x^(e*d)=x mod N

Tenemos ed=1 mod phi(N)
Así que existe un entero k tal que ed=1+phi(N)*k
Hacemos x^(ed)=x^(1+phi(N)*k) mod N
x^(ed)=x*(x^k)^phi(N) mod N
El teorema de Euler (pag 42) dice que a^phi(b)=1 mod b para todo b, por tanto x^(ed)=x mod N. Quod erat demostratum.

---

Algunos procedimientos de MAPLE