Shor's algorithm factors a number N by finding the order of some a (with \gcd(a, N) = 1): the smallest r \ge 1 with a^r \bmod N = 1. Its quantum part is phase estimation with t counting qubits on the gate |w\rangle \mapsto |a\,w \bmod N\rangle, whose eigenphases are \varphi = s/r for s = 0, 1, \dots, r-1. A run returns an outcome y in 0..2^t-1 with y/2^t \approx s/r for an unknown s. The classical half recovers r from y.
Use exactly this rule:
- Expand y/2^t as a continued fraction: start from z = y/2^t; the terms are c_0 = \lfloor z\rfloor, then z \leftarrow 1/(z - c_0) and repeat until z is a whole number. Cutting after each term gives the convergents h_k/k_k in lowest terms, the last one being y/2^t reduced. They follow h_k = c_k h_{k-1} + h_{k-2}, k_k = c_k k_{k-1} + k_{k-2} with h_{-1} = 1, h_{-2} = 0, k_{-1} = 0, k_{-2} = 1.
- Take the last convergent whose denominator is less than N; its denominator is the candidate r. For y = 0 the only convergent is 0/1, so the candidate is 1.
- If a^r \bmod N = 1, return r; otherwise return
None.
Write period_guess(y, t, a, N) that applies this rule. Use exact integers (floats break the expansion) and pow(a, r, N) for the check.
Examples
Input: y = 85, t = 9, a = 2, N = 21
Output: 6
Explanation: convergents of 85/512: 0/1, 1/6, 42/253, 85/512. The last with denominator < 21 is 1/6,
and 2**6 = 64 = 3 * 21 + 1.
Input: y = 171, t = 9, a = 2, N = 21
Output: None
Explanation: convergents 0/1, 1/2, 1/3, 171/512. Candidate 3, but 2**3 mod 21 = 8. The outcome was
near s/r = 2/6 = 1/3, and the shared factor hid part of the period.
Input: y = 0, t = 9, a = 2, N = 21
Output: None
Constraints
3 <= N <= 10**6;2 <= a < Nwithgcd(a, N) == 1;1 <= t <= 48;0 <= y < 2**t
Goals
- Turn a phase-estimation outcome into a candidate period with continued fractions
- Pick the right convergent with a precise rule and verify the candidate with `pow(a, r, N)`