Struct RawXgcdOutput 

pub(crate) struct RawXgcdOutput<const LIMBS: usize, MATRIX> {
    gcd: OddUint<LIMBS>,
    matrix: MATRIX,
}

Container for the raw output of the Binary XGCD algorithm.

Fields

gcd: OddUint<LIMBS>

matrix: MATRIX

Implementations

impl<const LIMBS: usize> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>

pub(crate) const fn divide(self) -> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>

Divide self.matrix.inner by 2^self.matrix.k, allowing us to simplify inner from a DividedPatternMatrix to a PatternMatrix.

The performed divisions are modulo lhs/gcd and rhs/gcd to maintain the correctness of the XGCD state.

This operation is ‘fast’ since it only applies the division to the top row of the matrix. This is allowed since it is assumed that self.matrix * (lhs, rhs) = (gcd, 0); dividing the bottom row of the matrix by a constant has no impact since its inner-product with the input vector is zero.

Executes in variable time w.r.t. k_upper_bound.

impl<const LIMBS: usize> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>

pub(crate) const fn gcd(&self) -> OddUint<LIMBS>

Obtain the gcd.

pub(crate) const fn bezout_coefficients(&self) -> (Int<LIMBS>, Int<LIMBS>)

Obtain the bezout coefficients (x, y) such that lhs * x + rhs * y = gcd.

pub(crate) const fn quotients(&self) -> (Uint<LIMBS>, Uint<LIMBS>)

Obtain the quotients lhs/gcd and rhs/gcd from matrix.