The last step of Shor's algorithm is pure number theory. Suppose a^r \bmod N = 1 for some even r, and let x = a^{r/2} \bmod N. Then x^2 \bmod N = 1, so N divides x^2 - 1 = (x - 1)(x + 1). If x is neither 1 nor N - 1, then N divides neither factor on its own, so \gcd(x - 1, N) and \gcd(x + 1, N) are both factors of N strictly between 1 and N.
Write split_with_period(a, N, r) that returns:
Noneifris odd;Noneif x = a^{r/2} \bmod N is 1 or N - 1 (no factor comes out);- otherwise the pair
(g1, g2)of \gcd(x - 1, N) and \gcd(x + 1, N), smaller first.
The tests promise a^r \bmod N = 1, but r need not be the smallest such power. Numbers go up to 10^{12}, and so do the powers: use pow(a, e, N) and math.gcd.
Examples
Input: a = 7, N = 15, r = 4
Output: (3, 5)
Explanation: x = 7**2 mod 15 = 4; gcd(3, 15) = 3 and gcd(5, 15) = 5.
Input: a = 14, N = 15, r = 2
Output: None
Explanation: x = 14 = N - 1. gcd(13, 15) = 1 and gcd(15, 15) = 15: no proper factor.
Input: a = 2, N = 21, r = 6
Output: (3, 7)
Explanation: x = 2**3 = 8; gcd(7, 21) = 7 and gcd(9, 21) = 3.
Constraints
3 <= N <= 10**13;2 <= a < N,gcd(a, N) == 1;1 <= r <= 10**12;pow(a, r, N) == 1
Goals
- Turn a period of $a^x \bmod N$ into factors of $N$ with two gcds
- Recognise the cases where a period gives no factor: odd $r$, $a^{r/2} \equiv \pm 1$