Why does cryptography use prime numbers

However, if Alice chooses two large prime numbers, computes their product, and communicates this openly, finding out what her original prime numbers were will be a very difficult task, as only she knows the factors. So Alice communicates her product to Bob, keeping her factors secret. Bob uses the product to encrypt his message to Alice, which can only be decrypted using the factors that she knows. If Eve is eavesdropping, she cannot decipher Bob's message unless she acquires Alice's factors, which were never communicated.

If Eve tries to break the product down into its prime factors—even using the fastest supercomputer—no known algorithm exists that can accomplish that before the sun will explode. Large prime numbers are used prominently in other cryptosystems too. The faster computers get, the larger the numbers they can crack. For modern applications, prime numbers measuring hundreds of digits suffice. These numbers are minuscule in comparison to the giant recently discovered.

In fact, the new prime is so large that, at present, no conceivable technological advancement in computing speed could lead to a need to use it for cryptographic safety.

It is even likely that the risks posed by the looming quantum computers wouldn't need such monster numbers to be made safe. It is neither safer cryptosystems nor improving computers that drove the latest Mersenne discovery, however. It is mathematicians' need to uncover the jewels inside the chest labeled "prime numbers" that fuels the ongoing quest. This is a primal desire that starts with counting one, two, three, and drives us to the frontiers of research.

The fact that online commerce has been revolutionized is almost an accident. The celebrated British mathematician Godfrey Harold Hardy said: "Pure mathematics is on the whole distinctly more useful than applied.

For what is useful above all is technique, and mathematical technique is taught mainly through pure mathematics. The merit of knowing these numbers lies in quenching the human race's intellectual thirst that started with Euclid's proof of the infinitude of primes and still goes on today. This article was originally published on The Conversation.

Now I'm going to send you a message outlining how many bottles of beer are on the wall — 99, of course — but we don't want anyone else to know.

Even if the message isn't a number, it can easily be represented as one; your phone or computer has made that conversion for you to read this article. I look you up on a directory and find your public key — your N and e — ,7. Then the calculations start. I raise my message to e it's an exponential, get it? In other words, I multiply 99 x 99 x 99 x 99 x 99 x 99 x 99 seven times and end up with a very large number. It's more than 93 trillion.

I then divide this massive number by your N The answer to this calculation is still pretty big ,,, Remember learning fractions and decimals? Divide a large number by a small number and you can end up with leftovers. For instance, 6 divided by 4 equals 1 with a remainder of 2.

In our encryption example, the remainder is And it's this number that I send to you; that's our encrypted message. We don't care if it's intercepted, because only you can decipher it. It's calculated based on your two original, secret prime numbers p and q and your public e. And now the numbers get even bigger. You take my message and multiply it by itself 23 times, ending up with a mammoth figure that's odd digits long.

Then divide this new, monster number by N , the product of your original primes p and q and find the remainder. All up, you keep p , q and d secret; N and e are public. There are, of course, online calculators that do all these sums for you. And in real encryption, you'd never choose simple prime numbers like 11 and 15 as p and q , Professor Batten explained.

The reason prime numbers are fundamental to RSA encryption is because when you multiply two together, the result is a number that can only be broken down into those primes and itself an 1.

In our example, the only whole numbers you can multiply to get are 11 and 17, or and 1. It's easy enough to break down into its primes because they're so small. But when you use much larger prime numbers for your p and q, it's pretty much impossible for computers to nut them out from N. Still, computers are getting faster and more powerful all the time, so mathematicians continue to search for large prime numbers. And when it comes to the biggest known prime numbers, Mersenne primes are most prolific.

Named after a French polymath, Mersenne primes take the form of 2 multiplied by itself a certain number of times, minus 1. The Boxing Day prime is a Mersenne prime: it's 2 multiplied by itself 77,, times, minus 1. It turns out that in binary — the language of computers — Mersenne primes can be denoted as strings of 1s only. Basically you have a " public key " consisting of a product of two large primes used to encrypt a message, and a "secret key" consisting of those two primes used to decrypt the message.

You can make the public key public, and everyone can use it to encrypt messages to you, but only you know the prime factors and can decrypt the messages.

Everyone else would have to factor the number, which takes too long to be practical, given the current state of the art of number theory. If you multiply two large prime numbers, you get a huge non-prime number with only two large prime factors. Factoring that number is a non-trivial operation, and that fact is the source of a lot of Cryptographic algorithms. See one-way functions for more information.