The RSA Theorem

Let p and q be distinct primes, and let e, d satisfy ed=1pmod{(p-1)(q-1)}. Then for any m<n=pq, m^{ed}=mpmod{n}.

For some reason, even in published works, this important cryptographic result is often only half proved. Here is a full proof.

Proof: We consider two cases: (i) m is relatively prime to both p and q (and hence relatively prime to n=pq), and (ii) m is a multiple of one of the primes, say p. We note that m can’t be a product of both primes, for then it would be greater than their product, thus violating the statement of the theorem.

(i) By definition, ed=k(p-1)(q-1)+1 for some integer k. Since (p-1)(q-1)=phi(n), then by Euler’s theorem

m^{ed}=m^{kphi(n)+1}=m(m^{phi(n)})^k=mpmod{n}.

(ii) Clearly

(1) m^{ed}=mpmod{p}

since both sides are equal to 0pmod{p}. We can also write m^{ed}=m^{k(p-1)(q-1)+1}=m.(m^{q-1})^{k(p-1)}, and since m is relatively prime to q, then by Euler’s theorem again m^{q-1}=1pmod{q} and so

(2) m^{ed}=mpmod{q}

By the Chinese remainder theorem, (1) and (2) together prove m^{ed}=mpmod{n} as required. Box

2 thoughts on “The RSA Theorem

  1. Possible typos:

    [1] …relatively prime to both p and q (and hence…
    comment: don’t know where the closing parenthesis should be placed; I think it’s missing.

    [2] …for then it would be greater then their product…
    —>
    …for then it would be greater than their product…
    comment: for the second “then”, change “e” to “a”

Leave a Reply

Your email address will not be published. Required fields are marked *