What’s a better idea for a first real post than a post about primes?

One beautiful day my girlfriend and me listen to some guy on youtube and he mentions how quantum computers are gonna change how fast we can find prime numbers.

Unexpectedly, she asks:

“What are prime numbers?””

Easy:

natural number greater than 1 that has no positive divisors other than 1 and itself 1

But it gets harder:

“Why are prime numbers that important?”

That got me thinking. Fermat’s last theorem? Cryptography? $100 000 prize for finding prime number?

Thinking really hard

Let’s be pragmatic and stick to cryptography. In short, huge part of current cryptography relies on prime numbers.

Say, you need some prime numbers with a lot of digits. It’s not trivial but it’s not that hard neither. Just pick some random very high number and use the algorithm that can say with very high probability that the number you’ve chosen is prime.

Find second prime number with many digits. Now multiply them. Result is a base for your public key in public key cryptography.

In case you don’t know, quick introduction:

Public (aka asymmetric) key cryptography is based on a fact that you have two keys: one private and one public. The thing that was secured (ciphered) with private key, can be unsecured (deciphered) with public key. Reversely - something ciphered with public key can be deciphered with private key only. You can’t cipher and decipher the same thing with public key, it doesn’t make sense.

Private key, as the name implies, is private which means no one should never know its value. Public key, on the other hand is really public, so anyone might know its exact value.

Sorcery

This sorcery is based on prime numbers. Those two prime numbers you found will make your private key. And their multiplication will make your public key. So in theory, everyone holding you public key has all information to get your private key, right? Especially given that prime numbers properties ensure that there is only one correct answer to question: what should I multiply to obtain that public key?

Yes, everyone with your public key is able to find out your private key. The question is how much time would it take to calculate it for large numbers. This problem is known as Prime Factorization and currently we don’t know any efficient algorithm to solve it.

The most popular (and still widely used) algorithm based on this problem is RSA - public key cryptography algorithm. Its creators in 1977 published a challenge in Scientific American article, where they challenged everyone to do prime factorization of 129-digit number.

They claimed that to break such a large number and find its primes would take the fastest computers of 1977 running for millions of times the age of the universe.2

Of course computers advanced much faster than expected, smarter algorithms emerged, internet occurred and problem was solved in 1994. A few years later 155-digit number was factorized and now current record is 232-digit number, which was broken by

equivalent of almost 2000 years of computing on a single core 2.2 GHz AMD Opteron

That’s a lot of digits and a lot of computer time.

As RSA-768 (smarter name for last mentioned number) was factorized, currently one should use at least RSA-1024 which you may think as equivalent to 309 digits. Of course the more digits, the merrier.

This is why we care about prime numbers and why finding huge prime numbers is a good thing. It makes us all secure.

  1. https://en.wikipedia.org/wiki/Prime_number 

  2. https://books.google.pl/books?id=hk72BwAAQBAJ&lpg=PA198&ots=V40B2u4IR1&dq=RSA%20first%20challenge&hl=pl&pg=PA198#v=onepage&q=RSA%20first%20challenge&f=false