pub struct Uint<const BITS: usize, const LIMBS: usize> {
pub limbs: [u64; LIMBS],
}Expand description
A fixed-size unsigned integer of BITS bits stored in LIMBS 64-bit limbs.
LIMBS must be ceil(BITS / 64) (checked at compile time). Values are
little-endian. When BITS is not a multiple of 64 the caller must keep the
unused high bits of the top limb zero; the decoding helpers do this
automatically but Uint::from_limbs does not.
Fields§
§limbs: [u64; LIMBS]Implementations§
Source§impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS>
impl<const BITS: usize, const LIMBS: usize> Uint<BITS, LIMBS>
pub const ZERO: Self
pub const ONE: Self
pub const MAX: Self
Sourcepub const fn from_limbs(limbs: [u64; LIMBS]) -> Self
pub const fn from_limbs(limbs: [u64; LIMBS]) -> Self
Builds a value directly from its little-endian limbs.
This is a low-level escape hatch: when BITS is not a multiple of 64
the caller is responsible for ensuring the unused high bits of the top
limb are zero. The decoding helpers (Self::from_be_slice,
Self::from_le_slice, Self::from_str_radix) enforce this for you.
Sourcepub fn from_be_slice(bytes: &[u8]) -> Self
pub fn from_be_slice(bytes: &[u8]) -> Self
Decodes LIMBS * 8 big-endian bytes.
The expected byte length is the limb-aligned width ceil(BITS / 64) * 8
bytes, which equals BITS / 8 whenever BITS is a multiple of 64. Any
bits at or above BITS are cleared.
§Panics
Panics if bytes.len() != LIMBS * 8.
Sourcepub fn from_le_slice(bytes: &[u8]) -> Self
pub fn from_le_slice(bytes: &[u8]) -> Self
Decodes LIMBS * 8 little-endian bytes.
The expected byte length is the limb-aligned width ceil(BITS / 64) * 8
bytes, which equals BITS / 8 whenever BITS is a multiple of 64. Any
bits at or above BITS are cleared.
§Panics
Panics if bytes.len() != LIMBS * 8.
Sourcepub fn to_be_bytes(&self) -> Vec<u8> ⓘ
pub fn to_be_bytes(&self) -> Vec<u8> ⓘ
Encodes the value as LIMBS * 8 big-endian bytes.
Allocates a Vec. Prefer Self::to_be_bytes_fixed in allocation-free
contexts.
Sourcepub fn to_le_bytes(&self) -> Vec<u8> ⓘ
pub fn to_le_bytes(&self) -> Vec<u8> ⓘ
Encodes the value as LIMBS * 8 little-endian bytes.
Allocates a Vec. Prefer Self::to_le_bytes_fixed in allocation-free
contexts.
Sourcepub fn to_be_bytes_fixed<const N: usize>(&self) -> [u8; N]
pub fn to_be_bytes_fixed<const N: usize>(&self) -> [u8; N]
Sourcepub fn to_le_bytes_fixed<const N: usize>(&self) -> [u8; N]
pub fn to_le_bytes_fixed<const N: usize>(&self) -> [u8; N]
Sourcepub fn bit(&self, index: usize) -> bool
pub fn bit(&self, index: usize) -> bool
Returns bit index (0 is the least significant).
Returns false for any index >= BITS.
Sourcepub fn ct_ge(&self, rhs: &Self) -> bool
pub fn ct_ge(&self, rhs: &Self) -> bool
Constant-time self >= rhs.
The execution path does not depend on the operand values.
Sourcepub fn ct_select(a: &Self, b: &Self, choice: bool) -> Self
pub fn ct_select(a: &Self, b: &Self, choice: bool) -> Self
Constant-time select: returns *a if choice is true, else *b.
Sourcepub fn add_raw(&self, rhs: &Self) -> (Self, u64)
pub fn add_raw(&self, rhs: &Self) -> (Self, u64)
Adds with carry, returning the wrapped sum and the carry out (0 or 1).
Sourcepub fn sub_raw(&self, rhs: &Self) -> (Self, u64)
pub fn sub_raw(&self, rhs: &Self) -> (Self, u64)
Subtracts with borrow, returning the wrapped difference and the borrow
out (0 or 1).
Sourcepub fn add_mod(&self, rhs: &Self, modulus: &Self) -> Self
pub fn add_mod(&self, rhs: &Self, modulus: &Self) -> Self
(self + rhs) mod modulus, constant time.
Requires self < modulus and rhs < modulus, and modulus > 0.
Sourcepub fn sub_mod(&self, rhs: &Self, modulus: &Self) -> Self
pub fn sub_mod(&self, rhs: &Self, modulus: &Self) -> Self
(self - rhs) mod modulus, constant time.
Requires self < modulus, rhs < modulus, and modulus > 0. For
self < rhs the result wraps to modulus - (rhs - self).
Sourcepub fn double_mod(&self, modulus: &Self) -> Self
pub fn double_mod(&self, modulus: &Self) -> Self
(self + self) mod modulus, constant time.
Requires self < modulus and modulus > 0.
Sourcepub fn mul_mod(&self, rhs: &Self, modulus: &Self) -> Self
pub fn mul_mod(&self, rhs: &Self, modulus: &Self) -> Self
(self * rhs) mod modulus using a bit-serial (shift-and-subtract)
reduction.
Constant time in the operands. Requires modulus > 0 and that the wide
product fits in 2 * LIMBS limbs (always true). This is the reference
implementation; prefer Self::mul_mod_barrett in hot loops.
Sourcepub fn compute_mu_for_barrett(&self) -> [u64; 260]
pub fn compute_mu_for_barrett(&self) -> [u64; 260]
Computes mu = floor(2^(2 * eff_limbs * 64) / self) for Barrett
reduction, where eff_limbs is ceil(self.bit_len() / 64).
Pass the result to Self::modpow_barrett or
Self::mul_mod_barrett_eff. The value is produced for the modulus’s
own effective limb count, which is what those functions use.
§Panics
Panics when self is zero (the reciprocal is undefined).
Sourcepub fn modpow_barrett(&self, exp: &Self, modulus: &Self, mu: &[u64]) -> Self
pub fn modpow_barrett(&self, exp: &Self, modulus: &Self, mu: &[u64]) -> Self
self^exp mod modulus using Barrett reduction.
mu must be produced by Self::compute_mu_for_barrett for the same
modulus; the effective limb count is derived from modulus.bit_len().
The base is reduced internally, so any input is accepted.
Not constant time in exp (it branches on each exponent bit); only use
it with a public exponent.
§Panics
Panics when modulus is zero or its effective limb count exceeds
MAX_BARRETT_LIMBS.
Sourcepub fn modpow_barrett_eff(
&self,
exp: &Self,
modulus: &Self,
mu: &[u64],
eff_limbs: usize,
) -> Self
pub fn modpow_barrett_eff( &self, exp: &Self, modulus: &Self, mu: &[u64], eff_limbs: usize, ) -> Self
Barrett modular exponentiation with an explicit effective limb count.
eff_limbs must equal ceil(modulus.bit_len() / 64) and mu must be
the matching reciprocal. See Self::modpow_barrett for the other
requirements.
Sourcepub fn modpow_barrett_w<const W: usize>(
&self,
exp: &Self,
modulus: &Self,
mu: &[u64],
) -> Self
pub fn modpow_barrett_w<const W: usize>( &self, exp: &Self, modulus: &Self, mu: &[u64], ) -> Self
Barrett modular exponentiation with a caller-chosen working width W.
W must be at least 2 * (eff_limbs + 1), where eff_limbs is the
modulus’s effective limb count. A W near that lower bound keeps the
scratch buffers small and is significantly faster than the default
Self::modpow_barrett (which uses W = MAX_LIMBS). Callers should
pick W from the modulus size; see the RSA public-key code.
Sourcepub fn mul_mod_barrett(&self, rhs: &Self, modulus: &Self, mu: &[u64]) -> Self
pub fn mul_mod_barrett(&self, rhs: &Self, modulus: &Self, mu: &[u64]) -> Self
(self * rhs) mod modulus using Barrett reduction.
mu must be produced by Self::compute_mu_for_barrett for the same
modulus. Both operands must already be reduced (< 2^(eff*64), in
practice < modulus); passing unreduced operands yields silently wrong
results. The effective limb count is derived from modulus.bit_len().
§Panics
Panics under the same conditions as Self::reduce_wide_barrett_eff.
Sourcepub fn mul_mod_barrett_eff(
&self,
rhs: &Self,
modulus: &Self,
mu: &[u64],
eff_limbs: usize,
) -> Self
pub fn mul_mod_barrett_eff( &self, rhs: &Self, modulus: &Self, mu: &[u64], eff_limbs: usize, ) -> Self
Barrett multiplication with an explicit effective limb count.
eff_limbs must equal ceil(modulus.bit_len() / 64) and both operands
must already be reduced. See Self::mul_mod_barrett.
Sourcepub fn mul_mod_barrett_w<const W: usize>(
&self,
rhs: &Self,
modulus: &Self,
mu: &[u64],
) -> Self
pub fn mul_mod_barrett_w<const W: usize>( &self, rhs: &Self, modulus: &Self, mu: &[u64], ) -> Self
Barrett multiplication with a caller-chosen working width W.
W must be at least 2 * (eff_limbs + 1) where eff_limbs is the
modulus’s effective limb count. Picking W near that bound (instead of
the default MAX_LIMBS) makes this much faster; see
Self::modpow_barrett_w.
The operands must already be reduced below the modulus.
Sourcepub fn reduce_wide_barrett_eff(
product: &[u64; 260],
modulus: &Self,
mu: &[u64],
eff_limbs: usize,
) -> Self
pub fn reduce_wide_barrett_eff( product: &[u64; 260], modulus: &Self, mu: &[u64], eff_limbs: usize, ) -> Self
Barrett reduction of a 2 * LIMBS-wide product with an explicit
effective limb count k = eff_limbs.
mu must equal floor(2^(2 * k * 64) / modulus) — that is, the value
returned by Self::compute_mu_for_barrett for this modulus — and have
at least k + 1 entries. The product must be less than
2^(2 * k * 64); when k < LIMBS this means the factors of the product
must already be reduced (see Self::mul_mod_barrett_eff).
§Panics
Panics when eff_limbs is out of range, when the effective width does
not fit in MAX_LIMBS, or when mu is too short.
Sourcepub fn modpow(&self, exp: &Self, modulus: &Self) -> Self
pub fn modpow(&self, exp: &Self, modulus: &Self) -> Self
self^exp mod modulus using square-and-multiply, scanning only up to
the exponent’s bit length.
Uses the bit-serial Self::mul_mod reduction and is therefore slow;
prefer Self::modpow_barrett in hot loops.
Not constant time in exp (it branches on each exponent bit); only use
it with a public exponent.
§Panics
In debug builds modulus must be nonzero; in release a zero modulus
yields an unreduced result.
Sourcepub fn reduce_wide_barrett(
product: &[u64; 260],
modulus: &Self,
mu: &[u64],
) -> Self
pub fn reduce_wide_barrett( product: &[u64; 260], modulus: &Self, mu: &[u64], ) -> Self
Barrett reduction of a 2 * LIMBS-wide product modulo modulus.
The effective limb count is derived from modulus.bit_len(), so mu
must be the matching value from Self::compute_mu_for_barrett. The
product must be less than 2^(2 * k * 64), where k is that effective
limb count; when the modulus does not fill all LIMBS limbs this means
the product’s factors must already be reduced (see
Self::mul_mod_barrett).
Equivalent to Self::reduce_wide_barrett_eff with
k = ceil(modulus.bit_len() / 64).
Sourcepub fn add_word(&self, word: u64) -> (Self, u64)
pub fn add_word(&self, word: u64) -> (Self, u64)
Adds a single u64, returning the wrapped result and carry out.
Sourcepub fn sub_word(&self, word: u64) -> (Self, u64)
pub fn sub_word(&self, word: u64) -> (Self, u64)
Subtracts a single u64, returning the wrapped result and borrow out.
Sourcepub fn mul_word(&self, word: u64) -> (Self, u64)
pub fn mul_word(&self, word: u64) -> (Self, u64)
Multiplies by a single u64, returning the low LIMBS limbs and the
carry (high word) out.
Sourcepub fn div_rem_word(&self, word: u64) -> (Self, u64)
pub fn div_rem_word(&self, word: u64) -> (Self, u64)
Sourcepub fn mul_u128(&self, value: u128) -> Self
pub fn mul_u128(&self, value: u128) -> Self
Multiplies by a u128, returning the low BITS bits (wrapping).
Sourcepub fn div_rem_u128(&self, divisor: u128) -> (Self, u128)
pub fn div_rem_u128(&self, divisor: u128) -> (Self, u128)
Sourcepub fn from_str_radix(src: &str, radix: u32) -> Result<Self, Error>
pub fn from_str_radix(src: &str, radix: u32) -> Result<Self, Error>
Parses src as an unsigned integer in radix (2..=36), accepting the
ASCII digits 0-9, a-z and A-Z.
Leading zero digits are accepted. The value must fit in BITS bits,
otherwise Error::Overflow is returned. Signs (+/-), whitespace,
_ separators and prefixes such as 0x are not accepted. The input
length is bounded before any per-digit work, so a hostile multi-megabyte
string cannot force unbounded computation. This method never allocates.
§Errors
Returns Error::InvalidRadix for radix outside 2..=36,
Error::EmptyString for an empty input, Error::InvalidDigit for a
non-digit or out-of-range character, and Error::Overflow when the
value does not fit in BITS bits.
§Examples
use big_number::Uint;
let max = Uint::<64, 1>::from_str_radix("ffffffffffffffff", 16).unwrap();
assert_eq!(max, Uint::<64, 1>::MAX);
assert!(Uint::<64, 1>::from_str_radix("10000000000000000", 16).is_err()); // 2^64Trait Implementations§
impl<const BITS: usize, const LIMBS: usize> Copy for Uint<BITS, LIMBS>
Source§impl<const BITS: usize, const LIMBS: usize> Display for Uint<BITS, LIMBS>
Available on crate feature alloc only.
impl<const BITS: usize, const LIMBS: usize> Display for Uint<BITS, LIMBS>
alloc only.