Skip to main content

expand_invert_mod2k

Function expand_invert_mod2k 

Source
pub(crate) const fn expand_invert_mod2k(
    a: &Odd<UintRef>,
    buf: &mut UintRef,
    k: usize,
    scratch: (&mut UintRef, &mut UintRef),
)
Expand description

Perform a modified recursive Hensel quadratic modular inversion to calculate a^-1 mod w^p given a^-1 mod w^k where w is the size of Limb. For reference see Algorithm 2: https://arxiv.org/pdf/1209.6626

p is determined by the length of the in-out buffer buf, which must be pre-populated with a^-1 mod w^k (constituting k limbs).

This method uses recursion, but the maximum depth is limited by the bit-width of the number of limbs being inverted (p).

This method is variable time in k and p only.

scratch must be a pair of mutable buffers, each with capacity at least p.