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

crypto_bigint/uint/
div.rs
