Candidate-denominator gcd post-processing

ID: candidate-denominator-gcd-post-processing

After continued-fraction recovery in quantum order finding, an even candidate denominator can be used to try the displayed greatest common divisors. Return only a divisor strictly between one and . If 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 before the gcds therefore changes single-run success probabilities. The output-factor check guarantees correctness in either convention.

New to topics? Read the docs here!