Struct SafeGcdInverter 

pub(crate) struct SafeGcdInverter<const LIMBS: usize> {
    pub(super) modulus: Odd<Uint<LIMBS>>,
    inverse: u64,
    adjuster: Uint<LIMBS>,
}

Modular multiplicative inverter based on the Bernstein-Yang method.

The inverter can be created for a specified modulus M and adjusting parameter A to compute the adjusted multiplicative inverses of positive integers, i.e. for computing (1 / x) * A (mod M) for a positive integer x.

The adjusting parameter allows computing the multiplicative inverses in the case of using the Montgomery representation for the input or the expected output. If R is the Montgomery factor, the multiplicative inverses in the appropriate representation can be computed provided that the value of A is chosen as follows:

• A = 1, if both the input and the expected output are in the standard form
• A = R^2 mod M, if both the input and the expected output are in the Montgomery form
• A = R mod M, if either the input or the expected output is in the Montgomery form, but not both of them

The public methods of this type receive and return unsigned big integers as arrays of 64-bit chunks, the ordering of which is little-endian. Both the modulus and the integer to be inverted should not exceed 2 ^ (62 * L - 64).

For better understanding the implementation, the following resources are recommended:

• D. Bernstein, B.-Y. Yang, “Fast constant-time gcd computation and modular inversion”, https://gcd.cr.yp.to/safegcd-20190413.pdf
• P. Wuille, “The safegcd implementation in libsecp256k1 explained”, https://github.com/bitcoin-core/secp256k1/blob/master/doc/safegcd_implementation.md

Fields

modulus: Odd<Uint<LIMBS>>

Modulus

inverse: u64

Multiplicative inverse of the modulus modulo 2^62

adjuster: Uint<LIMBS>

Adjusting parameter (see toplevel documentation).

Implementations

impl<const LIMBS: usize> SafeGcdInverter<LIMBS>

pub(crate) const fn new_with_inverse( modulus: &Odd<Uint<LIMBS>>, inverse: U64, adjuster: &Uint<LIMBS>, ) -> Self

pub const fn invert(&self, value: &Uint<LIMBS>) -> CtOption<Uint<LIMBS>>

Returns either the adjusted modular multiplicative inverse for the argument or None depending on invertibility of the argument, i.e. its coprimality with the modulus.

pub const fn invert_vartime(&self, value: &Uint<LIMBS>) -> CtOption<Uint<LIMBS>>

Returns either the adjusted modular multiplicative inverse for the argument or None depending on invertibility of the argument, i.e. its coprimality with the modulus.

This version is variable-time with respect to value.

Trait Implementations

impl<const LIMBS: usize> Clone for SafeGcdInverter<LIMBS>

fn clone(&self) -> SafeGcdInverter<LIMBS>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const LIMBS: usize> Debug for SafeGcdInverter<LIMBS>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.