Struct SafeGcdInverter

pub struct SafeGcdInverter<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> { /* private fields */ }

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

Implementations

impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>

pub const fn new( modulus: &Odd<Uint<SAT_LIMBS>>, adjuster: &Uint<SAT_LIMBS>, ) -> Self

Creates the inverter for specified modulus and adjusting parameter.

Modulus must be odd. Returns None if it is not.

pub const fn inv( &self, value: &Uint<SAT_LIMBS>, ) -> ConstCtOption<Uint<SAT_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 inv_vartime( &self, value: &Uint<SAT_LIMBS>, ) -> ConstCtOption<Uint<SAT_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 SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Clone for SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>

fn clone(&self) -> SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Debug for SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>

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

Formats the value using the given formatter.

impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize> Inverter for SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>

type Output = Uint<SAT_LIMBS>

Output of an inversion.

fn invert(&self, value: &Uint<SAT_LIMBS>) -> CtOption<Self::Output>

Compute a modular inversion, returning None if the result is undefined (i.e. if value is zero or isn’t prime relative to the modulus).

fn invert_vartime(&self, value: &Uint<SAT_LIMBS>) -> CtOption<Self::Output>

Compute a modular inversion, returning None if the result is undefined (i.e. if value is zero or isn’t prime relative to the modulus).