We've seen that the security of RSA is based on the fact that it is hard to factor numbers which are the products of large primes. So how hard is it to find the prime factors of large numbers?

The below applet factors numbers. It uses the following algorithm: first factor out all powers of 2, the number which is left is odd; then check if the number divides by every odd number trying them one after another.

Try to plug some small integers (e.g., 15, 17, 32, 99, etc...) to familiarize yourself with how it works. The time depends very much on your computer power. It also depends on the value of prime factors. It is easy to factor a big number if the factors are small. Below you can see different numbers which are products of two large primes. Next number is about 10 time bigger than the previous one. Try them one after another and see how long it takes.

Let us estimate how the time may increase. Suppose A is the product of two 4 digit primes, and B is a product of two 5 digit primes. Suppose that each 5 digit prime is about 10 times bigger than the corresponding 4 digit prime. Hence to find the first factor our algorithm has to check about 10 times more numbers. As our product is bigger and the numbers we use to check are bigger, each check takes more time on average. So, we see that adding a few digits on to our prime numbers makes factoring the product much, much harder. This is why RSA is considered to be secure.

Prime Factorization Machine

This Java applet implements a basic routine to factor an arbitrarily large integer. The routine starts by extracting any factors of 2. After this, only odd numbers are tested up to the limit=Sqrt(number) + 1. The prime factors are displayed and the result is verified by direct BigInteger multiplication of the factors.