Imagine you have a product of two prime numbers, say, 221. Now, we set that number to be an endpoint—for the purposes of our game, there are no higher integers. If we multiply two numbers together and get a number larger than 221, it wraps around, so 15 times 15 results in 225-221 = 4. If we multiply two by itself, we only get four, which doesn’t wrap, and we can do that 7 times before it wraps. But 28 results in 35. Got that? Great.

via Quantum cryptography: yesterday, today, and tomorrow | Ars Technica.

Let’s consider a consequence of using phase to calculate prime factors: 221 has prime factors 17 and 13, and factors 1 and 221. We can eliminate the latter in the classical part of our algorithm. But, what about two and 111? “Wait,” you say. “That is not a factor. The product is 222.” Nevertheless, we need to think about it, because quantum algorithms are probabilistic. 17 and 13 have the highest probabilities, but two and 111 only have a phase error of 0.5 percent. The probability of Shor’s algorithm returning the incorrect result is rather high. Unfortunately, a near miss (though easy to spot, since it is very quick to calculate that 2×111=222 not 221). This is likely not very useful in terms of decrypting a message, so we need to do something to increase the chance of getting the correct answer.