A prime day for pie

Two members of the Foundation staff are excited because today is Pi Day while the other three are saying to themselves, “What in the world is Pi Day?” If you are asking the same question, here are some clues:

Pi Day is a surprisingly big deal. For some it’s an excuse to eat pie. (Get it?) For others it’s a day for exploring an irrational number. The Massachusetts Institute of Technology (MIT) sends out college admission decisions on Pi Day. Perhaps more relevant to OpenSSL, UNESCO has declared 14 March as the International Day of Mathematics. Pi gets the name recognition, but another mathematical concept, prime numbers, plays an outsized role in securing communication over the internet.

The key to modern cryptography was the invention of public-key cryptography which turns on the mathematical concept of a one-way function. That might sound complicated, but you probably learned a one-way function in primary school. (“Elementary school” for US readers.) You might remember the concept of factoring numbers, which means figuring out all the numbers that can be multiplied together to get the number you want to factor.

If a teacher asked you to factor 6, you’d write down 2 and 3. If you were especially clever, you might write 1 and 6 too. Then the teacher would explain that numbers that can only be evenly divided by 1 and the number itself are called “prime”. So 6 is not prime (it’s “composite”). 2 and 3, meanwhile, are prime. The task of finding all the prime factors of a number is called “prime factorization” and it’s the secret to one of the ways that OpenSSL keeps your data safe.

Let’s take a harder problem. What are the prime factors of 323?

This problem took less than a minute to create. I just took two prime number I happen to know and multiplied them. Solving the problem takes much longer because there isn’t an easy way to figure out the factors. There are tricks to quickly see if numbers are divisible by 2, 3 and 5, but it gets more and more difficult as the prime factors increase. Even with powerful super computers, prime factorization of the numbers used as keys in modern cryptography could take many years.

In practical terms, I can share the product of two large primes with the world secure in the knowledge that nobody else will ever know the two primes that generated it. That’s handy because it means I can give out my number so that other people can use it to encrypt messages that only I can read. The details of how this all works were explained in a 1977 Mathematical Games article by Martin Gardner called “A new kind of cipher that would take millions of years to break”. The title turns out to be a bit of an exaggeration, but the idea has held up to nearly 50 years of increasingly powerful computers.

Pi pie image: Shisma, CC BY 4.0 https://creativecommons.org/licenses/by/4.0, via Wikimedia Commons