Order finding

Order finding is the problem of determining the smallest positive integer r such that a^r ≡ 1 (mod N) for given integers a and N that are coprime. This apparently obscure number-theoretic problem is the computational core of Shor's algorithm: factorization reduces to order finding, and order finding reduces to period detection via the quantum Fourier transform.

Classically, order finding is as hard as factorization itself — no efficient algorithm is known. This is what makes the quantum reduction so remarkable. Shor's algorithm does not solve factorization directly. It solves factorization by transforming it into order finding, and then solves order finding by transforming it into period finding, and then solves period finding quantum-mechanically. The cascade of reductions — factorization → order finding → period finding → quantum period extraction — is a masterclass in algorithmic design, and it suggests that the difficulty of factorization may be an artifact of classical computational models rather than an intrinsic property of the problem.

The order finding problem also appears in the analysis of pseudorandom number generators, in the study of cyclic groups in abstract algebra, and in the theory of computational number theory.