where and are both . We have seen can be computed in a realistic amount of time even if , , are many digits long.

A computes from using his knowledge of , . By
Corollary 8,

Similarly if . satisfies these two conditions if . Theorem 1 says we can let , where is a solution of

Since is divisible by and by , it is divisble by , hence we can recover from by taking to the -th power mod .

It is crucial to the security of this system that knowledge of
does not allow an eavesdropper to calculate and . The
crude approach of dividing by all numbers up to would
take steps for a 100-digit . 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.

2002-12-14