Breaking website codes is really about finding a repeating pattern

Every time your browser trusts a website, it is trusting math. The site publishes a public key that contains a huge number, called N. That N is a semi-prime, meaning it is one prime number, P, multiplied by another prime number, Q. The primes are secret, and if you can find them you can work out the private key, forge signatures, and spoof websites.

Guessing P and Q directly is hopeless. For realistic key sizes, it would probably take hundreds of millions of years with decent computing. The clever move in Shor's algorithm, a quantum method for finding the period, is to stop trying to factor and instead ask how often a certain calculation repeats.

Take a toy example where N is 15, whose secret factors are 3 and 5. Pick a random smaller number, say 2, and keep multiplying by it, but always keep only the remainder after dividing by 15. This remainder arithmetic works like a clock face with 15 hours, where you wrap around each time you pass the top, so the remainders have to eventually repeat.

The sequence goes 1, then 2, then 4, then 8. The next power would be 16, which wraps around the 15-hour clock to 1. Then it starts over: 2, 4, 8, 1. The pattern 1, 2, 4, 8 has a period, called R, of 4. Finding R is the whole game.

Saying 2 to the power of 4 equals 1 on that clock means 2 to the power of 4 minus 1 lands exactly on zero, so it is an exact multiple of 15. It equals some large whole number K, which nobody needs to know, times N, and since N is P times Q, that is also K times P times Q.

Ordinary algebra then splits that quantity, because a squared minus b squared equals the first number minus the second, times the first number plus the second. Here 2 to the power of 4 minus 1 is 2 squared, squared, minus 1 squared, so it becomes one number times a second number, where the second number is 2 to the power of R divided by 2, plus 1. That second number very often shares a factor with N. Take the greatest common divisor, the largest whole number that divides both, and a factor pops out.

Here R divided by 2 is 2, so that number is 2 squared plus 1, which is 5. The largest number dividing both 5 and 15 is 5, one of the secret factors. The other follows at once, because 15 divided by 5 is 3. If R had been odd, the halving would not have worked, and the recipe would be to pick a new starting number and try again.

For a real N of about 2,000 bits, that repeating sequence is far too long to walk through step by step. A quantum computer is useful because it can find the period without counting every step.