Decryption:

We need one more piece of (private) information.

Euclid, about 300 B.C.E.

If a and b don't have any common prime factors, then there are integers c and d such that

Since we picked e such that e and (p-1)(q-1) don't have any common prime factors, then there are integers c and d such that

or

Euclid also tells us how to find c and d, using the Euclidean Algorithm.

Once we have found the decryption exponent d, which is private, we can decrypt.

For each C, compute

What will this give you?

We know

although we don't yet know what P is.  So

but

by Euler's Theorem!  So

and we get our original plaintext back.

Example:

Next Section