How Shor’s algorithm works

If you remember only one thing about the strategy behind Shor’s algorithm, it should be this: the algorithm examines the repetition within a particular sequence of numbers and uses that repetition to factor the public key.

Let’s take a look at some sequences of numbers. (Once again, the numbers in our examples are laughingly small to ensure that the arithmetic is manageable.) On a rainy day in August, Alice initiates a sensitive conversation with Bob. While Eve does her snooping, she notices Alice sending the public key 15 to Bob. Eve’s goal is to factor 15 into its component parts.

With the help of her computer, Eve chooses a number that’s smaller than 15. As we did in the previous section, we’ll call this smaller number a coprime. As with the previous section’s coprime, this smaller number must have no divisors (other than 1) in common with the public key 15.

In this example, let’s have Eve...