Prime Factorization (or integer factorization) is a commonly used mathematical problem often used to secure public-key encryption systems. A common practice is to use very large semi-primes (that is, the result of the multiplication of two prime numbers) as the number securing the encryption. In order to break it, they would have to find the prime factorization of the large semi-prime number – that is, two or more **prime numbers** that multiplied together result in the original number.

First off, a bit of elementary math review. What is a prime number? A prime number is any number that is only evenly divisible by 1 and itself. 2 is a prime number, as is 3, 5, 7, 11, 13, 17, and so on. There are an infinite number of prime numbers (that is numbers don’t get to a point where they are always divisible by something). Additionally, all numbers have exactly one prime factorization – that is to say, every number can be reached by multiplying some prime numbers together.

Computationally speaking, it’s relatively easy to generate a fairly large prime number. You go fairly high up in numbers and then check backwards – if this divisible by anything? So we can generate our two prime numbers together. Then we multiply them together – simple enough. As a quick example, using more easy to understand primes:

Okay – so 589 is the result of multiplying these two primes together. You see – multiplying two numbers is a mathematically easy problem, and it scales well when you get into the bigger numbers. However, **factoring** numbers is a computationally difficult problem. It’s easy for smaller numbers, but once you start dealing with very large numbers, it can take computers, days, months, years, even centuries to solve. There is no easy shortcut for factoring numbers – it’s a trial and error process. You would have to try all of the primes that are less than 589 until you found which prime numbers that when multiplied together come to 589. This works for smaller numbers, but once you begin dealing with very large numbers the amount of possible numbers you need to check against each other becomes so large that even modern computers are not able to do it in a reasonable time frame.

To learn more about online privacy, see our guide to the best VPNs in Canada. Or if you prefer French, take a look at Meilleur VPN.

You Might Also Like:

• Big-O-Notation
• Pseudo-Random Number Generation
• The Birthday Problem