A sets up a system so that anyone can send him an encoded
message, but only A will be able to decode it. The message is represented
as a number M. The encoding is done by a publically known function f(M),
with A the only person who knows how to compute 
.
A chooses two large primes p, q which he keeps secret. He announces
n=pq and another number d, with (d,p-1)=(d,q-1)=1 (one way to
do this is to choose d a prime larger than p/2 and q/2.)
The encoding is
where M and f(M) are both 
.
As we have seen f can be computed in a realistic amount of time
even if M, d, n are many digits long.
A computes M from 
using his knowledge of p, q. By
Corollary 8,
Similarly 
if 
.
e satisfies these two conditions if 
. Theorem 1
says we can let e=x, where x is a solution of
Since 
is divisible by p and by q, it is
divisible by pq, hence we can recover M from by taking to
the e-th power mod pq.
It is crucial to the security of this system that knowledge of
n does not allow an eavesdropper to calculate p and q. The
crude approach of dividing n by all numbers up to 
would
take 
steps for a 100-digit n. However, many famous
mathematicians have been unable to devise significantly better
factoring algorithms, and this problem has been studied for at
least 100 years.
One practical difficulty in using this system is the need to do calculations with many-digit numbers, especially to find primes. Another difficulty is that the inventors of this system have patented it. Amateur programmers who have posted implementations on electronic bulletin boards have received letters from ``RSA Security, Inc'' warning of possible patent infringement.