RSA Cryptosystem

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

1. If , then there is some such that
   is nontrivial factor of

Corollary

Finding the private key is essentially as difficult as factoring