Breaking RSA encryption
N. David Mermin · Cambridge University Press eBooks · 2007
Period finding, factoring, and cryptography Simon's problem (Section 2.5) starts with a subroutine that calculates a function f(x) , which satisfies f(x) = f(y) for distinct x and y if and only if y = x ⊕ a , where ⊕ denotes the bitwise modulo-2 sum of the n -bit integers a and x . The number of times a classical computer must invoke the subroutine to determine a grows exponentially with n , but with a quantum computer it grows only linearly. This is a rather artificial example, of interest primarily because it gives a simple demonstration of the remarkable computational power a quantum computer can possess. It amounts to finding the unknown period a of a function on n -bit integers that is “periodic” under bitwise modulo-2 addition. A more difficult, but much more natural problem is to find the period r of a function f on the integers that is periodic under ordinary addition, satisfying f(x) = f(y) for distinct x and y if and only if x and y differ by an integral multiple of r . Finding the period of such a periodic function turns out to be the key to factoring products of large prime numbers, a mathematically natural problem with quite practical applications.