Merging upstream version 1.71.1+dfsg1.

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

1 files changed, 424 insertions, 176 deletions

diff --git a/vendor/crypto-bigint/src/uint/div.rs b/vendor/crypto-bigint/src/uint/div.rs
index f7d9d6bf3..90741c472 100644
--- a/vendor/crypto-bigint/src/uint/div.rs
+++ b/vendor/crypto-bigint/src/uint/div.rs
@@ -1,33 +1,68 @@
-//! [`UInt`] division operations.
+//! [`Uint`] division operations.
 
-use super::UInt;
-use crate::limb::Word;
-use crate::{Integer, Limb, NonZero, Wrapping};
+use super::div_limb::{div_rem_limb_with_reciprocal, Reciprocal};
+use crate::{CtChoice, Limb, NonZero, Uint, Word, Wrapping};
 use core::ops::{Div, DivAssign, Rem, RemAssign};
-use subtle::{Choice, CtOption};
+use subtle::CtOption;
+
+impl<const LIMBS: usize> Uint<LIMBS> {
+    /// Computes `self` / `rhs` using a pre-made reciprocal,
+    /// returns the quotient (q) and remainder (r).
+    #[inline(always)]
+    pub const fn ct_div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
+        div_rem_limb_with_reciprocal(self, reciprocal)
+    }
+
+    /// Computes `self` / `rhs` using a pre-made reciprocal,
+    /// returns the quotient (q) and remainder (r).
+    #[inline(always)]
+    pub fn div_rem_limb_with_reciprocal(
+        &self,
+        reciprocal: &CtOption<Reciprocal>,
+    ) -> CtOption<(Self, Limb)> {
+        reciprocal.map(|r| div_rem_limb_with_reciprocal(self, &r))
+    }
+
+    /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r).
+    /// Returns the truthy value as the third element of the tuple if `rhs != 0`,
+    /// and the falsy value otherwise.
+    #[inline(always)]
+    pub(crate) const fn ct_div_rem_limb(&self, rhs: Limb) -> (Self, Limb, CtChoice) {
+        let (reciprocal, is_some) = Reciprocal::ct_new(rhs);
+        let (quo, rem) = div_rem_limb_with_reciprocal(self, &reciprocal);
+        (quo, rem, is_some)
+    }
+
+    /// Computes `self` / `rhs`, returns the quotient (q) and remainder (r).
+    #[inline(always)]
+    pub fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
+        // Guaranteed to succeed since `rhs` is nonzero.
+        let (quo, rem, _is_some) = self.ct_div_rem_limb(*rhs);
+        (quo, rem)
+    }
 
