Module shor 

Shor’s period-finding subroutine.

The quantum heart of Shor’s factoring algorithm is order finding: given a base a coprime to N, find the multiplicative order r — the least positive integer with a^r ≡ 1 (mod N). Quantum phase estimation on the modular-multiplication unitary U_a|y⟩ = |a·y mod N⟩ yields a phase φ ≈ k/r, and the classical continued-fraction expansion of φ recovers the denominator r. Once r is known (and even, with a^{r/2} ≢ −1), the factors of N are gcd(a^{r/2} ± 1, N).

This module provides:

• mod_exp — fast modular exponentiation by repeated squaring.
• gcd — binary Euclidean greatest common divisor.
• continued_fraction_convergents — the convergents p_i/q_i of a real.
• order_finding — state-vector phase estimation of U_a plus classical continued-fraction post-processing.
• shor_factor — the end-to-end reduction from r to a non-trivial factor of N.

The counting register is little-endian (qubit i carries weight 2^i), matching crate::fourier::qft.

Structs

OrderFindingResult

Outcome of order_finding.

ShorResult

Outcome of shor_factor.

Functions

classical_order

Brute-force the multiplicative order of a modulo n (classical reference).

continued_fraction_convergents

Compute the continued-fraction convergents (p_i, q_i) of value ∈ [0, 1), stopping once a denominator exceeds max_denominator or the expansion terminates.

factor_from_order

Classical reduction from a period r (order of base mod n) to a factor.

gcd

Binary-Euclidean greatest common divisor of a and b.

mod_exp

Fast modular exponentiation base^exp mod modulus via repeated squaring.

order_finding

Quantum order finding for the unitary U_a|y⟩ = |a·y mod N⟩.

shor_factor

End-to-end Shor factoring driver using quantum order finding.