Shor's algorithm

Shor’s algorithm is a quantum algorithm that’s used to find prime factors of a number.

The idea is that the number is repeatedly multiplied with itself until it starts repeating. The required number of multiplications, the period can be used to find prime factors, and was for several decades the fastest quantum factorisation algorithm.¹ In essence, it’s like walking on a line and seeing how far you have to walk to get back to where you started.

Footnotes

1. From 2023’s Biggest Breakthroughs in Computer Science by Quanta Magazine. ↩