#[repr(transparent)]pub struct Odd<T: ?Sized>(pub(crate) T);Expand description
Wrapper type for odd integers.
These are frequently used in cryptography, e.g. as a modulus.
Tuple Fields§
§0: TImplementations§
Source§impl<const LIMBS: usize> Odd<Uint<LIMBS>>
impl<const LIMBS: usize> Odd<Uint<LIMBS>>
Sourcepub(crate) const MINIMAL_BINGCD_ITERATIONS: u32
pub(crate) const MINIMAL_BINGCD_ITERATIONS: u32
The minimal number of binary GCD iterations required to guarantee successful completion.
Sourcepub(crate) const fn classic_bingcd(&self, rhs: &Uint<LIMBS>) -> Self
pub(crate) const fn classic_bingcd(&self, rhs: &Uint<LIMBS>) -> Self
Computes gcd(self, rhs), leveraging (a constant time implementation of) the classic
Binary GCD algorithm.
Note: this algorithm is efficient for Uints with relatively few LIMBS.
Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 1. https://eprint.iacr.org/2020/972.pdf
Sourcepub(crate) const fn classic_bingcd_(&self, rhs: &Uint<LIMBS>) -> (Self, Word)
pub(crate) const fn classic_bingcd_(&self, rhs: &Uint<LIMBS>) -> (Self, Word)
Computes gcd(self, rhs), leveraging (a constant time implementation of) the classic
Binary GCD algorithm.
Note: this algorithm is efficient for Uints with relatively few LIMBS.
Ref: Pornin, Optimized Binary GCD for Modular Inversion, Algorithm 1. https://eprint.iacr.org/2020/972.pdf
This method returns a pair consisting of the GCD and the sign of the Jacobi symbol, 0 for positive and 1 for negative.
Sourcepub(crate) const fn classic_bingcd_vartime(&self, rhs: &Uint<LIMBS>) -> Self
pub(crate) const fn classic_bingcd_vartime(&self, rhs: &Uint<LIMBS>) -> Self
Variable time equivalent of Self::classic_bingcd.
Sourcepub(crate) const fn classic_bingcd_vartime_(
&self,
rhs: &Uint<LIMBS>,
) -> (Self, Word)
pub(crate) const fn classic_bingcd_vartime_( &self, rhs: &Uint<LIMBS>, ) -> (Self, Word)
Variable time equivalent of Self::classic_bingcd_.
Sourcepub(crate) const fn optimized_bingcd(&self, rhs: &Uint<LIMBS>) -> Self
pub(crate) const fn optimized_bingcd(&self, rhs: &Uint<LIMBS>) -> Self
Computes gcd(self, rhs), leveraging the optimized Binary GCD algorithm.
Note: this algorithm becomes more efficient than the classical algorithm for Uints with
relatively many LIMBS. A best-effort threshold is presented in Self::bingcd.
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
Sourcepub(crate) const fn optimized_bingcd_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>(
&self,
rhs: &Uint<LIMBS>,
batch_max: u32,
) -> (Self, Word)
pub(crate) const fn optimized_bingcd_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>( &self, rhs: &Uint<LIMBS>, batch_max: u32, ) -> (Self, Word)
Computes gcd(self, rhs), leveraging the optimized Binary 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 summarizingselfandrhsfor the inner loop. TheKtop bits andKleast significant bits are selected. It is recommended to keepKclose 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.
This method returns a pair consisting of the GCD and the sign of the Jacobi symbol, 0 for positive and 1 for negative.
Sourcepub(crate) const fn optimized_bingcd_vartime(&self, rhs: &Uint<LIMBS>) -> Self
pub(crate) const fn optimized_bingcd_vartime(&self, rhs: &Uint<LIMBS>) -> Self
Variable time equivalent of Self::optimized_bingcd.
Sourcepub(crate) const fn optimized_bingcd_vartime_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>(
&self,
rhs: &Uint<LIMBS>,
batch_max: u32,
) -> (Self, Word)
pub(crate) const fn optimized_bingcd_vartime_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>( &self, rhs: &Uint<LIMBS>, batch_max: u32, ) -> (Self, Word)
Variable time equivalent of Self::optimized_bingcd_.
Source§impl<const LIMBS: usize> Odd<Uint<LIMBS>>
impl<const LIMBS: usize> Odd<Uint<LIMBS>>
Sourceconst MIN_BINXGCD_ITERATIONS: u32
const MIN_BINXGCD_ITERATIONS: u32
The minimal number of binary GCD iterations required to guarantee successful completion.
Sourcepub(crate) const fn binxgcd_nz(
&self,
rhs: &NonZeroUint<LIMBS>,
) -> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>
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.
Sourcepub(crate) const fn binxgcd_odd(
&self,
rhs: &Self,
) -> RawXgcdOutput<LIMBS, PatternMatrix<LIMBS>>
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).
Sourcepub(crate) const fn classic_binxgcd(
&self,
rhs: &Self,
) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>
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.
Sourcepub(crate) const fn optimized_binxgcd(
&self,
rhs: &Self,
) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>
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.
Sourcepub(crate) const fn optimized_binxgcd_<const K: u32, const LIMBS_K: usize, const LIMBS_2K: usize>(
&self,
rhs: &Self,
) -> RawXgcdOutput<LIMBS, DividedPatternMatrix<LIMBS>>
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 summarizingselfandrhsfor the inner loop. TheK+1top bits andK-1least significant bits are selected. It is recommended to keepKclose 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.
Sourcepub(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)
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.
Source§impl<const LIMBS: usize> Odd<Int<LIMBS>>
impl<const LIMBS: usize> Odd<Int<LIMBS>>
Sourcepub const fn gcd_unsigned(&self, rhs: &Uint<LIMBS>) -> Odd<Uint<LIMBS>>
pub const fn gcd_unsigned(&self, rhs: &Uint<LIMBS>) -> Odd<Uint<LIMBS>>
Compute the greatest common divisor of self and rhs.
Sourcepub const fn gcd_unsigned_vartime(&self, rhs: &Uint<LIMBS>) -> OddUint<LIMBS>
pub const fn gcd_unsigned_vartime(&self, rhs: &Uint<LIMBS>) -> OddUint<LIMBS>
Compute the greatest common divisor of self and rhs.
Executes in variable time w.r.t. all input parameters.
Source§impl<const LIMBS: usize> Odd<Uint<LIMBS>>
impl<const LIMBS: usize> Odd<Uint<LIMBS>>
Sourcepub const fn from_be_hex(hex: &str) -> Self
pub const fn from_be_hex(hex: &str) -> Self
Sourcepub const fn from_le_hex(hex: &str) -> Self
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.
Sourcepub const fn as_uint_ref(&self) -> &OddUintRef
pub const fn as_uint_ref(&self) -> &OddUintRef
Borrow this OddUint as a &OddUintRef.
Source§impl Odd<UintRef>
impl Odd<UintRef>
Sourcepub const fn to_uint_resize<const T: usize>(&self) -> Odd<Uint<T>>
pub const fn to_uint_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.
Source§impl Odd<BoxedUint>
impl Odd<BoxedUint>
Sourcepub const fn as_uint_ref(&self) -> &OddUintRef
pub const fn as_uint_ref(&self) -> &OddUintRef
Borrow this OddBoxedUint as a &OddUintRef.
Source§impl<const LIMBS: usize> Odd<Uint<LIMBS>>
impl<const LIMBS: usize> Odd<Uint<LIMBS>>
Sourcepub const fn gcd_unsigned(&self, rhs: &Uint<LIMBS>) -> Self
pub const fn gcd_unsigned(&self, rhs: &Uint<LIMBS>) -> Self
Compute the greatest common divisor of self and rhs.
Sourcepub const fn gcd_unsigned_vartime(&self, rhs: &Uint<LIMBS>) -> Self
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.
Sourcepub const fn xgcd(&self, rhs: &Self) -> XgcdOutput<LIMBS, OddUint<LIMBS>>
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).
Source§impl<const LIMBS: usize> Odd<Uint<LIMBS>>
impl<const LIMBS: usize> Odd<Uint<LIMBS>>
Sourcepub(crate) const fn invert_mod_precision(&self) -> Uint<LIMBS>
pub(crate) const fn invert_mod_precision(&self) -> Uint<LIMBS>
Compute a full-width quadratic inversion, self^-1 mod 2^Self::BITS.
Sourcepub(crate) const fn invert_mod2k_vartime(&self, k: u32) -> Uint<LIMBS>
pub(crate) const fn invert_mod2k_vartime(&self, k: u32) -> Uint<LIMBS>
Compute a quadratic inversion, self^-1 mod 2^k where k <= Self::BITS.
This method is variable-time in k only.
Source§impl Odd<UintRef>
impl Odd<UintRef>
Sourcepub const fn invert_mod_u64(&self) -> u64
pub const fn invert_mod_u64(&self) -> u64
Returns the multiplicative inverse of the argument modulo 2^64. The implementation is based on the Hurchalla’s method for computing the multiplicative inverse modulo a power of two.
For better understanding the implementation, the following paper is recommended: J. Hurchalla, “An Improved Integer Multiplicative Inverse (modulo 2^w)”, https://arxiv.org/pdf/2204.limbs4342.pdf
Variable time with respect to the number of words in value, however that number will be
fixed for a given integer size.
Source§impl Odd<BoxedUint>
impl Odd<BoxedUint>
Sourcepub(crate) fn invert_mod_precision(&self) -> BoxedUint
pub(crate) fn invert_mod_precision(&self) -> BoxedUint
Compute a full-width quadratic inversion, self^-1 mod 2^bits_precision().
Sourcepub(crate) fn invert_mod2k_vartime(&self, k: u32) -> BoxedUint
pub(crate) fn invert_mod2k_vartime(&self, k: u32) -> BoxedUint
Compute a quadratic inversion, self^-1 mod 2^k where k <= bits_precision().
This method is variable-time in k only.
Trait Implementations§
Source§impl AsRef<Odd<UintRef>> for OddBoxedUint
Available on crate feature alloc only.
impl AsRef<Odd<UintRef>> for OddBoxedUint
alloc only.Source§fn as_ref(&self) -> &OddUintRef
fn as_ref(&self) -> &OddUintRef
Source§impl<const LIMBS: usize> AsRef<Odd<UintRef>> for OddUint<LIMBS>
impl<const LIMBS: usize> AsRef<Odd<UintRef>> for OddUint<LIMBS>
Source§fn as_ref(&self) -> &OddUintRef
fn as_ref(&self) -> &OddUintRef
Source§impl<T> CtAssign for Odd<T>where
T: CtAssign,
impl<T> CtAssign for Odd<T>where
T: CtAssign,
Source§impl<T> CtAssignSlice for Odd<T>where
T: CtAssignSlice,
impl<T> CtAssignSlice for Odd<T>where
T: CtAssignSlice,
Source§fn ct_assign_slice(dst: &mut [Self], src: &[Self], choice: Choice)
fn ct_assign_slice(dst: &mut [Self], src: &[Self], choice: Choice)
Source§impl<T> CtEqSlice for Odd<T>where
T: CtEq,
impl<T> CtEqSlice for Odd<T>where
T: CtEq,
Source§fn ct_eq_slice(a: &[Self], b: &[Self]) -> Choice
fn ct_eq_slice(a: &[Self], b: &[Self]) -> Choice
a is equal to b in constant-time.Source§fn ct_ne_slice(a: &[Self], b: &[Self]) -> Choice
fn ct_ne_slice(a: &[Self], b: &[Self]) -> Choice
a is NOT equal to b in constant-time.Source§impl<T> Mul for Odd<T>where
T: Mul<T, Output = T>,
Any odd integer multiplied by another odd integer is definitionally odd.
impl<T> Mul for Odd<T>where
T: Mul<T, Output = T>,
Any odd integer multiplied by another odd integer is definitionally odd.
Source§impl<T: Ord + ?Sized> Ord for Odd<T>
impl<T: Ord + ?Sized> Ord for Odd<T>
Source§impl PartialOrd<Odd<BoxedUint>> for BoxedUint
Available on crate feature alloc only.
impl PartialOrd<Odd<BoxedUint>> for BoxedUint
alloc only.Source§impl<const LIMBS: usize> PartialOrd<Odd<Uint<LIMBS>>> for Uint<LIMBS>
impl<const LIMBS: usize> PartialOrd<Odd<Uint<LIMBS>>> for Uint<LIMBS>
Source§impl<T: PartialOrd + ?Sized> PartialOrd for Odd<T>
impl<T: PartialOrd + ?Sized> PartialOrd for Odd<T>
Source§impl<const LIMBS: usize> Random for Odd<Uint<LIMBS>>
Available on crate feature rand_core only.
impl<const LIMBS: usize> Random for Odd<Uint<LIMBS>>
rand_core only.