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