Type Alias OddUint 

pub type OddUint<const LIMBS: usize> = Odd<Uint<LIMBS>>;

Odd unsigned integer.

Aliased Type

#[repr(transparent)]
pub struct OddUint<const LIMBS: usize>(pub(crate) Uint<LIMBS>);

Tuple Fields

0: Uint<LIMBS>

Implementations

impl<const LIMBS: usize> OddUint<LIMBS>

const fn half_mod(q: &Self) -> Self

Compute 1/2 mod q.

const fn mul_add_div2k( &self, b: Limb, addend: &Uint<LIMBS>, k: u32, ) -> Uint<LIMBS>

Compute ((self * b) + addend) / 2^k

impl<const LIMBS: usize> OddUint<LIMBS>

const MIN_BINXGCD_ITERATIONS: u32

The minimal number of binary GCD iterations required to guarantee successful completion.

pub(crate) const fn binxgcd_nz( &self, rhs: &NonZeroUint<LIMBS>, ) -> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>

Given (self, rhs), computes (g, x, y) s.t. self * x + rhs * y = g = gcd(self, rhs), leveraging the Binary Extended GCD algorithm.

pub(crate) const fn binxgcd_odd( &self, rhs: &Self, ) -> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>

Execute the classic Extended GCD algorithm.

Given (self, rhs), computes (g, x, y) s.t. self * x + rhs * y = g = gcd(self, rhs).

pub(crate) const fn classic_binxgcd( &self, rhs: &Self, ) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>

Execute the classic Binary Extended GCD algorithm.

Given (self, rhs), computes (g, x, y) s.t. self * x + rhs * y = g = gcd(self, rhs).

Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 1. https://eprint.iacr.org/2020/972.pdf.

pub(crate) const fn optimized_binxgcd( &self, rhs: &Self, ) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>

Given (self, rhs), computes (g, x, y) s.t. self * x + rhs * y = g = gcd(self, rhs), leveraging the Binary Extended GCD algorithm.

Warning: self and rhs must be contained in an U128 or larger.

Note: this algorithm becomes more efficient than the classical algorithm for Uints with relatively many LIMBS. A best-effort threshold is presented in [Self::binxgcd_].

Note: the full algorithm has an additional parameter; this function selects the best-effort value for this parameter. You might be able to further tune your performance by calling the Self::optimized_bingcd_ function directly.

Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 2. https://eprint.iacr.org/2020/972.pdf.

pub(crate) const fn optimized_binxgcd_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>( &self, rhs: &Self, ) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>

Given (self, rhs), computes (g, x, y), s.t. self * x + rhs * y = g = gcd(self, rhs), leveraging the optimized Binary Extended GCD algorithm.

Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 2. https://eprint.iacr.org/2020/972.pdf

In summary, the optimized algorithm does not operate on self and rhs directly, but instead of condensed summaries that fit in few registers. Based on these summaries, an update matrix is constructed by which self and rhs are updated in larger steps.

This function is generic over the following three values:

• K: the number of bits used when summarizing self and rhs for the inner loop. The K+1 top bits and K-1 least significant bits are selected. It is recommended to keep K close to a (multiple of) the number of bits that fit in a single register.
• LIMBS_K: should be chosen as the minimum number s.t. Uint::<LIMBS>::BITS ≥ K,
• LIMBS_2K: should be chosen as the minimum number s.t. Uint::<LIMBS>::BITS ≥ 2K.

pub(super) const fn partial_binxgcd<const UPDATE_LIMBS: usize>( &self, rhs: &Uint<LIMBS>, iterations: u32, halt_at_zero: Choice, ) -> (Self, Uint<LIMBS>, DividedPatternMatrix<UPDATE_LIMBS>, Word)

Executes the optimized Binary GCD inner loop.

Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 2. https://eprint.iacr.org/2020/972.pdf.

The function outputs the reduced values (a, b) for the input values (self, rhs) as well as the matrix that yields the former two when multiplied with the latter two.

Note: this implementation deviates slightly from the paper, in that it can be instructed to “run in place” (i.e., execute iterations that do nothing) once a becomes zero. This is done by passing a truthy halt_at_zero.

The function executes in time variable in iterations.

impl<const LIMBS: usize> OddUint<LIMBS>

pub const fn from_be_hex(hex: &str) -> Self

Create a new OddUint from the provided big endian hex string.

Panics

• if the hex is malformed or not zero-padded accordingly for the size.
• if the value is even.

pub const fn from_le_hex(hex: &str) -> Self

Create a new Odd<Uint<LIMBS>> from the provided little endian hex string.

Panics

• if the hex is malformed or not zero-padded accordingly for the size.
• if the value is even.

pub const fn as_uint_ref(&self) -> &OddUintRef

Borrow this OddUint as a &OddUintRef.

pub const fn resize<const T: usize>(&self) -> Odd<Uint<T>>

Construct an Odd<Uint<T>> from the unsigned integer value, truncating the upper bits if the value is too large to be represented.

impl<const LIMBS: usize> OddUint<LIMBS>

pub const fn gcd_unsigned(&self, rhs: &Uint<LIMBS>) -> Self

Compute the greatest common divisor of self and rhs.

pub const fn gcd_unsigned_vartime(&self, rhs: &Uint<LIMBS>) -> Self

Compute the greatest common divisor of self and rhs.

Executes in variable time w.r.t. all input parameters.

pub const fn xgcd(&self, rhs: &Self) -> XgcdOutput<LIMBS, OddUint<LIMBS>>

Execute the Extended GCD algorithm.

Given (self, rhs), computes (g, x, y) s.t. self * x + rhs * y = g = gcd(self, rhs).

Trait Implementations

impl<const LIMBS: usize> AsRef<Odd<UintRef>> for OddUint<LIMBS>

fn as_ref(&self) -> &OddUintRef

Converts this type into a shared reference of the (usually inferred) input type.

impl<const LIMBS: usize> Gcd<NonZero<Uint<LIMBS>>> for OddUint<LIMBS>

type Output = Odd<Uint<LIMBS>>

Output type.

fn gcd(&self, rhs: &NonZeroUint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs.

fn gcd_vartime(&self, rhs: &NonZeroUint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs in variable time.

impl<const LIMBS: usize> Gcd<Uint<LIMBS>> for OddUint<LIMBS>

type Output = Odd<Uint<LIMBS>>

Output type.

fn gcd(&self, rhs: &Uint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs.

fn gcd_vartime(&self, rhs: &Uint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs in variable time.

impl<const LIMBS: usize> Gcd for OddUint<LIMBS>

type Output = Odd<Uint<LIMBS>>

Output type.

fn gcd(&self, rhs: &OddUint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs.

fn gcd_vartime(&self, rhs: &OddUint<LIMBS>) -> Self::Output

Compute the greatest common divisor of self and rhs in variable time.

impl<const LIMBS: usize> Xgcd for OddUint<LIMBS>

type Output = XgcdOutput<LIMBS, Odd<Uint<LIMBS>>>

Output type.

fn xgcd(&self, rhs: &OddUint<LIMBS>) -> Self::Output

Compute the extended greatest common divisor of self and rhs.

fn xgcd_vartime(&self, rhs: &OddUint<LIMBS>) -> Self::Output

Compute the extended greatest common divisor of self and rhs in variable time.