= Candidate-denominator gcd post-processing
{title2=$d_\pm=\gcd(a^{q/2}\pm1,N)$}
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\equiv1$ before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.
Back to article page
