Primes Keep Secrets

When you send a message or pay for something on the internet, what you send crosses many computers on its way. Anyone along the way could read it. Yet it arrives safely locked, and only the right person can open it. Part of the lock is made of prime numbers. How can numbers keep a secret?

Easy one way, hard the other

Here are two primes: 211 and 241. Multiplying them takes a minute with pencil and paper:

211 × 241 = 50,851

Now go the other way. Someone gives you 50,851 and says: "This is two primes multiplied together. Which two?" There is no quick way back. You can only try dividing by the primes in order: 2, 3, 5, 7, 11, 13 and on, until one divides exactly. The smaller prime here is 211, which is the 47th prime. So it takes 47 tries.

On top, a short green arrow: 211 times 241 gives 50,851 in one step. Below, a long amber path going back from 50,851: try 2, try 3, try 5, try 7 and on and on, 47 tries, before 211 is found

In Only One Way to Build It we saw that every number is built from primes in only one way. So 50,851 has exactly one answer, 211 × 241. It is there to be found. Finding it is the hard part.

Make the primes bigger

With primes of 3 digits, 47 tries is a long afternoon, not a secret. But the gap grows fast. A computer multiplies two primes of 300 digits each in a blink. Going back from their product, a number about 600 digits long, is another matter: with every method known today, it would take far longer than anyone could wait - by most estimates, millions of years or more, even with many computers working together.

People have tried. In 2020 a team of mathematicians split a number of 250 digits into its two primes. The work would have taken one computer about 2,700 years; it was shared among thousands of them. The numbers used to lock messages are much longer than that.

A padlock anyone can close

This one-way street is how a lock can be given away in public. Think of a padlock that clicks shut without a key.

You make two big primes and keep them secret. You multiply them and tell the world the answer.
Anyone can use your big number to lock a message for you. That is like clicking the open padlock shut.
Opening it needs the two primes. Only you have them.

An open padlock with a big number on it, which anyone can click shut on a box. Beside it, a key made of two prime numbers, which only its owner has

The first lock of this kind was published in 1977 by three mathematicians, Ron Rivest, Adi Shamir and Leonard Adleman. It is called RSA, from their names, and is still used today. (Clifford Cocks in Britain had found the same idea in 1973, but it was kept a government secret until 1997.)

How the message is actually locked needs more maths than this course. The key idea is the one you can see: multiplying primes is easy, and undoing it is hard.

Try it at home

Multiply 13 × 17. Then give the answer to someone at home and ask them to find the two primes. Who was quicker?
91 is two primes multiplied together. Which two?

Answers: 1. 221. 2. 7 × 13 (try 2, 3 and 5 first: none of them divides 91).

Words to know

RSA - a way of locking messages, from 1977, that works because multiplying two big primes is easy but finding them again is very hard

Big idea

Multiplying two primes is quick, but getting them back from the answer means trying prime after prime. With primes hundreds of digits long that would take far longer than anyone could wait, and that is what keeps messages locked on the internet.