Struct BYInverter

pub struct BYInverter<const L: usize> { /* private fields */ }

Type of the 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 L: usize> BYInverter<L>

pub const fn new(modulus: &[u64], adjuster: &[u64]) -> Self

Creates the inverter for specified modulus and adjusting parameter

pub fn invert<const S: usize>(&self, value: &[u64]) -> Option<[u64; S]>

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