Module period 

The period / order seam — the classical shell of Shor’s algorithm

The multiplicative structure of ℤ/N hides a Fourier object: the map x ↦ aˣ mod N is periodic, with period r = ord_N(a) (the multiplicative order). That period is the additive shadow of the multiplicative group, and it reveals the factorization: if r is even and a^{r/2} ≢ ±1 (mod N), then a^{r/2} is a nontrivial square root of 1, so gcd(a^{r/2} − 1, N) and gcd(a^{r/2} + 1, N) split N. Factoring reduces to order-finding.

The catch — and the whole point — is that classically, finding the order is not easier than factoring. Baby-step-giant-step does it in O(√r), exponential in the bit length. Shor’s quantum algorithm replaces this scan with a quantum Fourier transform that reads the period off in polynomial time. So this module is the honest classical primitive: the reduction is exact and the order-finder is correct, but the speed lives on the quantum side of the seam. It is also a first-class number-theory primitive in its own right (order-finding underlies discrete-log and group-structure computations).

Functions

factor_from_order

Split n from a known order r of a: if r is even and a^{r/2} is a nontrivial square root of 1 (≢ ±1), then gcd(a^{r/2} ± 1, n) is a proper factor. None when the order is odd or the root is trivial (±1) — the ~50% of the time a fresh a is needed.

factor_via_order

Factoring via order-finding — the classical shell of Shor’s algorithm. Draw bases a, find each order (bounded by bound), and split n when the order is even with a nontrivial root. None if no trial succeeded within tries/bound. Classically O(√order) per base (exponential in bit length); this is exactly the step Shor’s quantum Fourier transform makes polynomial.

multiplicative_order

The multiplicative order of a modulo n — the least r > 0 with aʳ ≡ 1 (mod n) — by baby-step-giant-step, searching orders up to bound. None if gcd(a, n) ≠ 1 (no order) or the order exceeds bound. Runs in O(√bound) field multiplications.