Finding a sequence’s period

In the section entitled How Shor’s algorithm works, we saw how knowing the period of a certain repeating sequence of numbers helps an eavesdropper factor a large public key and decrypt a message. How can quantum computing help the eavesdropper discover a sequence’s period?

Consider the following sequence of numbers:

1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3, 1, 2, 7, 10, 15, 3

For want of a better name, we’ll call this my sequence. In my sequence, the pattern 1, 2, 7, 10, 15, 3 occurs four times:

• Since the pattern contains six numbers, we say that my sequence’s period is 6
• Since the pattern occurs four times in my sequence, we say that the pattern’s frequency is 4

My sequence contains 24 numbers. So, the period and frequency in my sequence are related by the following formula:

Mathematicians refer to my sequence’s period and its frequency as dual variables...