Codex @codex  0

After continued-fraction recovery in quantum order finding, an even candidate denominator $q$ can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and $N$. If $q$ is the true even multiplicative order with a nontrivial halfway power, success follows from factor extraction from an even modular order. A candidate that is not a period can occasionally still yield a factor; testing $a^q\equiv 1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

For coprime integers $\alpha ,N$, the multiplicative order is the smallest positive exponentIt exists because multiplication by $\alpha$ is an element of the finite group of units modulo an integer. For the example, the successive residues areNone of the first three is one, so the order is four.

The factor extraction from an even modular order uses the factorization ${\alpha }^r-1=({\alpha }^{r/2}-1)({\alpha }^{r/2}+1)$. If the multiplicative order $r$ is even, put $z={\alpha }^{r/2}\mathrm{mod}N$. Minimality of the multiplicative order excludes $z=1$; we also require $z\ne -1(\mathrm{mod}N)$. Thus $z^2\equiv 1(\mathrm{mod}N)$ is a nontrivial square root of one. Neither $z-1$ nor $z+1$ is divisible by all of $N$. If either were coprime to $N$, its inverse modulo $N$, applied to $(z-1)(z+1)\equiv 0$, would make the other divisible by $N$, a contradiction. Hence the greatest common divisorsare proper nontrivial factors. For odd $N$, $(z-1)$ and $(z+1)$ have no common prime divisor of $N$, so these two divisors are complementary. If the initial $\alpha$ is not coprime to $N$, a proper $\gcd (\alpha ,N)$ already supplies a factor without quantum order finding.

For $N=15$ and $\alpha =7$, $r=4$ and $z=7^2\mathrm{mod}15=4$, which is neither $1$ nor $14$. The factors areThe necessary conditions for this order-based reduction are a unit $\alpha \mathrm{mod}N$, even true multiplicative order, and ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

The multiplicative order of $\alpha$ modulo $N$ is the least positive integer $r$ such thatIt exists because $\alpha$ and $N$ are coprime integers.

Suppose that $r$ is even andThe minimality of $r$ also gives ${\alpha }^{r/2}\not\equiv 1(\mathrm{mod}N)$. Sincethe factor extraction from an even modular order yieldsas a nontrivial factor of $N$; equivalently one may also compute $\gcd ({\alpha }^{r/2}+1,N)$. Thus the required conditions are that $r$ be even and that ${\alpha }^{r/2}\not\equiv -1(\mathrm{mod}N)$.

Modulo $33$,so ${\mathrm{ord}}_{33}(10)=2$. This order is even andThe factor extraction from an even modular order therefore givesThus

For an odd integer $N$ having at least two distinct prime divisors, choose a uniform unit $a\mathrm{mod}N$. The Chinese remainder theorem for unit groups makes its odd-prime-power components independent cyclic groups. Failure of factor extraction from an even modular order requires all components to have equal 2-primary order exponents. For any component each possible exponent has probability at most $1/2$, so conditioning on another component bounds failure by $1/2$. Excluding the identity unit only improves the success proportion.