pub fn gcd_inner<const NUM_ROUNDS: usize>(
a: &mut u64,
b: &mut u64,
) -> (i64, i64, i64, i64)Expand description
Inner loop of the deferred GCD algorithm.
See: https://eprint.iacr.org/2020/972.pdf for more information.
This is basically a mini GCD algorithm which builds up a transformation to apply to the larger numbers in the main loop. The key point is that this small loop only uses u64s, subtractions and bit shifts, which are very fast operations.
The bottom NUM_ROUNDS bits of a and b should match the bottom NUM_ROUNDS bits of
the corresponding big-ints and the top NUM_ROUNDS + 2 should match the top bits including
zeroes if the original numbers have different sizes.