Re: About RSA Cryptosystem

On Feb 27, 5:13 pm, "Jian-jie" <jjzhao1...@xxxxxxxxx> wrote:
The RSA Cryptosystem. uses computations in Zn, where n is the product
of two distinct odd primes p and q. For such n, note that φ(n) = (p -
1) (q - 1).

It is easy to prove that ((x)^b)^a=x(mod n) when x belongs to Zn*.But
how to prove the result when x belongs to Zn\Zn*.
Thank you very much!
J-Zhao

Use the CRT. If m is not co-prime to p, then m^(ed) = 0 = m mod p
same with mod q. Thus m^(ed) = m mod p (and mod q)

Also, If p and q are coprime, a = b (mod p), and a=b (mod q), then a =
b mod (pq).

.