-impl<const LIMBS: usize> UInt<LIMBS> {
     /// Computes `self` / `rhs`, returns the quotient (q), remainder (r)
-    /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
-    /// NOTE: Use only if you need to access const fn. Otherwise use `div_rem` because
+    /// and the truthy value for is_some or the falsy value for is_none.
+    ///
+    /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::div_rem`] because
     /// the value for is_some needs to be checked before using `q` and `r`.
     ///
     /// This is variable only with respect to `rhs`.
     ///
     /// When used with a fixed `rhs`, this function is constant-time with respect
     /// to `self`.
-    pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, u8) {
+    pub(crate) const fn ct_div_rem(&self, rhs: &Self) -> (Self, Self, CtChoice) {
         let mb = rhs.bits_vartime();
-        let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
+        let mut bd = Self::BITS - mb;
         let mut rem = *self;
         let mut quo = Self::ZERO;
         let mut c = rhs.shl_vartime(bd);
 
         loop {
             let (mut r, borrow) = rem.sbb(&c, Limb::ZERO);
-            rem = Self::ct_select(r, rem, borrow.0);
+            rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
             r = quo.bitor(&Self::ONE);
-            quo = Self::ct_select(r, quo, borrow.0);
+            quo = Self::ct_select(&r, &quo, CtChoice::from_mask(borrow.0));
             if bd == 0 {
                 break;
             }
@@ -36,27 +71,28 @@ impl<const LIMBS: usize> UInt<LIMBS> {
             quo = quo.shl_vartime(1);
         }
 
-        let is_some = Limb(mb as Word).is_nonzero();
-        quo = Self::ct_select(Self::ZERO, quo, is_some);
-        (quo, rem, (is_some & 1) as u8)
+        let is_some = Limb(mb as Word).ct_is_nonzero();
+        quo = Self::ct_select(&Self::ZERO, &quo, is_some);
+        (quo, rem, is_some)
     }
 
     /// Computes `self` % `rhs`, returns the remainder and
-    /// and 1 for is_some or 0 for is_none. The results can be wrapped in [`CtOption`].
-    /// NOTE: Use only if you need to access const fn. Otherwise use `reduce`
+    /// and the truthy value for is_some or the falsy value for is_none.
+    ///
+    /// NOTE: Use only if you need to access const fn. Otherwise use [`Self::rem`].
     /// This is variable only with respect to `rhs`.
     ///
     /// When used with a fixed `rhs`, this function is constant-time with respect
     /// to `self`.
-    pub(crate) const fn ct_reduce(&self, rhs: &Self) -> (Self, u8) {
+    pub const fn const_rem(&self, rhs: &Self) -> (Self, CtChoice) {
         let mb = rhs.bits_vartime();
-        let mut bd = (LIMBS * Limb::BIT_SIZE) - mb;
+        let mut bd = Self::BITS - mb;
         let mut rem = *self;
         let mut c = rhs.shl_vartime(bd);
 
         loop {
             let (r, borrow) = rem.sbb(&c, Limb::ZERO);
-            rem = Self::ct_select(r, rem, borrow.0);
+            rem = Self::ct_select(&r, &rem, CtChoice::from_mask(borrow.0));
             if bd == 0 {
                 break;
             }
@@ -64,20 +100,55 @@ impl<const LIMBS: usize> UInt<LIMBS> {
             c = c.shr_vartime(1);
         }
 
-        let is_some = Limb(mb as Word).is_nonzero();
-        (rem, (is_some & 1) as u8)
+        let is_some = Limb(mb as Word).ct_is_nonzero();
+        (rem, is_some)
+    }
+
+    /// Computes `self` % `rhs`, returns the remainder and
+    /// and the truthy value for is_some or the falsy value for is_none.
+    ///
+    /// This is variable only with respect to `rhs`.
+    ///
+    /// When used with a fixed `rhs`, this function is constant-time with respect
+    /// to `self`.
+    pub const fn const_rem_wide(lower_upper: (Self, Self), rhs: &Self) -> (Self, CtChoice) {
+        let mb = rhs.bits_vartime();
+
+        // The number of bits to consider is two sets of limbs * BITS - mb (modulus bitcount)
+        let mut bd = (2 * Self::BITS) - mb;
+
+        // The wide integer to reduce, split into two halves
+        let (mut lower, mut upper) = lower_upper;
+
+        // Factor of the modulus, split into two halves
+        let mut c = Self::shl_vartime_wide((*rhs, Uint::ZERO), bd);
+
+        loop {
+            let (lower_sub, borrow) = lower.sbb(&c.0, Limb::ZERO);
+            let (upper_sub, borrow) = upper.sbb(&c.1, borrow);
+
+            lower = Self::ct_select(&lower_sub, &lower, CtChoice::from_mask(borrow.0));
+            upper = Self::ct_select(&upper_sub, &upper, CtChoice::from_mask(borrow.0));
+            if bd == 0 {
+                break;
+            }
+            bd -= 1;
+            c = Self::shr_vartime_wide(c, 1);
+        }
+
+        let is_some = Limb(mb as Word).ct_is_nonzero();
+        (lower, is_some)
     }
 
     /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
-    /// Limited to 2^16-1 since UInt doesn't support higher.
-    pub const fn reduce2k(&self, k: usize) -> Self {
+    /// Limited to 2^16-1 since Uint doesn't support higher.
+    pub const fn rem2k(&self, k: usize) -> Self {
         let highest = (LIMBS - 1) as u32;
-        let index = k as u32 / (Limb::BIT_SIZE as u32);
-        let res = Limb::ct_cmp(Limb::from_u32(index), Limb::from_u32(highest)) - 1;
-        let le = Limb::is_nonzero(Limb(res as Word));
+        let index = k as u32 / (Limb::BITS as u32);
+        let le = Limb::ct_le(Limb::from_u32(index), Limb::from_u32(highest));
         let word = Limb::ct_select(Limb::from_u32(highest), Limb::from_u32(index), le).0 as usize;
 
-        let base = k % Limb::BIT_SIZE;
+        let base = k % Limb::BITS;
         let mask = (1 << base) - 1;
         let mut out = *self;
 
@@ -94,266 +165,418 @@ impl<const LIMBS: usize> UInt<LIMBS> {
         out
     }
 
-    /// Computes self / rhs, returns the quotient, remainder
-    /// if rhs != 0
-    pub fn div_rem(&self, rhs: &Self) -> CtOption<(Self, Self)> {
-        let (q, r, c) = self.ct_div_rem(rhs);
-        CtOption::new((q, r), Choice::from(c))
+    /// Computes self / rhs, returns the quotient, remainder.
+    pub fn div_rem(&self, rhs: &NonZero<Self>) -> (Self, Self) {
+        // Since `rhs` is nonzero, this should always hold.
+        let (q, r, _c) = self.ct_div_rem(rhs);
+        (q, r)
     }
 
-    /// Computes self % rhs, returns the remainder
-    /// if rhs != 0
-    pub fn reduce(&self, rhs: &Self) -> CtOption<Self> {
-        let (r, c) = self.ct_reduce(rhs);
-        CtOption::new(r, Choice::from(c))
+    /// Computes self % rhs, returns the remainder.
+    pub fn rem(&self, rhs: &NonZero<Self>) -> Self {
+        // Since `rhs` is nonzero, this should always hold.
+        let (r, _c) = self.const_rem(rhs);
+        r
     }
 
     /// Wrapped division is just normal division i.e. `self` / `rhs`
     /// There’s no way wrapping could ever happen.
     /// This function exists, so that all operations are accounted for in the wrapping operations.
+    ///
+    /// Panics if `rhs == 0`.
     pub const fn wrapping_div(&self, rhs: &Self) -> Self {
         let (q, _, c) = self.ct_div_rem(rhs);
-        assert!(c == 1, "divide by zero");
+        assert!(c.is_true_vartime(), "divide by zero");
         q
     }
 
     /// Perform checked division, returning a [`CtOption`] which `is_some`
     /// only if the rhs != 0
     pub fn checked_div(&self, rhs: &Self) -> CtOption<Self> {
-        let (q, _, c) = self.ct_div_rem(rhs);
-        CtOption::new(q, Choice::from(c))
+        NonZero::new(*rhs).map(|rhs| {
+            let (q, _r) = self.div_rem(&rhs);
+            q
+        })
     }
 
     /// Wrapped (modular) remainder calculation is just `self` % `rhs`.
     /// There’s no way wrapping could ever happen.
     /// This function exists, so that all operations are accounted for in the wrapping operations.
+    ///
+    /// Panics if `rhs == 0`.
     pub const fn wrapping_rem(&self, rhs: &Self) -> Self {
-        let (r, c) = self.ct_reduce(rhs);
-        assert!(c == 1, "modulo zero");
+        let (r, c) = self.const_rem(rhs);
+        assert!(c.is_true_vartime(), "modulo zero");
         r
     }
 
     /// Perform checked reduction, returning a [`CtOption`] which `is_some`
     /// only if the rhs != 0
     pub fn checked_rem(&self, rhs: &Self) -> CtOption<Self> {
-        let (r, c) = self.ct_reduce(rhs);
-        CtOption::new(r, Choice::from(c))
+        NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
     }
 }
 
-impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+//
+// Division by a single limb
+//
+
+impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
-    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
         *self / *rhs
     }
 }
 
-impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Div<&NonZero<Limb>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
-    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
         self / *rhs
     }
 }
 
-impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Div<NonZero<Limb>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
-    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
         *self / rhs
     }
 }
 
-impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Div<NonZero<Limb>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
 
-    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
-        let (q, _, _) = self.ct_div_rem(&rhs);
+    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
+        let (q, _, _) = self.ct_div_rem_limb(*rhs);
         q
     }
 }
 
-impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
-        let (q, _, _) = self.ct_div_rem(rhs);
-        *self = q
+impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Uint<LIMBS> {
+    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
+        *self /= *rhs;
     }
 }
 
-impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
-        *self /= &rhs;
+impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Uint<LIMBS> {
+    fn div_assign(&mut self, rhs: NonZero<Limb>) {
+        *self = *self / rhs;
     }
 }
 
-impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Div<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
-        Wrapping(self.0.wrapping_div(rhs.as_ref()))
+    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
+        Wrapping(self.0 / rhs)
     }
 }
 
-impl<const LIMBS: usize> Div<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Div<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn div(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: NonZero<Limb>) -> Self::Output {
         *self / rhs
     }
 }
 
-impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Div<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
         *self / *rhs
     }
 }
 
-impl<const LIMBS: usize> Div<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Div<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn div(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn div(self, rhs: &NonZero<Limb>) -> Self::Output {
         self / *rhs
     }
 }
 
-impl<const LIMBS: usize> DivAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    fn div_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
-        *self = Wrapping(self.0.wrapping_div(rhs.as_ref()))
+impl<const LIMBS: usize> DivAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    fn div_assign(&mut self, rhs: &NonZero<Limb>) {
+        *self = Wrapping(self.0 / rhs)
     }
 }
 
-impl<const LIMBS: usize> DivAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    fn div_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+impl<const LIMBS: usize> DivAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    fn div_assign(&mut self, rhs: NonZero<Limb>) {
         *self /= &rhs;
     }
 }
 
-impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Uint<LIMBS> {
+    type Output = Limb;
 
-    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
         *self % *rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Uint<LIMBS> {
+    type Output = Limb;
 
-    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
         self % *rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Uint<LIMBS> {
+    type Output = Limb;
 
-    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
         *self % rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    type Output = UInt<LIMBS>;
+impl<const LIMBS: usize> Rem<NonZero<Limb>> for Uint<LIMBS> {
+    type Output = Limb;
 
-    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
-        let (r, _) = self.ct_reduce(&rhs);
+    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
+        let (_, r, _) = self.ct_div_rem_limb(*rhs);
         r
     }
 }
 
-impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
-        let (r, _) = self.ct_reduce(rhs);
-        *self = r
+impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Uint<LIMBS> {
+    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
+        *self = (*self % rhs).into();
     }
 }
 
-impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for UInt<LIMBS>
-where
-    UInt<LIMBS>: Integer,
-{
-    fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Uint<LIMBS> {
+    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
         *self %= &rhs;
     }
 }
 
-impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Rem<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Limb>;
+
+    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
+        Wrapping(self.0 % rhs)
+    }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Limb>;
+
+    fn rem(self, rhs: NonZero<Limb>) -> Self::Output {
+        *self % rhs
+    }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<Limb>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Limb>;
+
+    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
+        *self % *rhs
+    }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Limb>;
+
+    fn rem(self, rhs: &NonZero<Limb>) -> Self::Output {
+        self % *rhs
+    }
+}
+
+impl<const LIMBS: usize> RemAssign<NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    fn rem_assign(&mut self, rhs: NonZero<Limb>) {
+        *self %= &rhs;
+    }
+}
+
+impl<const LIMBS: usize> RemAssign<&NonZero<Limb>> for Wrapping<Uint<LIMBS>> {
+    fn rem_assign(&mut self, rhs: &NonZero<Limb>) {
+        *self = Wrapping((self.0 % rhs).into())
+    }
+}
+
+//
+// Division by an Uint
+//
+
+impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self / *rhs
+    }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        self / *rhs
+    }
+}
+
+impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self / rhs
+    }
+}
+
+impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        let (q, _) = self.div_rem(&rhs);
+        q
+    }
+}
+
+impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
+        *self /= *rhs
+    }
+}
+
+impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
+        *self = *self / rhs;
+    }
+}
+
+impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
+
+    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        Wrapping(self.0 / rhs)
+    }
+}
+
+impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
-        Wrapping(self.0.wrapping_rem(rhs.as_ref()))
+    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self / rhs
+    }
+}
+
+impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
+
+    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self / *rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
+
+    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        self / *rhs
+    }
+}
 
-    fn rem(self, rhs: NonZero<UInt<LIMBS>>) -> Self::Output {
+impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
+        *self = Wrapping(self.0 / rhs);
+    }
+}
+
+impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
+        *self /= &rhs;
+    }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self % *rhs
+    }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
+        self % *rhs
+    }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
         *self % rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for &Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    type Output = Uint<LIMBS>;
+
+    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        Self::rem(&self, &rhs)
+    }
+}
+
+impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
+        *self %= *rhs
+    }
+}
+
+impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Uint<LIMBS> {
+    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
+        *self = *self % rhs;
+    }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        Wrapping(self.0 % rhs)
+    }
+}
+
+impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
+
+    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
+        *self % rhs
+    }
+}
+
+impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
+
+    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
         *self % *rhs
     }
 }
 
-impl<const LIMBS: usize> Rem<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    type Output = Wrapping<UInt<LIMBS>>;
+impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    type Output = Wrapping<Uint<LIMBS>>;
 
-    fn rem(self, rhs: &NonZero<UInt<LIMBS>>) -> Self::Output {
+    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
         self % *rhs
     }
 }
 
-impl<const LIMBS: usize> RemAssign<NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    fn rem_assign(&mut self, rhs: NonZero<UInt<LIMBS>>) {
+impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
         *self %= &rhs;
     }
 }
 
-impl<const LIMBS: usize> RemAssign<&NonZero<UInt<LIMBS>>> for Wrapping<UInt<LIMBS>> {
-    fn rem_assign(&mut self, rhs: &NonZero<UInt<LIMBS>>) {
-        *self = Wrapping(self.0.wrapping_rem(rhs.as_ref()))
+impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Uint<LIMBS>> {
+    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
+        *self = Wrapping(self.0 % rhs)
     }
 }
 
@@ -387,7 +610,7 @@ mod tests {
             let lhs = U256::from(*n);
             let rhs = U256::from(*d);
             let (q, r, is_some) = lhs.ct_div_rem(&rhs);
-            assert_eq!(is_some, 1);
+            assert!(is_some.is_true_vartime());
             assert_eq!(U256::from(*e), q);
             assert_eq!(U256::from(*ee), r);
         }
@@ -401,9 +624,9 @@ mod tests {
             let num = U256::random(&mut rng).shr_vartime(128);
             let den = U256::random(&mut rng).shr_vartime(128);
             let n = num.checked_mul(&den);
-            if n.is_some().unwrap_u8() == 1 {
+            if n.is_some().into() {
                 let (q, _, is_some) = n.unwrap().ct_div_rem(&den);
-                assert_eq!(is_some, 1);
+                assert!(is_some.is_true_vartime());
                 assert_eq!(q, num);
             }
         }
@@ -415,17 +638,17 @@ mod tests {
         let mut b = U256::ZERO;
         b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
         let q = a.wrapping_div(&b);
-        assert_eq!(q, UInt::ZERO);
+        assert_eq!(q, Uint::ZERO);
         a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
         b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
         let q = a.wrapping_div(&b);
-        assert_eq!(q, UInt::ZERO);
+        assert_eq!(q, Uint::ZERO);
     }
 
     #[test]
     fn div_zero() {
         let (q, r, is_some) = U256::ONE.ct_div_rem(&U256::ZERO);
-        assert_eq!(is_some, 0);
+        assert!(!is_some.is_true_vartime());
         assert_eq!(q, U256::ZERO);
         assert_eq!(r, U256::ONE);
     }
@@ -433,36 +656,49 @@ mod tests {
     #[test]
     fn div_one() {
         let (q, r, is_some) = U256::from(10u8).ct_div_rem(&U256::ONE);
-        assert_eq!(is_some, 1);
+        assert!(is_some.is_true_vartime());
         assert_eq!(q, U256::from(10u8));
         assert_eq!(r, U256::ZERO);
     }
 
     #[test]
     fn reduce_one() {
-        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::ONE);
-        assert_eq!(is_some, 1);
+        let (r, is_some) = U256::from(10u8).const_rem(&U256::ONE);
+        assert!(is_some.is_true_vartime());
         assert_eq!(r, U256::ZERO);
     }
 
     #[test]
     fn reduce_zero() {
         let u = U256::from(10u8);
-        let (r, is_some) = u.ct_reduce(&U256::ZERO);
-        assert_eq!(is_some, 0);
+        let (r, is_some) = u.const_rem(&U256::ZERO);
+        assert!(!is_some.is_true_vartime());
         assert_eq!(r, u);
     }
 
     #[test]
     fn reduce_tests() {
-        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(2u8));
-        assert_eq!(is_some, 1);
+        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(2u8));
+        assert!(is_some.is_true_vartime());
         assert_eq!(r, U256::ZERO);
-        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(3u8));
-        assert_eq!(is_some, 1);
+        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(3u8));
+        assert!(is_some.is_true_vartime());
         assert_eq!(r, U256::ONE);
-        let (r, is_some) = U256::from(10u8).ct_reduce(&U256::from(7u8));
-        assert_eq!(is_some, 1);
+        let (r, is_some) = U256::from(10u8).const_rem(&U256::from(7u8));
+        assert!(is_some.is_true_vartime());
+        assert_eq!(r, U256::from(3u8));
+    }
+
+    #[test]
+    fn reduce_tests_wide_zero_padded() {
+        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(2u8));
+        assert!(is_some.is_true_vartime());
+        assert_eq!(r, U256::ZERO);
+        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(3u8));
+        assert!(is_some.is_true_vartime());
+        assert_eq!(r, U256::ONE);
+        let (r, is_some) = U256::const_rem_wide((U256::from(10u8), U256::ZERO), &U256::from(7u8));
+        assert!(is_some.is_true_vartime());
         assert_eq!(r, U256::from(3u8));
     }
 
@@ -472,7 +708,7 @@ mod tests {
         let mut b = U256::ZERO;
         b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
         let r = a.wrapping_rem(&b);
-        assert_eq!(r, UInt::ZERO);
+        assert_eq!(r, Uint::ZERO);
         a.limbs[a.limbs.len() - 1] = Limb(1 << (HI_BIT - 7));
         b.limbs[b.limbs.len() - 1] = Limb(0x82 << (HI_BIT - 7));
         let r = a.wrapping_rem(&b);
@@ -481,16 +717,28 @@ mod tests {
 
     #[cfg(feature = "rand")]
     #[test]
-    fn reduce2krand() {
+    fn rem2krand() {
         let mut rng = ChaChaRng::from_seed([7u8; 32]);
         for _ in 0..25 {
             let num = U256::random(&mut rng);
             let k = (rng.next_u32() % 256) as usize;
             let den = U256::ONE.shl_vartime(k);
 
-            let a = num.reduce2k(k);
+            let a = num.rem2k(k);
             let e = num.wrapping_rem(&den);
             assert_eq!(a, e);
         }
     }
+
+    #[test]
+    fn rem_trait() {
+        let a = U256::from(10u64);
+        let b = NonZero::new(U256::from(3u64)).unwrap();
+        let c = U256::from(1u64);
+
+        assert_eq!(a % b, c);
+        assert_eq!(a % &b, c);
+        assert_eq!(&a % b, c);
+        assert_eq!(&a % &b, c);
+    }
 }