Merging upstream version 1.71.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

21 files changed, 1402 insertions, 0 deletions

diff --git a/vendor/crypto-bigint/src/uint/modular/add.rs b/vendor/crypto-bigint/src/uint/modular/add.rs
new file mode 100644
index 000000000..f4d0f79d3
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/add.rs
@@ -0,0 +1,9 @@
+use crate::Uint;
+
+pub(crate) const fn add_montgomery_form<const LIMBS: usize>(
+    a: &Uint<LIMBS>,
+    b: &Uint<LIMBS>,
+    modulus: &Uint<LIMBS>,
+) -> Uint<LIMBS> {
+    a.add_mod(b, modulus)
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs
new file mode 100644
index 000000000..f94e4c475
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs
@@ -0,0 +1,189 @@
+use core::{fmt::Debug, marker::PhantomData};
+
+use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
+
+use crate::{Limb, Uint, Zero};
+
+use super::{reduction::montgomery_reduction, Retrieve};
+
+#[cfg(feature = "rand_core")]
+use crate::{rand_core::CryptoRngCore, NonZero, Random, RandomMod};
+
+#[cfg(feature = "serde")]
+use {
+    crate::Encoding,
+    serdect::serde::de::Error,
+    serdect::serde::{Deserialize, Deserializer, Serialize, Serializer},
+};
+
+/// Additions between residues with a constant modulus
+mod const_add;
+/// Multiplicative inverses of residues with a constant modulus
+mod const_inv;
+/// Multiplications between residues with a constant modulus
+mod const_mul;
+/// Negations of residues with a constant modulus
+mod const_neg;
+/// Exponentiation of residues with a constant modulus
+mod const_pow;
+/// Subtractions between residues with a constant modulus
+mod const_sub;
+
+/// Macros to remove the boilerplate code when dealing with constant moduli.
+#[macro_use]
+mod macros;
+
+pub use macros::*;
+
+/// The parameters to efficiently go to and from the Montgomery form for a given odd modulus. An easy way to generate these parameters is using the `impl_modulus!` macro. These parameters are constant, so they cannot be set at runtime.
+///
+/// Unfortunately, `LIMBS` must be generic for now until const generics are stabilized.
+pub trait ResidueParams<const LIMBS: usize>:
+    Copy + Debug + Default + Eq + Send + Sync + 'static
+{
+    /// Number of limbs required to encode a residue
+    const LIMBS: usize;
+
+    /// The constant modulus
+    const MODULUS: Uint<LIMBS>;
+    /// Parameter used in Montgomery reduction
+    const R: Uint<LIMBS>;
+    /// R^2, used to move into Montgomery form
+    const R2: Uint<LIMBS>;
+    /// R^3, used to perform a multiplicative inverse
+    const R3: Uint<LIMBS>;
+    /// The lowest limbs of -(MODULUS^-1) mod R
+    // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS.
+    const MOD_NEG_INV: Limb;
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+/// A residue mod `MOD`, represented using `LIMBS` limbs. The modulus of this residue is constant, so it cannot be set at runtime.
+pub struct Residue<MOD, const LIMBS: usize>
+where
+    MOD: ResidueParams<LIMBS>,
+{
+    montgomery_form: Uint<LIMBS>,
+    phantom: PhantomData<MOD>,
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// The representation of 0 mod `MOD`.
+    pub const ZERO: Self = Self {
+        montgomery_form: Uint::<LIMBS>::ZERO,
+        phantom: PhantomData,
+    };
+
+    /// The representation of 1 mod `MOD`.
+    pub const ONE: Self = Self {
+        montgomery_form: MOD::R,
+        phantom: PhantomData,
+    };
+
+    /// Instantiates a new `Residue` that represents this `integer` mod `MOD`.
+    pub const fn new(integer: &Uint<LIMBS>) -> Self {
+        let product = integer.mul_wide(&MOD::R2);
+        let montgomery_form =
+            montgomery_reduction::<LIMBS>(&product, &MOD::MODULUS, MOD::MOD_NEG_INV);
+
+        Self {
+            montgomery_form,
+            phantom: PhantomData,
+        }
+    }
+
+    /// Retrieves the integer currently encoded in this `Residue`, guaranteed to be reduced.
+    pub const fn retrieve(&self) -> Uint<LIMBS> {
+        montgomery_reduction::<LIMBS>(
+            &(self.montgomery_form, Uint::ZERO),
+            &MOD::MODULUS,
+            MOD::MOD_NEG_INV,
+        )
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS> + Copy, const LIMBS: usize> ConditionallySelectable
+    for Residue<MOD, LIMBS>
+{
+    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
+        Residue {
+            montgomery_form: Uint::conditional_select(
+                &a.montgomery_form,
+                &b.montgomery_form,
+                choice,
+            ),
+            phantom: PhantomData,
+        }
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> ConstantTimeEq for Residue<MOD, LIMBS> {
+    fn ct_eq(&self, other: &Self) -> Choice {
+        ConstantTimeEq::ct_eq(&self.montgomery_form, &other.montgomery_form)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Default for Residue<MOD, LIMBS> {
+    fn default() -> Self {
+        Self::ZERO
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Zero for Residue<MOD, LIMBS> {
+    const ZERO: Self = Self::ZERO;
+}
+
+#[cfg(feature = "rand_core")]
+impl<MOD, const LIMBS: usize> Random for Residue<MOD, LIMBS>
+where
+    MOD: ResidueParams<LIMBS>,
+{
+    #[inline]
+    fn random(rng: &mut impl CryptoRngCore) -> Self {
+        Self::new(&Uint::random_mod(rng, &NonZero::from_uint(MOD::MODULUS)))
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Retrieve for Residue<MOD, LIMBS> {
+    type Output = Uint<LIMBS>;
+    fn retrieve(&self) -> Self::Output {
+        self.retrieve()
+    }
+}
+
+#[cfg(feature = "serde")]
+impl<'de, MOD, const LIMBS: usize> Deserialize<'de> for Residue<MOD, LIMBS>
+where
+    MOD: ResidueParams<LIMBS>,
+    Uint<LIMBS>: Encoding,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: Deserializer<'de>,
+    {
+        Uint::<LIMBS>::deserialize(deserializer).and_then(|montgomery_form| {
+            if Uint::ct_lt(&montgomery_form, &MOD::MODULUS).into() {
+                Ok(Self {
+                    montgomery_form,
+                    phantom: PhantomData,
+                })
+            } else {
+                Err(D::Error::custom("montgomery form must be reduced"))
+            }
+        })
+    }
+}
+
+#[cfg(feature = "serde")]
+impl<MOD, const LIMBS: usize> Serialize for Residue<MOD, LIMBS>
+where
+    MOD: ResidueParams<LIMBS>,
+    Uint<LIMBS>: Encoding,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        self.montgomery_form.serialize(serializer)
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs
new file mode 100644
index 000000000..82eb8826c
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs
@@ -0,0 +1,98 @@
+use core::ops::{Add, AddAssign};
+
+use crate::modular::add::add_montgomery_form;
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Adds `rhs`.
+    pub const fn add(&self, rhs: &Residue<MOD, LIMBS>) -> Self {
+        Self {
+            montgomery_form: add_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &MOD::MODULUS,
+            ),
+            phantom: core::marker::PhantomData,
+        }
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<&Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn add(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self.add(rhs)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn add(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self + &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<&Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn add(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self + rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn add(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self + &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> AddAssign<&Self> for Residue<MOD, LIMBS> {
+    fn add_assign(&mut self, rhs: &Self) {
+        *self = *self + rhs;
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> AddAssign<Self> for Residue<MOD, LIMBS> {
+    fn add_assign(&mut self, rhs: Self) {
+        *self += &rhs;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
+
+    impl_modulus!(
+        Modulus,
+        U256,
+        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
+    );
+
+    #[test]
+    fn add_overflow() {
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let mut x_mod = const_residue!(x, Modulus);
+
+        let y =
+            U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
+        let y_mod = const_residue!(y, Modulus);
+
+        x_mod += &y_mod;
+
+        let expected =
+            U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956");
+
+        assert_eq!(expected, x_mod.retrieve());
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs
new file mode 100644
index 000000000..5c8da7b88
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs
@@ -0,0 +1,69 @@
+use core::marker::PhantomData;
+
+use subtle::CtOption;
+
+use crate::{modular::inv::inv_montgomery_form, traits::Invert, CtChoice, NonZero};
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Computes the residue `self^-1` representing the multiplicative inverse of `self`.
+    /// I.e. `self * self^-1 = 1`.
+    /// If the number was invertible, the second element of the tuple is the truthy value,
+    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
+    pub const fn invert(&self) -> (Self, CtChoice) {
+        let (montgomery_form, is_some) = inv_montgomery_form(
+            &self.montgomery_form,
+            &MOD::MODULUS,
+            &MOD::R3,
+            MOD::MOD_NEG_INV,
+        );
+
+        let value = Self {
+            montgomery_form,
+            phantom: PhantomData,
+        };
+
+        (value, is_some)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for Residue<MOD, LIMBS> {
+    type Output = CtOption<Self>;
+    fn invert(&self) -> Self::Output {
+        let (value, is_some) = self.invert();
+        CtOption::new(value, is_some.into())
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for NonZero<Residue<MOD, LIMBS>> {
+    type Output = Self;
+    fn invert(&self) -> Self::Output {
+        // Always succeeds for a non-zero argument
+        let (value, _is_some) = self.as_ref().invert();
+        NonZero::new(value).unwrap()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
+
+    impl_modulus!(
+        Modulus,
+        U256,
+        "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"
+    );
+
+    #[test]
+    fn test_self_inverse() {
+        let x =
+            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
+        let x_mod = const_residue!(x, Modulus);
+
+        let (inv, _is_some) = x_mod.invert();
+        let res = &x_mod * &inv;
+
+        assert_eq!(res.retrieve(), U256::ONE);
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs
new file mode 100644
index 000000000..3bce1848a
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs
@@ -0,0 +1,94 @@
+use core::{
+    marker::PhantomData,
+    ops::{Mul, MulAssign},
+};
+
+use crate::{
+    modular::mul::{mul_montgomery_form, square_montgomery_form},
+    traits::Square,
+};
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Multiplies by `rhs`.
+    pub const fn mul(&self, rhs: &Self) -> Self {
+        Self {
+            montgomery_form: mul_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &MOD::MODULUS,
+                MOD::MOD_NEG_INV,
+            ),
+            phantom: PhantomData,
+        }
+    }
+
+    /// Computes the (reduced) square of a residue.
+    pub const fn square(&self) -> Self {
+        Self {
+            montgomery_form: square_montgomery_form(
+                &self.montgomery_form,
+                &MOD::MODULUS,
+                MOD::MOD_NEG_INV,
+            ),
+            phantom: PhantomData,
+        }
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<&Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn mul(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self.mul(rhs)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn mul(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self * &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<&Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn mul(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self * rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn mul(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self * &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> MulAssign<&Self> for Residue<MOD, LIMBS> {
+    fn mul_assign(&mut self, rhs: &Residue<MOD, LIMBS>) {
+        *self = *self * rhs;
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> MulAssign<Self> for Residue<MOD, LIMBS> {
+    fn mul_assign(&mut self, rhs: Self) {
+        *self *= &rhs;
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Square for Residue<MOD, LIMBS> {
+    fn square(&self) -> Self {
+        Residue::square(self)
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs
new file mode 100644
index 000000000..1981f5a20
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs
@@ -0,0 +1,48 @@
+use core::ops::Neg;
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Negates the number.
+    pub const fn neg(&self) -> Self {
+        Self::ZERO.sub(self)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Neg for Residue<MOD, LIMBS> {
+    type Output = Self;
+    fn neg(self) -> Self {
+        Residue::neg(&self)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Neg for &Residue<MOD, LIMBS> {
+    type Output = Residue<MOD, LIMBS>;
+    fn neg(self) -> Residue<MOD, LIMBS> {
+        Residue::neg(self)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
+
+    impl_modulus!(
+        Modulus,
+        U256,
+        "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409"
+    );
+
+    #[test]
+    fn test_negate() {
+        let x =
+            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
+        let x_mod = const_residue!(x, Modulus);
+
+        let res = -x_mod;
+        let expected =
+            U256::from_be_hex("089B67BB2C124F084701AD76E8750D321385E35044C74CE457301A2A9BE061B1");
+
+        assert_eq!(res.retrieve(), expected);
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs
new file mode 100644
index 000000000..60455b05b
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs
@@ -0,0 +1,98 @@
+use crate::{modular::pow::pow_montgomery_form, PowBoundedExp, Uint};
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Raises to the `exponent` power.
+    pub const fn pow(&self, exponent: &Uint<LIMBS>) -> Residue<MOD, LIMBS> {
+        self.pow_bounded_exp(exponent, Uint::<LIMBS>::BITS)
+    }
+
+    /// Raises to the `exponent` power,
+    /// with `exponent_bits` representing the number of (least significant) bits
+    /// to take into account for the exponent.
+    ///
+    /// NOTE: `exponent_bits` may be leaked in the time pattern.
+    pub const fn pow_bounded_exp(
+        &self,
+        exponent: &Uint<LIMBS>,
+        exponent_bits: usize,
+    ) -> Residue<MOD, LIMBS> {
+        Self {
+            montgomery_form: pow_montgomery_form(
+                &self.montgomery_form,
+                exponent,
+                exponent_bits,
+                &MOD::MODULUS,
+                &MOD::R,
+                MOD::MOD_NEG_INV,
+            ),
+            phantom: core::marker::PhantomData,
+        }
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> PowBoundedExp<Uint<LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    fn pow_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: usize) -> Self {
+        self.pow_bounded_exp(exponent, exponent_bits)
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
+
+    impl_modulus!(
+        Modulus,
+        U256,
+        "9CC24C5DF431A864188AB905AC751B727C9447A8E99E6366E1AD78A21E8D882B"
+    );
+
+    #[test]
+    fn test_powmod_small_base() {
+        let base = U256::from(105u64);
+        let base_mod = const_residue!(base, Modulus);
+
+        let exponent =
+            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
+
+        let res = base_mod.pow(&exponent);
+
+        let expected =
+            U256::from_be_hex("7B2CD7BDDD96C271E6F232F2F415BB03FE2A90BD6CCCEA5E94F1BFD064993766");
+        assert_eq!(res.retrieve(), expected);
+    }
+
+    #[test]
+    fn test_powmod_small_exponent() {
+        let base =
+            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
+        let base_mod = const_residue!(base, Modulus);
+
+        let exponent = U256::from(105u64);
+
+        let res = base_mod.pow(&exponent);
+
+        let expected =
+            U256::from_be_hex("89E2A4E99F649A5AE2C18068148C355CA927B34A3245C938178ED00D6EF218AA");
+        assert_eq!(res.retrieve(), expected);
+    }
+
+    #[test]
+    fn test_powmod() {
+        let base =
+            U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4");
+        let base_mod = const_residue!(base, Modulus);
+
+        let exponent =
+            U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685");
+
+        let res = base_mod.pow(&exponent);
+
+        let expected =
+            U256::from_be_hex("3681BC0FEA2E5D394EB178155A127B0FD2EF405486D354251C385BDD51B9D421");
+        assert_eq!(res.retrieve(), expected);
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs
new file mode 100644
index 000000000..f65061146
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs
@@ -0,0 +1,98 @@
+use core::ops::{Sub, SubAssign};
+
+use crate::modular::sub::sub_montgomery_form;
+
+use super::{Residue, ResidueParams};
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
+    /// Subtracts `rhs`.
+    pub const fn sub(&self, rhs: &Self) -> Self {
+        Self {
+            montgomery_form: sub_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &MOD::MODULUS,
+            ),
+            phantom: core::marker::PhantomData,
+        }
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<&Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn sub(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self.sub(rhs)
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<Residue<MOD, LIMBS>>
+    for &Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn sub(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        self - &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<&Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn sub(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self - rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<Residue<MOD, LIMBS>>
+    for Residue<MOD, LIMBS>
+{
+    type Output = Residue<MOD, LIMBS>;
+    fn sub(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> {
+        &self - &rhs
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> SubAssign<&Self> for Residue<MOD, LIMBS> {
+    fn sub_assign(&mut self, rhs: &Self) {
+        *self = *self - rhs;
+    }
+}
+
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> SubAssign<Self> for Residue<MOD, LIMBS> {
+    fn sub_assign(&mut self, rhs: Self) {
+        *self -= &rhs;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256};
+
+    impl_modulus!(
+        Modulus,
+        U256,
+        "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551"
+    );
+
+    #[test]
+    fn sub_overflow() {
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let mut x_mod = const_residue!(x, Modulus);
+
+        let y =
+            U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
+        let y_mod = const_residue!(y, Modulus);
+
+        x_mod -= &y_mod;
+
+        let expected =
+            U256::from_be_hex("6f357a71e1d5a03167f34879d469352add829491c6df41ddff65387d7ed56f56");
+
+        assert_eq!(expected, x_mod.retrieve());
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs
new file mode 100644
index 000000000..1583ca529
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs
@@ -0,0 +1,50 @@
+// TODO: Use `adt_const_params` once stabilized to make a `Residue` generic around a modulus rather than having to implement a ZST + trait
+#[macro_export]
+/// Implements a modulus with the given name, type, and value, in that specific order. Please `use crypto_bigint::traits::Encoding` to make this work.
+/// For example, `impl_modulus!(MyModulus, U256, "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001");` implements a 256-bit modulus named `MyModulus`.
+macro_rules! impl_modulus {
+    ($name:ident, $uint_type:ty, $value:expr) => {
+        #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
+        pub struct $name {}
+        impl<const DLIMBS: usize>
+            $crate::modular::constant_mod::ResidueParams<{ $crate::nlimbs!(<$uint_type>::BITS) }>
+            for $name
+        where
+            $crate::Uint<{ $crate::nlimbs!(<$uint_type>::BITS) }>:
+                $crate::Concat<Output = $crate::Uint<DLIMBS>>,
+        {
+            const LIMBS: usize = { $crate::nlimbs!(<$uint_type>::BITS) };
+            const MODULUS: $crate::Uint<{ $crate::nlimbs!(<$uint_type>::BITS) }> =
+                <$uint_type>::from_be_hex($value);
+            const R: $crate::Uint<{ $crate::nlimbs!(<$uint_type>::BITS) }> = $crate::Uint::MAX
+                .const_rem(&Self::MODULUS)
+                .0
+                .wrapping_add(&$crate::Uint::ONE);
+            const R2: $crate::Uint<{ $crate::nlimbs!(<$uint_type>::BITS) }> =
+                $crate::Uint::const_rem_wide(Self::R.square_wide(), &Self::MODULUS).0;
+            const MOD_NEG_INV: $crate::Limb = $crate::Limb(
+                $crate::Word::MIN.wrapping_sub(
+                    Self::MODULUS
+                        .inv_mod2k($crate::Word::BITS as usize)
+                        .as_limbs()[0]
+                        .0,
+                ),
+            );
+            const R3: $crate::Uint<{ $crate::nlimbs!(<$uint_type>::BITS) }> =
+                $crate::modular::montgomery_reduction(
+                    &Self::R2.square_wide(),
+                    &Self::MODULUS,
+                    Self::MOD_NEG_INV,
+                );
+        }
+    };
+}
+
+#[macro_export]
+/// Creates a `Residue` with the given value for a specific modulus.
+/// For example, `residue!(U256::from(105u64), MyModulus);` creates a `Residue` for 105 mod `MyModulus`.
+macro_rules! const_residue {
+    ($variable:ident, $modulus:ident) => {
+        $crate::modular::constant_mod::Residue::<$modulus, { $modulus::LIMBS }>::new(&$variable)
+    };
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/inv.rs b/vendor/crypto-bigint/src/uint/modular/inv.rs
new file mode 100644
index 000000000..408c03fb8
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/inv.rs
@@ -0,0 +1,14 @@
+use crate::{modular::reduction::montgomery_reduction, CtChoice, Limb, Uint};
+
+pub const fn inv_montgomery_form<const LIMBS: usize>(
+    x: &Uint<LIMBS>,
+    modulus: &Uint<LIMBS>,
+    r3: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> (Uint<LIMBS>, CtChoice) {
+    let (inverse, is_some) = x.inv_odd_mod(modulus);
+    (
+        montgomery_reduction(&inverse.mul_wide(r3), modulus, mod_neg_inv),
+        is_some,
+    )
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/mul.rs b/vendor/crypto-bigint/src/uint/modular/mul.rs
new file mode 100644
index 000000000..b84ceb5ca
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/mul.rs
@@ -0,0 +1,22 @@
+use crate::{Limb, Uint};
+
+use super::reduction::montgomery_reduction;
+
+pub(crate) const fn mul_montgomery_form<const LIMBS: usize>(
+    a: &Uint<LIMBS>,
+    b: &Uint<LIMBS>,
+    modulus: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> Uint<LIMBS> {
+    let product = a.mul_wide(b);
+    montgomery_reduction::<LIMBS>(&product, modulus, mod_neg_inv)
+}
+
+pub(crate) const fn square_montgomery_form<const LIMBS: usize>(
+    a: &Uint<LIMBS>,
+    modulus: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> Uint<LIMBS> {
+    let product = a.square_wide();
+    montgomery_reduction::<LIMBS>(&product, modulus, mod_neg_inv)
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/pow.rs b/vendor/crypto-bigint/src/uint/modular/pow.rs
new file mode 100644
index 000000000..5ab1fd63d
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/pow.rs
@@ -0,0 +1,79 @@
+use crate::{Limb, Uint, Word};
+
+use super::mul::{mul_montgomery_form, square_montgomery_form};
+
+/// Performs modular exponentiation using Montgomery's ladder.
+/// `exponent_bits` represents the number of bits to take into account for the exponent.
+///
+/// NOTE: this value is leaked in the time pattern.
+pub const fn pow_montgomery_form<const LIMBS: usize>(
+    x: &Uint<LIMBS>,
+    exponent: &Uint<LIMBS>,
+    exponent_bits: usize,
+    modulus: &Uint<LIMBS>,
+    r: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> Uint<LIMBS> {
+    if exponent_bits == 0 {
+        return *r; // 1 in Montgomery form
+    }
+
+    const WINDOW: usize = 4;
+    const WINDOW_MASK: Word = (1 << WINDOW) - 1;
+
+    // powers[i] contains x^i
+    let mut powers = [*r; 1 << WINDOW];
+    powers[1] = *x;
+    let mut i = 2;
+    while i < powers.len() {
+        powers[i] = mul_montgomery_form(&powers[i - 1], x, modulus, mod_neg_inv);
+        i += 1;
+    }
+
+    let starting_limb = (exponent_bits - 1) / Limb::BITS;
+    let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS;
+    let starting_window = starting_bit_in_limb / WINDOW;
+    let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1;
+
+    let mut z = *r; // 1 in Montgomery form
+
+    let mut limb_num = starting_limb + 1;
+    while limb_num > 0 {
+        limb_num -= 1;
+        let w = exponent.as_limbs()[limb_num].0;
+
+        let mut window_num = if limb_num == starting_limb {
+            starting_window + 1
+        } else {
+            Limb::BITS / WINDOW
+        };
+        while window_num > 0 {
+            window_num -= 1;
+
+            let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK;
+
+            if limb_num == starting_limb && window_num == starting_window {
+                idx &= starting_window_mask;
+            } else {
+                let mut i = 0;
+                while i < WINDOW {
+                    i += 1;
+                    z = square_montgomery_form(&z, modulus, mod_neg_inv);
+                }
+            }
+
+            // Constant-time lookup in the array of powers
+            let mut power = powers[0];
+            let mut i = 1;
+            while i < 1 << WINDOW {
+                let choice = Limb::ct_eq(Limb(i as Word), Limb(idx));
+                power = Uint::<LIMBS>::ct_select(&power, &powers[i], choice);
+                i += 1;
+            }
+
+            z = mul_montgomery_form(&z, &power, modulus, mod_neg_inv);
+        }
+    }
+
+    z
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/reduction.rs b/vendor/crypto-bigint/src/uint/modular/reduction.rs
new file mode 100644
index 000000000..d3543bf97
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/reduction.rs
@@ -0,0 +1,56 @@
+use crate::{CtChoice, Limb, Uint, WideWord, Word};
+
+/// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
+pub const fn montgomery_reduction<const LIMBS: usize>(
+    lower_upper: &(Uint<LIMBS>, Uint<LIMBS>),
+    modulus: &Uint<LIMBS>,
+    mod_neg_inv: Limb,
+) -> Uint<LIMBS> {
+    let (mut lower, mut upper) = *lower_upper;
+
+    let mut meta_carry: WideWord = 0;
+
+    let mut i = 0;
+    while i < LIMBS {
+        let u = (lower.limbs[i].0.wrapping_mul(mod_neg_inv.0)) as WideWord;
+
+        let new_limb =
+            (u * modulus.limbs[0].0 as WideWord).wrapping_add(lower.limbs[i].0 as WideWord);
+        let mut carry = new_limb >> Word::BITS;
+
+        let mut j = 1;
+        while j < (LIMBS - i) {
+            let new_limb = (u * modulus.limbs[j].0 as WideWord)
+                .wrapping_add(lower.limbs[i + j].0 as WideWord)
+                .wrapping_add(carry);
+            carry = new_limb >> Word::BITS;
+            lower.limbs[i + j] = Limb(new_limb as Word);
+
+            j += 1;
+        }
+        while j < LIMBS {
+            let new_limb = (u * modulus.limbs[j].0 as WideWord)
+                .wrapping_add(upper.limbs[i + j - LIMBS].0 as WideWord)
+                .wrapping_add(carry);
+            carry = new_limb >> Word::BITS;
+            upper.limbs[i + j - LIMBS] = Limb(new_limb as Word);
+
+            j += 1;
+        }
+
+        let new_sum = (upper.limbs[i].0 as WideWord)
+            .wrapping_add(carry)
+            .wrapping_add(meta_carry);
+        meta_carry = new_sum >> Word::BITS;
+        upper.limbs[i] = Limb(new_sum as Word);
+
+        i += 1;
+    }
+
+    // Division is simply taking the upper half of the limbs
+    // Final reduction (at this point, the value is at most 2 * modulus)
+    let must_reduce = CtChoice::from_lsb(meta_carry as Word).or(Uint::ct_gt(modulus, &upper).not());
+    upper = upper.wrapping_sub(&Uint::ct_select(&Uint::ZERO, modulus, must_reduce));
+
+    upper
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs
new file mode 100644
index 000000000..72f1094cf
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs
@@ -0,0 +1,107 @@
+use crate::{Limb, Uint, Word};
+
+use super::{reduction::montgomery_reduction, Retrieve};
+
+/// Additions between residues with a modulus set at runtime
+mod runtime_add;
+/// Multiplicative inverses of residues with a modulus set at runtime
+mod runtime_inv;
+/// Multiplications between residues with a modulus set at runtime
+mod runtime_mul;
+/// Negations of residues with a modulus set at runtime
+mod runtime_neg;
+/// Exponentiation of residues with a modulus set at runtime
+mod runtime_pow;
+/// Subtractions between residues with a modulus set at runtime
+mod runtime_sub;
+
+/// The parameters to efficiently go to and from the Montgomery form for a modulus provided at runtime.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub struct DynResidueParams<const LIMBS: usize> {
+    // The constant modulus
+    modulus: Uint<LIMBS>,
+    // Parameter used in Montgomery reduction
+    r: Uint<LIMBS>,
+    // R^2, used to move into Montgomery form
+    r2: Uint<LIMBS>,
+    // R^3, used to compute the multiplicative inverse
+    r3: Uint<LIMBS>,
+    // The lowest limbs of -(MODULUS^-1) mod R
+    // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS.
+    mod_neg_inv: Limb,
+}
+
+impl<const LIMBS: usize> DynResidueParams<LIMBS> {
+    /// Instantiates a new set of `ResidueParams` representing the given `modulus`.
+    pub fn new(modulus: &Uint<LIMBS>) -> Self {
+        let r = Uint::MAX.const_rem(modulus).0.wrapping_add(&Uint::ONE);
+        let r2 = Uint::const_rem_wide(r.square_wide(), modulus).0;
+        let mod_neg_inv =
+            Limb(Word::MIN.wrapping_sub(modulus.inv_mod2k(Word::BITS as usize).limbs[0].0));
+        let r3 = montgomery_reduction(&r2.square_wide(), modulus, mod_neg_inv);
+
+        Self {
+            modulus: *modulus,
+            r,
+            r2,
+            r3,
+            mod_neg_inv,
+        }
+    }
+}
+
+/// A residue represented using `LIMBS` limbs. The odd modulus of this residue is set at runtime.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub struct DynResidue<const LIMBS: usize> {
+    montgomery_form: Uint<LIMBS>,
+    residue_params: DynResidueParams<LIMBS>,
+}
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Instantiates a new `Residue` that represents this `integer` mod `MOD`.
+    pub const fn new(integer: &Uint<LIMBS>, residue_params: DynResidueParams<LIMBS>) -> Self {
+        let product = integer.mul_wide(&residue_params.r2);
+        let montgomery_form = montgomery_reduction(
+            &product,
+            &residue_params.modulus,
+            residue_params.mod_neg_inv,
+        );
+
+        Self {
+            montgomery_form,
+            residue_params,
+        }
+    }
+
+    /// Retrieves the integer currently encoded in this `Residue`, guaranteed to be reduced.
+    pub const fn retrieve(&self) -> Uint<LIMBS> {
+        montgomery_reduction(
+            &(self.montgomery_form, Uint::ZERO),
+            &self.residue_params.modulus,
+            self.residue_params.mod_neg_inv,
+        )
+    }
+
+    /// Instantiates a new `Residue` that represents zero.
+    pub const fn zero(residue_params: DynResidueParams<LIMBS>) -> Self {
+        Self {
+            montgomery_form: Uint::<LIMBS>::ZERO,
+            residue_params,
+        }
+    }
+
+    /// Instantiates a new `Residue` that represents 1.
+    pub const fn one(residue_params: DynResidueParams<LIMBS>) -> Self {
+        Self {
+            montgomery_form: residue_params.r,
+            residue_params,
+        }
+    }
+}
+
+impl<const LIMBS: usize> Retrieve for DynResidue<LIMBS> {
+    type Output = Uint<LIMBS>;
+    fn retrieve(&self) -> Self::Output {
+        self.retrieve()
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs
new file mode 100644
index 000000000..eb4708603
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs
@@ -0,0 +1,92 @@
+use core::ops::{Add, AddAssign};
+
+use crate::modular::add::add_montgomery_form;
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Adds `rhs`.
+    pub const fn add(&self, rhs: &Self) -> Self {
+        Self {
+            montgomery_form: add_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &self.residue_params.modulus,
+            ),
+            residue_params: self.residue_params,
+        }
+    }
+}
+
+impl<const LIMBS: usize> Add<&DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn add(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        debug_assert_eq!(self.residue_params, rhs.residue_params);
+        self.add(rhs)
+    }
+}
+
+impl<const LIMBS: usize> Add<DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn add(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        self + &rhs
+    }
+}
+
+impl<const LIMBS: usize> Add<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn add(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self + rhs
+    }
+}
+
+impl<const LIMBS: usize> Add<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn add(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self + &rhs
+    }
+}
+
+impl<const LIMBS: usize> AddAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn add_assign(&mut self, rhs: &DynResidue<LIMBS>) {
+        *self = *self + rhs;
+    }
+}
+
+impl<const LIMBS: usize> AddAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn add_assign(&mut self, rhs: DynResidue<LIMBS>) {
+        *self += &rhs;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{
+        modular::runtime_mod::{DynResidue, DynResidueParams},
+        U256,
+    };
+
+    #[test]
+    fn add_overflow() {
+        let params = DynResidueParams::new(&U256::from_be_hex(
+            "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
+        ));
+
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let mut x_mod = DynResidue::new(&x, params);
+
+        let y =
+            U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
+        let y_mod = DynResidue::new(&y, params);
+
+        x_mod += &y_mod;
+
+        let expected =
+            U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956");
+
+        assert_eq!(expected, x_mod.retrieve());
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs
new file mode 100644
index 000000000..5e639d439
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs
@@ -0,0 +1,35 @@
+use subtle::CtOption;
+
+use crate::{modular::inv::inv_montgomery_form, traits::Invert, CtChoice};
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Computes the residue `self^-1` representing the multiplicative inverse of `self`.
+    /// I.e. `self * self^-1 = 1`.
+    /// If the number was invertible, the second element of the tuple is the truthy value,
+    /// otherwise it is the falsy value (in which case the first element's value is unspecified).
+    pub const fn invert(&self) -> (Self, CtChoice) {
+        let (montgomery_form, is_some) = inv_montgomery_form(
+            &self.montgomery_form,
+            &self.residue_params.modulus,
+            &self.residue_params.r3,
+            self.residue_params.mod_neg_inv,
+        );
+
+        let value = Self {
+            montgomery_form,
+            residue_params: self.residue_params,
+        };
+
+        (value, is_some)
+    }
+}
+
+impl<const LIMBS: usize> Invert for DynResidue<LIMBS> {
+    type Output = CtOption<Self>;
+    fn invert(&self) -> Self::Output {
+        let (value, is_some) = self.invert();
+        CtOption::new(value, is_some.into())
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs
new file mode 100644
index 000000000..30c4b9c04
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs
@@ -0,0 +1,84 @@
+use core::ops::{Mul, MulAssign};
+
+use crate::{
+    modular::mul::{mul_montgomery_form, square_montgomery_form},
+    traits::Square,
+};
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Multiplies by `rhs`.
+    pub const fn mul(&self, rhs: &Self) -> Self {
+        Self {
+            montgomery_form: mul_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &self.residue_params.modulus,
+                self.residue_params.mod_neg_inv,
+            ),
+            residue_params: self.residue_params,
+        }
+    }
+
+    /// Computes the (reduced) square of a residue.
+    pub const fn square(&self) -> Self {
+        Self {
+            montgomery_form: square_montgomery_form(
+                &self.montgomery_form,
+                &self.residue_params.modulus,
+                self.residue_params.mod_neg_inv,
+            ),
+            residue_params: self.residue_params,
+        }
+    }
+}
+
+impl<const LIMBS: usize> Mul<&DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn mul(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        debug_assert_eq!(self.residue_params, rhs.residue_params);
+        self.mul(rhs)
+    }
+}
+
+impl<const LIMBS: usize> Mul<DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn mul(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        self * &rhs
+    }
+}
+
+impl<const LIMBS: usize> Mul<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn mul(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self * rhs
+    }
+}
+
+impl<const LIMBS: usize> Mul<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn mul(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self * &rhs
+    }
+}
+
+impl<const LIMBS: usize> MulAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn mul_assign(&mut self, rhs: &DynResidue<LIMBS>) {
+        *self = *self * rhs;
+    }
+}
+
+impl<const LIMBS: usize> MulAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn mul_assign(&mut self, rhs: DynResidue<LIMBS>) {
+        *self *= &rhs;
+    }
+}
+
+impl<const LIMBS: usize> Square for DynResidue<LIMBS> {
+    fn square(&self) -> Self {
+        DynResidue::square(self)
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs
new file mode 100644
index 000000000..fca1ff875
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs
@@ -0,0 +1,24 @@
+use core::ops::Neg;
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Negates the number.
+    pub const fn neg(&self) -> Self {
+        Self::zero(self.residue_params).sub(self)
+    }
+}
+
+impl<const LIMBS: usize> Neg for DynResidue<LIMBS> {
+    type Output = Self;
+    fn neg(self) -> Self {
+        DynResidue::neg(&self)
+    }
+}
+
+impl<const LIMBS: usize> Neg for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn neg(self) -> DynResidue<LIMBS> {
+        DynResidue::neg(self)
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs
new file mode 100644
index 000000000..270f4c01c
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs
@@ -0,0 +1,35 @@
+use crate::{modular::pow::pow_montgomery_form, PowBoundedExp, Uint};
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Raises to the `exponent` power.
+    pub const fn pow(&self, exponent: &Uint<LIMBS>) -> DynResidue<LIMBS> {
+        self.pow_bounded_exp(exponent, Uint::<LIMBS>::BITS)
+    }
+
+    /// Raises to the `exponent` power,
+    /// with `exponent_bits` representing the number of (least significant) bits
+    /// to take into account for the exponent.
+    ///
+    /// NOTE: `exponent_bits` may be leaked in the time pattern.
+    pub const fn pow_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: usize) -> Self {
+        Self {
+            montgomery_form: pow_montgomery_form(
+                &self.montgomery_form,
+                exponent,
+                exponent_bits,
+                &self.residue_params.modulus,
+                &self.residue_params.r,
+                self.residue_params.mod_neg_inv,
+            ),
+            residue_params: self.residue_params,
+        }
+    }
+}
+
+impl<const LIMBS: usize> PowBoundedExp<Uint<LIMBS>> for DynResidue<LIMBS> {
+    fn pow_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: usize) -> Self {
+        self.pow_bounded_exp(exponent, exponent_bits)
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs
new file mode 100644
index 000000000..dd6fd84c8
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs
@@ -0,0 +1,92 @@
+use core::ops::{Sub, SubAssign};
+
+use crate::modular::sub::sub_montgomery_form;
+
+use super::DynResidue;
+
+impl<const LIMBS: usize> DynResidue<LIMBS> {
+    /// Subtracts `rhs`.
+    pub const fn sub(&self, rhs: &Self) -> Self {
+        Self {
+            montgomery_form: sub_montgomery_form(
+                &self.montgomery_form,
+                &rhs.montgomery_form,
+                &self.residue_params.modulus,
+            ),
+            residue_params: self.residue_params,
+        }
+    }
+}
+
+impl<const LIMBS: usize> Sub<&DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn sub(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        debug_assert_eq!(self.residue_params, rhs.residue_params);
+        self.sub(rhs)
+    }
+}
+
+impl<const LIMBS: usize> Sub<DynResidue<LIMBS>> for &DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn sub(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        self - &rhs
+    }
+}
+
+impl<const LIMBS: usize> Sub<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    #[allow(clippy::op_ref)]
+    fn sub(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self - rhs
+    }
+}
+
+impl<const LIMBS: usize> Sub<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    type Output = DynResidue<LIMBS>;
+    fn sub(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> {
+        &self - &rhs
+    }
+}
+
+impl<const LIMBS: usize> SubAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn sub_assign(&mut self, rhs: &DynResidue<LIMBS>) {
+        *self = *self - rhs;
+    }
+}
+
+impl<const LIMBS: usize> SubAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> {
+    fn sub_assign(&mut self, rhs: DynResidue<LIMBS>) {
+        *self -= &rhs;
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{
+        modular::runtime_mod::{DynResidue, DynResidueParams},
+        U256,
+    };
+
+    #[test]
+    fn sub_overflow() {
+        let params = DynResidueParams::new(&U256::from_be_hex(
+            "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551",
+        ));
+
+        let x =
+            U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56");
+        let mut x_mod = DynResidue::new(&x, params);
+
+        let y =
+            U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251");
+        let y_mod = DynResidue::new(&y, params);
+
+        x_mod -= &y_mod;
+
+        let expected =
+            U256::from_be_hex("6f357a71e1d5a03167f34879d469352add829491c6df41ddff65387d7ed56f56");
+
+        assert_eq!(expected, x_mod.retrieve());
+    }
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/sub.rs b/vendor/crypto-bigint/src/uint/modular/sub.rs
new file mode 100644
index 000000000..9c4717033
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/sub.rs
@@ -0,0 +1,9 @@
+use crate::Uint;
+
+pub(crate) const fn sub_montgomery_form<const LIMBS: usize>(
+    a: &Uint<LIMBS>,
+    b: &Uint<LIMBS>,
+    modulus: &Uint<LIMBS>,
+) -> Uint<LIMBS> {
+    a.sub_mod(b, modulus)
+}