Skip to main content

bingcd_step

Function bingcd_step 

Source
pub(super) const fn bingcd_step<const LIMBS: usize>(
    a: &mut Uint<LIMBS>,
    b: &mut Uint<LIMBS>,
) -> (Choice, Choice, Word)
Expand description

Binary GCD update step.

This is a condensed, constant time execution of the following algorithm:

if a mod 2 == 1
   if a < b
       (a, b) ← (b, a)
   a ← a - b
a ← a/2

Note: assumes b to be odd. Might yield an incorrect result if this is not the case.

Ref: Pornin, Algorithm 1, L3-9, https://eprint.iacr.org/2020/972.pdf.