= Probability of a useful unit in Shor factorization
{title2=$\Pr(r\text{ even},a^{r/2}\not\equiv-1\bmod N)\geq1/2$}
For an odd integer $N$ having at least two distinct prime divisors, choose a uniform unit $a\bmod 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.
Back to article page
