A lock made of primes

About this video

How can numbers keep a secret? This short animation starts with two primes, 211 and 241. Multiplying them takes a minute with pencil and paper: 211 × 241 = 50,851. Going the other way is another matter. Given 50,851 and told it is two primes multiplied together, there is no quick way back: you try dividing by the primes in order, 2, 3, 5, 7, 11 and on, until one divides exactly. Here that is 211, the 47th prime, so it takes 47 tries. Every number is built from primes in only one way, so the answer is there to be found. Finding it is the hard part.

With primes of 300 digits, a computer multiplies them in a blink, but going back from their product, a number about 600 digits long, would take far longer than anyone could wait with every method known today. That one-way street is how a lock can be given away in public. You keep two big primes secret and tell the world their product. Anyone can use the product to lock a message for you, like clicking an open padlock shut, but only the two primes open it. The first lock of this kind, RSA, was published in 1977 and is still used today. This video goes with the Primes Keep Secrets lesson of Number Theory Level 1 on Knaph.

Transcript

1. 0:00Can numbers keep a secret?
2. 0:04Multiply two primes. Two hundred eleven times two hundred forty-one. A minute with a pencil.
3. 0:10Now go back. Try prime after prime. It takes forty-seven tries to find two hundred eleven.
4. 0:17Make the primes three hundred digits long. A blink one way, longer than a lifetime back.
5. 0:23Anyone can close the lock. Only the two primes open it.
6. 0:29Easy one way, hard the other.