Math Alive Crypto 2 (2024)

We've seen that the security of RSA is based on the fact that it ishard to factor numbers which are the products of large primes. So howhard 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, thenumber which is left is odd; then check if the number divides by everyodd number trying them one after another.

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

Let us estimate how the timemay increase. Suppose A is the product of two 4 digit primes, and B isa product of two 5 digit primes. Suppose that each 5 digit prime isabout 10 times bigger than the corresponding 4 digit prime. Hence tofind the first factor our algorithm has to check about 10 times morenumbers. As our product is bigger and the numbers we use to check arebigger, each check takes more time on average. So, we see that adding afew 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 abasic routineto factor an arbitrarily large integer. The routine starts byextracting any factors of 2. Afterthis, only odd numbers are tested up to the limit=Sqrt(number)+ 1. The prime factors are displayed andthe result is verified by direct BigInteger multiplication of thefactors.