Suppose where are distinct odd primes.
Choose some encrypting exponent such that
By Euclid, find such that
Call the decrypting exponent.
The public key is
We encrypt as
The private key is and we decrypt as
Then
Theorem
Suppose we know some
Write for order of in
Write where and is odd
Let
If , then there is some such that
is nontrivial factor of
Corollary
Finding the private key is essentially as difficult as factoring