How come there’s prime numbers and not un-prime numbers?
In: Technology
The details behind why we use prime numbers for certian types of cryptography is very, very complex, but at a _super_ high level, primes are important because the security of many encryption algorithms are based on the fact that it is very fast to multiply two large prime numbers and get the result, while it is extremely computer-intensive to do the reverse.
When you encrypt something, brute forcing the encryption becomes functionally impossible (with technology the way it stands today) because you just have to keep guessing prime combinations until you get it right; if you were to use non-prime numbers, you are able to use factorization to make the brute-force application much easier.
Prime numbers are often useful for cryptography because computers are really bad at factoring big numbers quickly. RSA, a famous encryption algorithm, uses the product of two large prime numbers as the public piece of information used for encoding data. If someone knows the two prime numbers, they can crack the code. However, since computers are bad at factoring, it’s basically impossible to find them out.
So why do the two large numbers need to be prime? Well, because, if they weren’t, they would have smaller prime factors (every composite number is a product of smaller primes), which could be found quickly, dramatically reducing the time required to factor the large, public number.
In a nutshell, encryption often relies on computers being bad at factoring. Big prime numbers, having no factors, make factoring problems even harder.
Increasingly they’re not – other methods are being used.
However, the basic principle is that you want a mathematical operation that is easy to perform in one direction but hard to perform in reverse.
If I give you two prime numbers, multiplying them is easy. Even if I give you two 100-digit prime numbers, you can probably multiply them by hand in a minute or two.
However, if I give you the result of that multiplication and ask you to factor it back into the two original 100-digit prime numbers, you could spend the rest of your life trying to solve that problem and you’d still run out of time.
What that means is that I can give you that very large composite number and you can use it to mathematically manipulate the data in such a way that only someone (presumably me) who has the original prime factors can undo. Since it’s so hard to factor the composite number, I don’t have to worry (much) about someone reverse-engineering the original prime factors from the very large composite number.
Some forms of encryption work by multiplying two numbers together (there’s more to it than that but it’s an ELI5). You decrypt that data by getting the factors.
We don’t have a good way to factor numbers. A lot of it comes down to guessing a number and seeing if it divides easily.
If you use two prime numbers there are only 2 possible factors to the larger number so it’s really hard to guess. If you don’t use prime numbers there are more possible factors so it’s easier to guess.
example:
221 has only 2 factors; 13 and 17
273 has more factors; 3, 7 and 13
So if you start guessing randomly you have a 50% higher chance of guessing a prime factor of 273 than of 221.
Latest Answers