Copy
Interesting Things I Come Across
Edition 036
Read time: 4 min 
An increasingly irrelevant number is worth $250,000
A primer
A prime number does not divide into anything other than one and itself. Prime numbers are important for reasons I'll get to soon; they are also plentiful: Euclid, in perhaps the fourth century, proved there are infinitely many unique primes. To date, the largest known of these is 23,249,425 digits long, and was discovered on Boxing Day last year by a collaborative network of volunteers, each of whom dedicate some of their excess computing power. This community call themselves GIMPS; the Great Internet Mersenne Prime Searchers. 

The prize, the value
The Electronic Frontier Foundation will pay $250,000 to whoever discovers a prime number more than one billion digits long. Two GIMPS members have already claimed bounties for one- and ten-million digit primes: $50,000 and $100,000, respectively.  

The aforementioned money comes from an anonymous donor, and the EFF website is coy on exactly why the bounty exists. However: prime numbers are valued mostly for their role in internet security. Encryption largely relies on the inability of present-day computers to solve problems involving very large prime numbers. Here is the root of it: 

"It’s easy to take two large prime numbers and multiply them, but it’s very difficult to take a large number that is the product of two primes and then deduce what the original prime factors are [...] prime factorization is an example of a process that is easy one way (easy to scramble eggs) and very difficult the other (nearly impossible to unscramble them). In cryptography, two large prime numbers are multiplied to create a security key. Unlocking that key would be the equivalent of unscrambling an egg" 
(via The New Yorker profile of an Oxonian recluse widely considered the father of quantum computing)

The science
Here is very short version of the physics involved in quantum computing, which I will no doubt bastardise, and encourage you to read up on yourself. Regular computers use bits as the most basic unit of computation; they are either one or zero. Quantum computing takes advantage of a quirk discovered by quantum physicists: a particle exists in lots of places simultaneously until it is observed to be in one place. Quantum bits (qubits) harness the uncertainty inherent to unobserved particles, and can be both one or zero or both one and zero, simultaneously. In theory, this makes quantum computers incredibly efficient at solving problems: "with one millionth of the hardware of an ordinary laptop, a quantum computer could store as many bits of information as there are particles in the universe" (again, via The New Yorker).

Some quantum scientists suggest that if quantum computing works as predicted, the existence of multiple universes is the best explanation. 

The irrelevancy 
So: modern encryption relies on prime products being too difficult to factorise. But: quantum computers will be able to solve such problems far more easily. Current supercomputers remain superior to the best quantum computers, owing to the difficulties involved in keeping multiple qubits stable for long enough to be computationally useful. However: the first quantum-capable computer will in theory be able to decrypt anything encrypted using present technology. 

The irony  
Such a computer would also, presumably, be able to find very large prime numbers relatively easily -- and claim the aforementioned $250,000 prize. So: the existence of a quantum computer capable of finding large primes would also render the cryptographic value of large primes useless.  

 
* * *
 
Addenda
1. The race to develop stable quantum computers is very much on, and here's a long read about China's efforts: alongside quantum computers, they're also testing new types of encryption using quantum physics. This is going on right now: they've built a long chain of quantum receivers at 100 kilometre intervals through the countryside, and they're sending quantum information to and from special satellites
2. According to my limited understanding of blockchain architecture, blockchains rely on similar prime factorisation problems. Not sure of the implications here.
About Interesting Things I Come Across 
Interesting Things I Come Across is a weekly, self-explanatory newsletter. My goal is to share thoughtful ideas with clever people in no more than 500 words. Replies are encouraged and corrections are welcomed. I don't necessarily endorse the Things I write about, unless explicitly stated.

If you want to claim the ideas as your own while speaking to friends, that's fine. However: you could save yourself the hassle by forwarding this to people you think would find it interesting. They can subscribe here and read old editions here.
 
Update your details or unsubscribe
Email Marketing Powered by Mailchimp