To find a hidden repeat, try waves until one lights up

Physicists spend their careers hunting for repeating patterns, said Phil, a physicist who works on quantum computers. From locating atoms in a crystal lattice to mapping the cosmic microwave background, the faint glow left over from the early universe, much of the job is asking what waves combine to make a pattern. The math for that goes back to the 19th century French mathematician Joseph Fourier.

Take a simple striped pattern, like the bars of a crosswalk. A Fourier transform breaks it into a sum of simple sine and cosine waves, the smooth up and down curves from school math.

Two details matter: how much of each wave you need, and the phase, which is how the peaks and troughs line up. The first piece is boring. It is just flat gray, the average brightness of the picture, what engineers call the DC level. Since it never ripples, its frequency is zero.

Then the hunt begins. Try a wave that fits once across the picture, and almost nothing happens. Try one that fits twice, and still little changes. Try one that fits three times, and bingo, it contributes a huge amount. You have found the repeat.

That pattern can live in space, like an image, or unfold over time, like a tune. In code breaking, the pattern is a list of numbers that repeats, such as 1, 2, 4, 8, then 1, 2, 4, 8 again.

Adding waves together to build a picture is called Fourier synthesis. Running the other way, starting with the list and asking what waves build it, is called Fourier decomposition. That reverse search is what Shor's algorithm needs, a quantum method for breaking codes by finding a number's hidden repeat.

In the small demo for the factoring problem with the number 15, the list holds 16 numbers, the sequence 1, 2, 4, 8 repeated four times. Those 16 slots are the window, and the average of the numbers in it is 3.75.

Waves that cycle once, twice, or three times across that window contribute nothing. The wave that cycles four times lights up, and the period of 4 pops out.

That fast way to find the repeat is the speedup: finding the repeat for a huge number without testing every factor. The 600 digit number is the one to be factored, and the list is the repeating sequence it produces. You could never eyeball that list, and you would never want to test every possible factor by hand. Apply the transform and the peak appears.