crypto_bigint/uint/
div.rs

1//! [`Uint`] division operations.
2
3use super::div_limb::Reciprocal;
4use crate::{
5    CheckedDiv, CtOption, Div, DivAssign, DivRemLimb, DivVartime, Limb, NonZero, Rem, RemAssign,
6    RemLimb, RemMixed, ToUnsigned, Uint, UintRef, Unsigned, Wrapping,
7};
8
9impl<const LIMBS: usize> Uint<LIMBS> {
10    /// Computes `self / rhs` using a pre-made reciprocal, returning the quotient
11    /// and remainder.
12    #[must_use]
13    pub const fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
14        let mut quo = *self;
15        let rem = quo
16            .as_mut_uint_ref()
17            .div_rem_limb_with_reciprocal(reciprocal);
18        (quo, rem)
19    }
20
21    /// Computes `self / rhs`, returning the quotient and remainder.
22    #[must_use]
23    pub const fn div_rem_limb(&self, rhs: NonZero<Limb>) -> (Self, Limb) {
24        let mut quo = *self;
25        let rem = quo.as_mut_uint_ref().div_rem_limb(rhs);
26        (quo, rem)
27    }
28
29    /// Computes `self % rhs` using a pre-made reciprocal.
30    #[must_use]
31    pub const fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
32        self.as_uint_ref()
33            .rem_limb_with_reciprocal(reciprocal, Limb::ZERO)
34    }
35
36    /// Computes `self % rhs` for a `Limb`-sized divisor.
37    #[must_use]
38    pub const fn rem_limb(&self, rhs: NonZero<Limb>) -> Limb {
39        self.as_uint_ref().rem_limb(rhs)
40    }
41
42    /// Computes `self` / `rhs`, returning the quotient and the remainder.
43    ///
44    /// This function is constant-time with respect to both `self` and `rhs`.
45    #[must_use]
46    pub const fn div_rem<const RHS_LIMBS: usize>(
47        &self,
48        rhs: &NonZero<Uint<RHS_LIMBS>>,
49    ) -> (Self, Uint<RHS_LIMBS>) {
50        let (mut x, mut y) = (*self, *rhs.as_ref());
51        UintRef::div_rem(x.as_mut_uint_ref(), y.as_mut_uint_ref());
52        (x, y)
53    }
54
55    /// Computes `self` / `rhs`, returning the quotient and the remainder.
56    ///
57    /// This is variable-time only with respect to `rhs`.
58    ///
59    /// When used with a fixed `rhs`, this function is constant-time with respect
60    /// to `self`.
61    #[inline]
62    #[must_use]
63    pub const fn div_rem_vartime<const RHS_LIMBS: usize>(
64        &self,
65        rhs: &NonZero<Uint<RHS_LIMBS>>,
66    ) -> (Self, Uint<RHS_LIMBS>) {
67        let (mut x, mut y) = (*self, *rhs.as_ref());
68        UintRef::div_rem_vartime(x.as_mut_uint_ref(), y.as_mut_uint_ref());
69        (x, y)
70    }
71
72    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
73    #[must_use]
74    pub const fn div_exact<const RHS_LIMBS: usize>(
75        &self,
76        rhs: &NonZero<Uint<RHS_LIMBS>>,
77    ) -> CtOption<Self> {
78        let mut quo = *self;
79        let mut div = rhs.get_copy();
80        let exact = quo.as_mut_uint_ref().div_exact(div.as_mut_uint_ref());
81        CtOption::new(quo, exact)
82    }
83
84    /// Exactly divides `self` by `rhs`, returning `CtOption::none()` if `self` is not divisible by `rhs`.
85    ///
86    /// This is variable-time only with respect to `rhs`.
87    ///
88    /// When used with a fixed `rhs`, this function is constant-time with respect to `self`.
89    #[must_use]
90    pub const fn div_exact_vartime<const RHS_LIMBS: usize>(
91        &self,
92        rhs: &NonZero<Uint<RHS_LIMBS>>,
93    ) -> CtOption<Self> {
94        let mut quo = *self;
95        let mut div = rhs.get_copy();
96        let exact = quo
97            .as_mut_uint_ref()
98            .div_exact_vartime(div.as_mut_uint_ref());
99        CtOption::new(quo, exact)
100    }
101
102    /// Computes self / rhs, assigning the quotient to `self` and returning the remainder.
103    #[must_use]
104    pub(crate) fn div_rem_assign<Rhs: Unsigned>(&mut self, rhs: NonZero<Rhs>) -> Rhs {
105        let mut rem = rhs.get();
106        self.as_mut_uint_ref().div_rem(rem.as_mut_uint_ref());
107        rem
108    }
109
110    /// Computes `self` % `rhs`.
111    #[must_use]
112    pub const fn rem<const RHS_LIMBS: usize>(
113        &self,
114        rhs: &NonZero<Uint<RHS_LIMBS>>,
115    ) -> Uint<RHS_LIMBS> {
116        let (mut x, mut y) = (*self, *rhs.as_ref());
117        UintRef::div_rem(x.as_mut_uint_ref(), y.as_mut_uint_ref());
118        y
119    }
120
121    /// Computes `self` % `rhs` in variable-time with respect to `rhs`.
122    ///
123    /// When used with a fixed `rhs`, this function is constant-time with respect
124    /// to `self`.
125    #[inline]
126    #[must_use]
127    pub const fn rem_vartime<const RHS_LIMBS: usize>(
128        &self,
129        rhs: &NonZero<Uint<RHS_LIMBS>>,
130    ) -> Uint<RHS_LIMBS> {
131        let (mut x, mut y) = (*self, *rhs.as_ref());
132        UintRef::div_rem_vartime(x.as_mut_uint_ref(), y.as_mut_uint_ref());
133        y
134    }
135
136    /// Computes `self` % `rhs` for a double-width `Uint`.
137    #[inline]
138    #[must_use]
139    pub const fn rem_wide(mut lower_upper: (Self, Self), rhs: &NonZero<Self>) -> Self {
140        let mut y = *rhs.as_ref();
141        UintRef::rem_wide(
142            (
143                lower_upper.0.as_mut_uint_ref(),
144                lower_upper.1.as_mut_uint_ref(),
145            ),
146            y.as_mut_uint_ref(),
147        );
148        y
149    }
150
151    /// Computes `self` % `rhs`.
152    ///
153    /// This is variable-time only with respect to `rhs`.
154    ///
155    /// When used with a fixed `rhs`, this function is constant-time with respect
156    /// to `self`.
157    #[inline]
158    #[must_use]
159    pub const fn rem_wide_vartime(mut lower_upper: (Self, Self), rhs: &NonZero<Self>) -> Self {
160        let mut y = *rhs.as_ref();
161        UintRef::rem_wide_vartime(
162            (
163                lower_upper.0.as_mut_uint_ref(),
164                lower_upper.1.as_mut_uint_ref(),
165            ),
166            y.as_mut_uint_ref(),
167        );
168        y
169    }
170
171    /// Computes `self` % 2^k. Faster than reduce since its a power of 2.
172    /// Limited to 2^16-1 since Uint doesn't support higher.
173    ///
174    /// ### Usage:
175    /// ```
176    /// use crypto_bigint::{U448, Limb};
177    ///
178    /// let a = U448::from(10_u64);
179    /// let k = 3; // 2^3 = 8
180    /// let remainder = a.rem2k_vartime(k);
181    ///
182    /// // As 10 % 8 = 2
183    /// assert_eq!(remainder, U448::from(2_u64));
184    /// ```
185    #[must_use]
186    pub const fn rem2k_vartime(&self, k: u32) -> Self {
187        self.restrict_bits(k)
188    }
189
190    /// Wrapped division is just normal division i.e. `self` / `rhs`.
191    ///
192    /// There’s no way wrapping could ever happen.
193    /// This function exists, so that all operations are accounted for in the wrapping operations.
194    #[must_use]
195    pub const fn wrapping_div(&self, rhs: &NonZero<Self>) -> Self {
196        self.div_rem(rhs).0
197    }
198
199    /// Wrapped division is just normal division i.e. `self` / `rhs`.
200    ///
201    /// There’s no way wrapping could ever happen.
202    /// This function exists, so that all operations are accounted for in the wrapping operations.
203    #[must_use]
204    pub const fn wrapping_div_vartime<const RHS: usize>(&self, rhs: &NonZero<Uint<RHS>>) -> Self {
205        self.div_rem_vartime(rhs).0
206    }
207
208    /// Perform checked division, returning a [`CtOption`] which `is_some`
209    /// only if the rhs != 0.
210    ///
211    /// ### Usage:
212    /// ```
213    /// use crypto_bigint::{U448, NonZero};
214    ///
215    /// let a = U448::from(8_u64);
216    /// let result = NonZero::new(U448::from(4_u64))
217    ///     .map(|b| a.div_rem(&b))
218    ///     .expect("Division by zero");
219    ///
220    /// assert_eq!(result.0, U448::from(2_u64));
221    ///
222    /// // Check division by zero
223    /// let zero = U448::from(0_u64);
224    /// assert!(a.checked_div(&zero).is_none().to_bool(), "should be None for division by zero");
225    /// ```
226    #[must_use]
227    pub fn checked_div<const RHS_LIMBS: usize>(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
228        NonZero::new(*rhs).map(|rhs| self.div_rem(&rhs).0)
229    }
230
231    /// This function exists, so that all operations are accounted for in the wrapping operations.
232    ///
233    /// # Panics
234    /// - if `rhs == 0`.
235    ///
236    /// ### Usage:
237    /// ```
238    /// use crypto_bigint::U448;
239    ///
240    /// let a = U448::from(10_u64);
241    /// let b = U448::from(3_u64);
242    /// let remainder = a.wrapping_rem_vartime(&b);
243    ///
244    /// assert_eq!(remainder, U448::from(1_u64));
245    /// ```
246    #[must_use]
247    pub const fn wrapping_rem_vartime(&self, rhs: &Self) -> Self {
248        let nz_rhs = rhs.to_nz().expect_copied("non-zero divisor");
249        self.rem_vartime(&nz_rhs)
250    }
251
252    /// Perform checked reduction, returning a [`CtOption`] which `is_some`
253    /// only if the rhs != 0
254    ///
255    /// ### Usage:
256    /// ```
257    /// use crypto_bigint::{U448, NonZero};
258    ///
259    /// let a = U448::from(10_u64);
260    /// let remainder_option = NonZero::new(U448::from(3_u64))
261    ///     .map(|b| a.rem(&b));
262    ///
263    /// assert!(bool::from(remainder_option.is_some()));
264    ///
265    /// // Check reduction by zero
266    /// let zero = U448::from(0_u64);
267    ///
268    /// assert!(a.checked_rem(&zero).is_none().to_bool(), "should be None for reduction by zero");
269    /// ```
270    #[must_use]
271    pub fn checked_rem<const RHS_LIMBS: usize>(
272        &self,
273        rhs: &Uint<RHS_LIMBS>,
274    ) -> CtOption<Uint<RHS_LIMBS>> {
275        NonZero::new(*rhs).map(|rhs| self.rem(&rhs))
276    }
277}
278
279impl<const LIMBS: usize, const RHS_LIMBS: usize> CheckedDiv<Uint<RHS_LIMBS>> for Uint<LIMBS> {
280    fn checked_div(&self, rhs: &Uint<RHS_LIMBS>) -> CtOption<Self> {
281        self.checked_div(rhs)
282    }
283}
284
285impl<const LIMBS: usize, Rhs: Unsigned> Div<Rhs> for &Uint<LIMBS> {
286    type Output = Uint<LIMBS>;
287
288    #[inline]
289    fn div(self, rhs: Rhs) -> Self::Output {
290        *self / rhs
291    }
292}
293
294impl<const LIMBS: usize, Rhs: Unsigned> Div<Rhs> for Uint<LIMBS> {
295    type Output = Uint<LIMBS>;
296
297    #[inline]
298    fn div(self, rhs: Rhs) -> Self::Output {
299        self / NonZero::new(rhs).expect("attempt to divide with a divisor of zero")
300    }
301}
302
303impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &Uint<LIMBS> {
304    type Output = Uint<LIMBS>;
305
306    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
307        let mut quo = *self;
308        let _rem = quo.div_rem_assign(rhs.to_unsigned());
309        quo
310    }
311}
312
313impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for Uint<LIMBS> {
314    type Output = Self;
315
316    fn div(mut self, rhs: &NonZero<Rhs>) -> Self::Output {
317        let _rem = self.div_rem_assign(rhs.to_unsigned());
318        self
319    }
320}
321
322impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for &Uint<LIMBS> {
323    type Output = Uint<LIMBS>;
324
325    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
326        let mut quo = *self;
327        let _rem = quo.div_rem_assign(rhs);
328        quo
329    }
330}
331
332impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for Uint<LIMBS> {
333    type Output = Self;
334
335    fn div(mut self, rhs: NonZero<Rhs>) -> Self::Output {
336        let _rem = self.div_rem_assign(rhs);
337        self
338    }
339}
340
341impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>> for Uint<LIMBS> {
342    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
343        let _rem = self.div_rem_assign(rhs.to_unsigned());
344    }
345}
346
347impl<const LIMBS: usize, Rhs: Unsigned> DivAssign<NonZero<Rhs>> for Uint<LIMBS> {
348    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
349        let _rem = self.div_rem_assign(rhs);
350    }
351}
352
353impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
354    type Output = Self;
355
356    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
357        Wrapping(self.0 / rhs)
358    }
359}
360
361impl<const LIMBS: usize, Rhs: Unsigned> Div<NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
362    type Output = Wrapping<Uint<LIMBS>>;
363
364    fn div(self, rhs: NonZero<Rhs>) -> Self::Output {
365        Wrapping(self.0 / rhs)
366    }
367}
368
369impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
370    type Output = Wrapping<Uint<LIMBS>>;
371
372    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
373        Wrapping(self.0 / rhs)
374    }
375}
376
377impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Div<&NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
378    type Output = Self;
379
380    fn div(self, rhs: &NonZero<Rhs>) -> Self::Output {
381        Wrapping(self.0 / rhs)
382    }
383}
384
385impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> DivAssign<&NonZero<Rhs>>
386    for Wrapping<Uint<LIMBS>>
387{
388    fn div_assign(&mut self, rhs: &NonZero<Rhs>) {
389        self.0 /= rhs;
390    }
391}
392
393impl<const LIMBS: usize, Rhs: Unsigned> DivAssign<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
394    fn div_assign(&mut self, rhs: NonZero<Rhs>) {
395        self.0 /= rhs;
396    }
397}
398
399impl<const LIMBS: usize> DivVartime for Uint<LIMBS> {
400    fn div_vartime(&self, rhs: &NonZero<Uint<LIMBS>>) -> Self {
401        self.div_rem_vartime(rhs).0
402    }
403}
404
405impl<const LIMBS: usize, Rhs: Unsigned> Rem<Rhs> for &Uint<LIMBS> {
406    type Output = Rhs;
407
408    #[inline]
409    fn rem(self, rhs: Rhs) -> Self::Output {
410        *self % rhs
411    }
412}
413
414impl<const LIMBS: usize, Rhs: Unsigned> Rem<Rhs> for Uint<LIMBS> {
415    type Output = Rhs;
416
417    #[inline]
418    fn rem(self, rhs: Rhs) -> Self::Output {
419        self % NonZero::new(rhs).expect("attempt to calculate the remainder with a divisor of zero")
420    }
421}
422
423impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for &Uint<LIMBS> {
424    type Output = Rhs::Unsigned;
425
426    #[inline]
427    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
428        (*self).rem(rhs)
429    }
430}
431
432impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for Uint<LIMBS> {
433    type Output = Rhs::Unsigned;
434
435    #[inline]
436    fn rem(mut self, rhs: &NonZero<Rhs>) -> Self::Output {
437        self.div_rem_assign(rhs.to_unsigned())
438    }
439}
440
441impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for &Uint<LIMBS> {
442    type Output = Rhs;
443
444    #[inline]
445    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
446        (*self).rem(rhs)
447    }
448}
449
450impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for Uint<LIMBS> {
451    type Output = Rhs;
452
453    #[inline]
454    fn rem(mut self, rhs: NonZero<Rhs>) -> Self::Output {
455        self.div_rem_assign(rhs)
456    }
457}
458
459impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
460    type Output = Wrapping<Rhs>;
461
462    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
463        Wrapping(self.0 % rhs)
464    }
465}
466
467impl<const LIMBS: usize, Rhs: Unsigned> Rem<NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
468    type Output = Wrapping<Rhs>;
469
470    fn rem(self, rhs: NonZero<Rhs>) -> Self::Output {
471        *self % rhs
472    }
473}
474
475impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for &Wrapping<Uint<LIMBS>> {
476    type Output = Wrapping<Rhs::Unsigned>;
477
478    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
479        *self % rhs.to_unsigned()
480    }
481}
482
483impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> Rem<&NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
484    type Output = Wrapping<Rhs::Unsigned>;
485
486    fn rem(self, rhs: &NonZero<Rhs>) -> Self::Output {
487        self % rhs.to_unsigned()
488    }
489}
490
491impl<const LIMBS: usize, Rhs: Unsigned> RemAssign<NonZero<Rhs>> for Uint<LIMBS> {
492    fn rem_assign(&mut self, rhs: NonZero<Rhs>) {
493        let rem = *self % rhs;
494        *self = rem.as_uint_ref().to_uint_resize();
495    }
496}
497
498impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> RemAssign<&NonZero<Rhs>> for Uint<LIMBS> {
499    fn rem_assign(&mut self, rhs: &NonZero<Rhs>) {
500        *self %= rhs.to_unsigned();
501    }
502}
503
504impl<const LIMBS: usize, Rhs: Unsigned> RemAssign<NonZero<Rhs>> for Wrapping<Uint<LIMBS>> {
505    fn rem_assign(&mut self, rhs: NonZero<Rhs>) {
506        *self %= &rhs;
507    }
508}
509
510impl<const LIMBS: usize, Rhs: ToUnsigned + ?Sized> RemAssign<&NonZero<Rhs>>
511    for Wrapping<Uint<LIMBS>>
512{
513    fn rem_assign(&mut self, rhs: &NonZero<Rhs>) {
514        self.0 %= rhs;
515    }
516}
517
518impl<const LIMBS: usize> DivRemLimb for Uint<LIMBS> {
519    fn div_rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> (Self, Limb) {
520        Self::div_rem_limb_with_reciprocal(self, reciprocal)
521    }
522}
523
524impl<const LIMBS: usize> RemLimb for Uint<LIMBS> {
525    fn rem_limb_with_reciprocal(&self, reciprocal: &Reciprocal) -> Limb {
526        Self::rem_limb_with_reciprocal(self, reciprocal)
527    }
528}
529
530impl<const LIMBS: usize, Rhs: Unsigned> RemMixed<Rhs> for Uint<LIMBS> {
531    fn rem_mixed(&self, reductor: &NonZero<Rhs>) -> Rhs {
532        let (mut quo, mut rem) = (*self, reductor.as_ref().clone());
533        quo.as_mut_uint_ref().div_rem(rem.as_mut_uint_ref());
534        rem
535    }
536}
537
538#[cfg(test)]
539#[allow(clippy::integer_division_remainder_used, reason = "test")]
540mod tests {
541    use crate::{
542        CtAssign, DivVartime, Limb, NonZero, One, RemMixed, U64, U128, U256, U512, U896, U1024,
543        Uint, Word, Wrapping, Zero,
544    };
545
546    #[cfg(feature = "rand_core")]
547    use {crate::Random, chacha20::ChaCha8Rng, rand_core::Rng, rand_core::SeedableRng};
548
549    #[test]
550    fn div_word() {
551        for (n, d, e, ee) in &[
552            (200u64, 2u64, 100u64, 0),
553            (100u64, 25u64, 4u64, 0),
554            (100u64, 10u64, 10u64, 0),
555            (1024u64, 8u64, 128u64, 0),
556            (27u64, 13u64, 2u64, 1u64),
557            (26u64, 13u64, 2u64, 0u64),
558            (14u64, 13u64, 1u64, 1u64),
559            (13u64, 13u64, 1u64, 0u64),
560            (12u64, 13u64, 0u64, 12u64),
561            (1u64, 13u64, 0u64, 1u64),
562        ] {
563            let lhs = U256::from(*n);
564            let rhs = NonZero::new(U256::from(*d)).unwrap();
565            let (q, r) = lhs.div_rem(&rhs);
566            assert_eq!(U256::from(*e), q);
567            assert_eq!(U256::from(*ee), r);
568            let (q, r) = lhs.div_rem_vartime(&rhs);
569            assert_eq!(U256::from(*e), q);
570            assert_eq!(U256::from(*ee), r);
571            let q = lhs.div_exact(&rhs).into_option();
572            assert_eq!(if *ee == 0 { Some(U256::from(*e)) } else { None }, q);
573            let q = lhs.div_exact_vartime(&rhs).into_option();
574            assert_eq!(if *ee == 0 { Some(U256::from(*e)) } else { None }, q);
575        }
576    }
577
578    #[cfg(feature = "rand_core")]
579    #[test]
580    fn div() {
581        let mut rng = ChaCha8Rng::from_seed([7u8; 32]);
582        for _ in 0..25 {
583            let num = U256::random_from_rng(&mut rng)
584                .overflowing_shr_vartime(128)
585                .unwrap();
586            let den = NonZero::new(
587                U256::random_from_rng(&mut rng)
588                    .overflowing_shr_vartime(128)
589                    .unwrap(),
590            )
591            .unwrap();
592            let n = num.checked_mul(den.as_ref());
593            if n.is_some().into() {
594                let n = n.unwrap();
595                let (q, _) = n.div_rem(&den);
596                assert_eq!(q, num);
597                let (q, _) = n.div_rem_vartime(&den);
598                assert_eq!(q, num);
599                let q = n.div_exact(&den).into_option();
600                assert_eq!(q, Some(num));
601                let q = n.div_exact_vartime(&den).into_option();
602                assert_eq!(q, Some(num));
603            }
604        }
605    }
606
607    #[test]
608    fn div_max() {
609        let mut a = U256::ZERO;
610        let mut b = U256::ZERO;
611        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
612        let q = a.wrapping_div(&NonZero::new(b).unwrap());
613        assert_eq!(q, Uint::ZERO);
614        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
615        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
616        let b = NonZero::new(b).unwrap();
617        let q = a.wrapping_div(&b);
618        assert_eq!(q, Uint::ZERO);
619    }
620
621    #[test]
622    fn div_one() {
623        let (q, r) = U256::from(10u8).div_rem(&NonZero::new(U256::ONE).unwrap());
624        assert_eq!(q, U256::from(10u8));
625        assert_eq!(r, U256::ZERO);
626        let (q, r) = U256::from(10u8).div_rem_vartime(&NonZero::new(U256::ONE).unwrap());
627        assert_eq!(q, U256::from(10u8));
628        assert_eq!(r, U256::ZERO);
629    }
630
631    #[test]
632    fn div_edge() {
633        let lo = U128::from_be_hex("00000000000000000000000000000001");
634        let hi = U128::from_be_hex("00000000000000000000000000000001");
635        let y = U128::from_be_hex("00000000000000010000000000000001");
636        let x = U256::from((lo, hi));
637        let expect = (U64::MAX.resize::<{ U256::LIMBS }>(), U256::from(2u64));
638
639        let (q1, r1) = Uint::div_rem(&x, &NonZero::new(y.resize()).unwrap());
640        assert_eq!((q1, r1), expect);
641        let (q2, r2) = Uint::div_rem_vartime(&x, &NonZero::new(y).unwrap());
642        assert_eq!((q2, r2.resize()), expect);
643        let r3 = Uint::rem(&x, &NonZero::new(y.resize()).unwrap());
644        assert_eq!(r3, expect.1);
645        let r4 = Uint::rem_vartime(&x, &NonZero::new(y.resize()).unwrap());
646        assert_eq!(r4, expect.1);
647        let r5 = Uint::rem_wide((lo, hi), &NonZero::new(y).unwrap());
648        assert_eq!(r5.resize(), expect.1);
649        let r6 = Uint::rem_wide_vartime((lo, hi), &NonZero::new(y).unwrap());
650        assert_eq!(r6.resize(), expect.1);
651    }
652
653    #[test]
654    fn div_rem_larger_denominator() {
655        // 1 = len(x) < len(y) and x < y
656        let x = U64::from_be_hex("8000000000000000");
657        let y = U128::from_be_hex("00000000000000010000000000000000")
658            .to_nz()
659            .unwrap();
660        let (quo, rem) = x.div_rem(&y);
661        assert_eq!(quo, Uint::ZERO);
662        assert_eq!(rem, x.resize());
663
664        // 1 = len(x) < len(y) and x > y
665        let x = U64::from_be_hex("8000000000000000");
666        let y = U128::from_be_hex("00000000000000000000000000001000")
667            .to_nz()
668            .unwrap();
669        let (quo, rem) = x.div_rem(&y);
670        assert_eq!(quo, U64::from_be_hex("0008000000000000"));
671        assert_eq!(rem, U128::ZERO);
672
673        // 2 = len(x) < len(y) and x < y
674        let x = U128::from_be_hex("80000000000000008000000000000000");
675        let y =
676            U256::from_be_hex("0000000000000001000000000000000000000000000000010000000000000000")
677                .to_nz()
678                .unwrap();
679        let (quo, rem) = x.div_rem(&y);
680        assert_eq!(quo, U128::ZERO);
681        assert_eq!(rem, x.resize());
682
683        // 2 = len(x) < len(y) and x > y
684        let x = U128::from_be_hex("80000000000000008000000000000000");
685        let y =
686            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000110000")
687                .to_nz()
688                .unwrap();
689        let (quo, rem) = x.div_rem(&y);
690        assert_eq!(quo, U128::from_be_hex("000007878787878787878f0f0f0f0f0f"));
691        assert_eq!(
692            rem,
693            U256::from_be_hex("0000000000000000000000000000000000000000000000000000000000010000",)
694        );
695    }
696
697    #[test]
698    fn div_rem_larger_numerator() {
699        let denom = U128::from_be_hex("AAAA0000FFFF11117777333344449999");
700        let (full_q, full_r) =
701            U1024::MAX.div_rem(&denom.resize::<{ U1024::LIMBS }>().to_nz().unwrap());
702
703        let (q, r) = U1024::MAX.div_rem(&denom.to_nz().unwrap());
704        assert_eq!(full_q, q);
705        assert_eq!(full_r.resize(), r);
706    }
707
708    #[allow(clippy::op_ref)]
709    #[test]
710    fn div_trait() {
711        let a = U256::from(10u64);
712        let b = NonZero::new(U256::from(2u64)).unwrap();
713        let c = U256::from(5u64);
714
715        assert_eq!(a / b, c);
716        assert_eq!(a / &b, c);
717        assert_eq!(&a / b, c);
718        assert_eq!(&a / &b, c);
719        assert_eq!(Wrapping(a) / b, Wrapping(c));
720        assert_eq!(Wrapping(a) / &b, Wrapping(c));
721        assert_eq!(&Wrapping(a) / b, Wrapping(c));
722        assert_eq!(&Wrapping(a) / &b, Wrapping(c));
723    }
724
725    #[allow(clippy::op_ref)]
726    #[test]
727    fn div_assign_trait() {
728        let a = U256::from(10u64);
729        let b = NonZero::new(U256::from(2u64)).unwrap();
730        let c = U256::from(5u64);
731
732        let mut res = a;
733        res /= b;
734        assert_eq!(res, c);
735        let mut res = a;
736        res /= &b;
737        assert_eq!(res, c);
738
739        let mut res = Wrapping(a);
740        res /= b;
741        assert_eq!(res, Wrapping(c));
742        let mut res = Wrapping(a);
743        res /= &b;
744        assert_eq!(res, Wrapping(c));
745    }
746
747    #[should_panic]
748    #[test]
749    fn div_zero() {
750        let _ = U256::ONE / U256::ZERO;
751    }
752
753    #[should_panic]
754    #[test]
755    #[allow(clippy::op_ref)]
756    fn div_ref_zero() {
757        let _ = &U256::ONE / U256::ZERO;
758    }
759
760    #[test]
761    fn reduce_one() {
762        let r = U256::from(10u8).rem_vartime(&NonZero::new(U256::ONE).unwrap());
763        assert_eq!(r, U256::ZERO);
764    }
765
766    #[test]
767    fn reduce_tests() {
768        let tests = [
769            (U256::from(2u8), 0u8),
770            (U256::from(3u8), 1u8),
771            (U256::from(7u8), 3u8),
772            (U256::MAX, 10u8),
773        ];
774        for (divisor, expect) in tests {
775            let r1 = U256::from(10u8).rem(&NonZero::new(divisor).unwrap());
776            let r2 = U256::from(10u8).rem_vartime(&NonZero::new(divisor).unwrap());
777            assert_eq!(r1, U256::from(expect));
778            assert_eq!(r1, r2);
779        }
780    }
781
782    #[test]
783    fn reduce_tests_wide_zero_padded() {
784        let tests = [
785            (U256::from(2u8), 0u8),
786            (U256::from(3u8), 1u8),
787            (U256::from(7u8), 3u8),
788            (U256::MAX, 10u8),
789        ];
790        for (divisor, expect) in tests {
791            let r1 = U256::rem_wide(
792                (U256::from(10u8), U256::ZERO),
793                &NonZero::new(divisor).unwrap(),
794            );
795            let r2 = U256::rem_wide_vartime(
796                (U256::from(10u8), U256::ZERO),
797                &NonZero::new(divisor).unwrap(),
798            );
799            assert_eq!(r1, U256::from(expect));
800            assert_eq!(r1, r2);
801        }
802    }
803
804    #[test]
805    fn rem_wide_corner_case() {
806        let modulus = "0000000000000000000000000000000081000000000000000000000000000001";
807        let modulus = NonZero::new(U256::from_be_hex(modulus)).expect("it's odd and not zero");
808        let lo_hi = (
809            U256::from_be_hex("1000000000000000000000000000000000000000000000000000000000000001"),
810            U256::ZERO,
811        );
812        let rem = U256::rem_wide(lo_hi, &modulus);
813        // Lower half is zero
814        assert_eq!(
815            &rem.to_be_bytes().as_ref()[0..16],
816            U128::ZERO.to_be_bytes().as_ref()
817        );
818        // Upper half
819        let expected = U128::from_be_hex("203F80FE03F80FE03F80FE03F80FE041");
820        assert_eq!(
821            &rem.to_be_bytes().as_ref()[16..],
822            expected.to_be_bytes().as_ref()
823        );
824
825        let remv = U256::rem_wide_vartime(lo_hi, &modulus);
826        assert_eq!(rem, remv);
827    }
828
829    #[test]
830    fn reduce_max() {
831        let mut a = U256::ZERO;
832        let mut b = U256::ZERO;
833        b.limbs[b.limbs.len() - 1] = Limb(Word::MAX);
834        let r = a.wrapping_rem_vartime(&b);
835        assert_eq!(r, Uint::ZERO);
836        a.limbs[a.limbs.len() - 1] = Limb(1 << (Limb::HI_BIT - 7));
837        b.limbs[b.limbs.len() - 1] = Limb(0x82 << (Limb::HI_BIT - 7));
838        let r = a.wrapping_rem_vartime(&b);
839        assert_eq!(r, a);
840    }
841
842    #[cfg(feature = "rand_core")]
843    #[test]
844    fn rem2krand() {
845        let mut rng = ChaCha8Rng::from_seed([7u8; 32]);
846        for _ in 0..25 {
847            let num = U256::random_from_rng(&mut rng);
848            let k = rng.next_u32() % 256;
849            let den = U256::ONE.overflowing_shl_vartime(k).unwrap();
850
851            let a = num.rem2k_vartime(k);
852            let e = num.wrapping_rem_vartime(&den);
853            assert_eq!(a, e);
854        }
855    }
856
857    #[allow(clippy::op_ref)]
858    #[test]
859    fn rem_trait() {
860        let a = U256::from(10u64);
861        let b = NonZero::new(U256::from(3u64)).unwrap();
862        let c = U256::from(1u64);
863
864        assert_eq!(a % b, c);
865        assert_eq!(a % &b, c);
866        assert_eq!(&a % b, c);
867        assert_eq!(&a % &b, c);
868        assert_eq!(Wrapping(a) % b, Wrapping(c));
869        assert_eq!(Wrapping(a) % &b, Wrapping(c));
870        assert_eq!(&Wrapping(a) % b, Wrapping(c));
871        assert_eq!(&Wrapping(a) % &b, Wrapping(c));
872    }
873
874    #[allow(clippy::op_ref)]
875    #[test]
876    fn rem_assign_trait() {
877        let a = U256::from(10u64);
878        let b = NonZero::new(U256::from(3u64)).unwrap();
879        let c = U256::from(1u64);
880
881        let mut res = a;
882        res %= b;
883        assert_eq!(res, c);
884        let mut res = a;
885        res %= &b;
886        assert_eq!(res, c);
887
888        let mut res = Wrapping(a);
889        res %= b;
890        assert_eq!(res, Wrapping(c));
891        let mut res = Wrapping(a);
892        res %= &b;
893        assert_eq!(res, Wrapping(c));
894    }
895
896    #[should_panic]
897    #[test]
898    fn rem_zero() {
899        let _ = U256::ONE % U256::ZERO;
900    }
901
902    #[should_panic]
903    #[test]
904    #[allow(clippy::op_ref)]
905    fn rem_ref_zero() {
906        let _ = &U256::ONE % U256::ZERO;
907    }
908
909    #[test]
910    fn rem_mixed() {
911        let x = U1024::from_be_hex(concat![
912            "3740C11DB8F260753BC6B97DD2B8746D3E2694412772AC6ABD975119EE0A6190",
913            "F27F6F0969BCA069D8D151031AF83EE2283CC2E3E4FADBBDB9EEDBF0B8F4C1FD",
914            "51912C0D329FDC37D49176DB0A1A2D17E5E6D4F9F6B217FE9412EAA2F881F702",
915            "7A831C1B06D31D3618D218D6E667DBD85BFC7B6B6B93422D52516989376AA29A",
916        ]);
917        let y = U128::from_u64(1234567890987654321);
918        let rem = x.rem_mixed(&y.to_nz().unwrap());
919
920        let y2: U1024 = U128::concat_mixed(&y, &U896::ZERO);
921        let rem_control = x.rem(&NonZero::new(y2).unwrap());
922
923        assert_eq!(rem.bits(), rem_control.bits());
924        assert_eq!(rem.as_words(), &rem_control.as_words()[0..U128::LIMBS]);
925        assert!(
926            rem_control.as_words()[U128::LIMBS..]
927                .iter()
928                .all(|w| *w == 0)
929        );
930    }
931
932    #[test]
933    fn rem_mixed_even() {
934        let x = U1024::from_be_hex(concat![
935            "3740C11DB8F260753BC6B97DD2B8746D3E2694412772AC6ABD975119EE0A6190",
936            "F27F6F0969BCA069D8D151031AF83EE2283CC2E3E4FADBBDB9EEDBF0B8F4C1FD",
937            "51912C0D329FDC37D49176DB0A1A2D17E5E6D4F9F6B217FE9412EAA2F881F702",
938            "7A831C1B06D31D3618D218D6E667DBD85BFC7B6B6B93422D52516989376AA29A",
939        ]);
940        let y = U512::from_u64(1234567890987654321);
941        let rem: U512 = x.rem_mixed(&y.to_nz().unwrap());
942
943        let y_wide = U512::concat_mixed(&y, &U512::ZERO);
944        let rem_control: U1024 = x.rem(&NonZero::new(y_wide).unwrap());
945
946        assert_eq!(rem.bits(), rem_control.bits());
947        assert_eq!(rem.as_words(), &rem_control.as_words()[0..U512::LIMBS]);
948        assert!(
949            rem_control.as_words()[U512::LIMBS..]
950                .iter()
951                .all(|w| *w == 0)
952        );
953    }
954
955    #[test]
956    fn rem_mixed_through_traits() {
957        struct A<T, U> {
958            t: T,
959            u: U,
960        }
961        impl<T, U> A<T, U>
962        where
963            T: RemMixed<U>,
964            U: Clone + Zero + One + CtAssign,
965        {
966            fn reduce_t_by_u(&self) -> U {
967                let rhs = &NonZero::new(self.u.clone()).unwrap();
968                self.t.rem_mixed(rhs)
969            }
970        }
971
972        let a = A {
973            t: U1024::from(1234567890u64),
974            u: U128::from(456u64),
975        };
976        assert_eq!(a.reduce_t_by_u(), U128::from(330u64));
977    }
978
979    #[test]
980    fn div_vartime_through_traits() {
981        struct A<T> {
982            x: T,
983            y: T,
984        }
985        impl<T> A<T>
986        where
987            T: DivVartime + Clone + Zero + One + CtAssign,
988        {
989            fn divide_x_by_y(&self) -> T {
990                let rhs = &NonZero::new(self.y.clone()).unwrap();
991                self.x.div_vartime(rhs)
992            }
993        }
994
995        let a = A {
996            x: U1024::from(1234567890u64),
997            y: U1024::from(456u64),
998        };
999        assert_eq!(a.divide_x_by_y(), U1024::from(2707385u64));
1000    }
1001}
crypto_bigint/uint/div.rs

crypto_bigint/uint/
div.rs
