Prime Factorization Problem

Prime Factorization Problem is a fundamental concept that underlies many cryptographic algorithms. It is based on the idea that every natural number can be written as a product of prime numbers, which are numbers that have only two factors: one and themselves. For example, 12 can be written as 2 x 2 x 3, where 2 and 3 are prime numbers.

But why is this a problem? To understand this, let’s do some experiments with different numbers and see how easy or hard it is to find their prime factorization.

First, let’s take some small numbers: 10, 35, 95, 178, 595, and 973. Try to find their prime factorization by yourself or using a calculator. You can use the method of trial division, which means dividing the number by successive primes until you get a quotient of one. For example, to find the prime factorization of 10, you can do:

10 / 2 = 5
5 / 5 = 1

So the prime factorization of 10 is 2 x 5.

Did you find the prime factorization of the other numbers? Here are the answers:

35 = 5 x 7
95 = 5 x 19
178 = 2 x 89
595 = 5 x 7 x 17
973 = 7 x 139

How long did it take you to find them? Probably not too long, right? Now let’s try some bigger numbers: 583634, 837453831, and 74548749236. Try to find their prime factorization using the same method. How long does it take you now? You might notice that it takes much longer and it is much harder to find the right primes to divide by. You might even give up after a while.

Here are the answers for these numbers:

583634 = 2 x 291817
837453831 = 3 x 279151277
74548749236 = 2 x 2 x 13 x 32843 x 43651

Did you get them right? How did you feel while doing this task? You probably felt frustrated and bored. This is how computers feel too when they try to find the prime factorization of large numbers. It can take them years or even centuries to find the answer using the best algorithms available.

Now let’s do another experiment. Instead of finding the prime factorization of numbers, let’s try to multiply them. For example, try to multiply these numbers:

2 x 5
5 x 7
5 x 19
2 x 89
5 x 7 x 17
7 x 139
2 x 291817
3 x 279151277
2 x 2 x 13 x 32843 x 43651

How long does it take you to do this? Probably much faster and easier than finding the prime factorization, right? You can use a simple algorithm like long multiplication or use a calculator to get the answers quickly. Here are the answers for these numbers:

2 x 5 = 10
5 x 7 = 35
5 x 19 =95
2 x89 =178
5x7x17=595
7×139=973
2×291817=583634
3×279151277=837453831
2x2x13x32843x43651=74548749236

Did you get them right? How did you feel while doing this task? You probably felt confident and satisfied. This is how computers feel too when they try to multiply large numbers. It can take them milliseconds or even nanoseconds to get the answer using simple algorithms.

So from this experiment, we can conclude that it is easy to multiply large numbers but it is very difficult to find the prime factorization of large numbers.

This is the prime factorization problem.

I hope this story helps you understand what the prime factorization problem is and why it is important for cryptography. If you want to learn more about this topic