crypto_bigint/int/
div_uint.rs

1//! Operations related to dividing an [`Int`] by a [`Uint`].
2use core::ops::{Div, DivAssign, Rem, RemAssign};
3
4use crate::{ConstChoice, Int, NonZero, Uint, Wrapping};
5
6/// Checked division operations.
7impl<const LIMBS: usize> Int<LIMBS> {
8    #[inline]
9    /// Base div_rem operation on dividing an [`Int`] by a [`Uint`].
10    /// Computes the quotient and remainder of `self / rhs`.
11    /// Furthermore, returns the sign of `self`.
12    const fn div_rem_base_uint(
13        &self,
14        rhs: &NonZero<Uint<LIMBS>>,
15    ) -> (Uint<{ LIMBS }>, Uint<{ LIMBS }>, ConstChoice) {
16        let (lhs_mag, lhs_sgn) = self.abs_sign();
17        let (quotient, remainder) = lhs_mag.div_rem(rhs);
18        (quotient, remainder, lhs_sgn)
19    }
20
21    /// Compute the quotient and remainder of `self / rhs`.
22    ///
23    /// Example:
24    /// ```
25    /// use crypto_bigint::{I128, NonZero, U128};
26    ///
27    /// let (quotient, remainder) = I128::from(8).div_rem_uint(&U128::from(3u32).to_nz().unwrap());
28    /// assert_eq!(quotient, I128::from(2));
29    /// assert_eq!(remainder, I128::from(2));
30    ///
31    /// let (quotient, remainder) = I128::from(-8).div_rem_uint(&U128::from(3u32).to_nz().unwrap());
32    /// assert_eq!(quotient, I128::from(-2));
33    /// assert_eq!(remainder, I128::from(-2));
34    /// ```
35    pub const fn div_rem_uint(&self, rhs: &NonZero<Uint<LIMBS>>) -> (Self, Self) {
36        let (quotient, remainder, lhs_sgn) = self.div_rem_base_uint(rhs);
37        (
38            Self(quotient).wrapping_neg_if(lhs_sgn),
39            Self(remainder).wrapping_neg_if(lhs_sgn),
40        )
41    }
42
43    /// Perform division.
44    /// Note: this operation rounds towards zero, truncating any fractional part of the exact result.
45    pub const fn div_uint(&self, rhs: &NonZero<Uint<LIMBS>>) -> Self {
46        self.div_rem_uint(rhs).0
47    }
48
49    /// Compute the remainder.
50    /// The remainder will have the same sign as `self` (or be zero).
51    pub const fn rem_uint(&self, rhs: &NonZero<Uint<LIMBS>>) -> Self {
52        self.div_rem_uint(rhs).1
53    }
54}
55
56/// Vartime checked division operations.
57impl<const LIMBS: usize> Int<LIMBS> {
58    #[inline]
59    /// Variable time equivalent of [Self::div_rem_base_uint`].
60    ///
61    /// This is variable only with respect to `rhs`.
62    ///
63    /// When used with a fixed `rhs`, this function is constant-time with respect
64    /// to `self`.
65    const fn div_rem_base_uint_vartime<const RHS_LIMBS: usize>(
66        &self,
67        rhs: &NonZero<Uint<RHS_LIMBS>>,
68    ) -> (Uint<LIMBS>, Uint<RHS_LIMBS>, ConstChoice) {
69        let (lhs_mag, lhs_sgn) = self.abs_sign();
70        let (quotient, remainder) = lhs_mag.div_rem_vartime(rhs);
71        (quotient, remainder, lhs_sgn)
72    }
73
74    /// Variable time equivalent of [Self::div_rem_uint`].
75    ///
76    /// This is variable only with respect to `rhs`.
77    ///
78    /// When used with a fixed `rhs`, this function is constant-time with respect
79    /// to `self`.
80    pub const fn div_rem_uint_vartime<const RHS_LIMBS: usize>(
81        &self,
82        rhs: &NonZero<Uint<RHS_LIMBS>>,
83    ) -> (Self, Int<RHS_LIMBS>) {
84        let (quotient, remainder, lhs_sgn) = self.div_rem_base_uint_vartime(rhs);
85        (
86            Self(quotient).wrapping_neg_if(lhs_sgn),
87            remainder.as_int().wrapping_neg_if(lhs_sgn),
88        )
89    }
90
91    /// Variable time equivalent of [Self::div_uint`].
92    ///
93    /// This is variable only with respect to `rhs`.
94    ///
95    /// When used with a fixed `rhs`, this function is constant-time with respect
96    /// to `self`.
97    pub const fn div_uint_vartime<const RHS_LIMBS: usize>(
98        &self,
99        rhs: &NonZero<Uint<RHS_LIMBS>>,
100    ) -> Self {
101        self.div_rem_uint_vartime(rhs).0
102    }
103
104    /// Variable time equivalent of [Self::rem_uint`].
105    ///
106    /// This is variable only with respect to `rhs`.
107    ///
108    /// When used with a fixed `rhs`, this function is constant-time with respect
109    /// to `self`.
110    pub const fn rem_uint_vartime<const RHS_LIMBS: usize>(
111        &self,
112        rhs: &NonZero<Uint<RHS_LIMBS>>,
113    ) -> Int<RHS_LIMBS> {
114        self.div_rem_uint_vartime(rhs).1
115    }
116}
117
118/// Checked div-floor operations
119impl<const LIMBS: usize> Int<LIMBS> {
120    /// Perform floored division and mod:
121    /// given `n` and `d`, computes `q` and `r` s.t. `n = qd + r` and `q = ⌊n/d⌋`.
122    /// Note: this operation rounds **down**, not towards zero.
123    ///
124    /// Example:
125    /// ```
126    /// use crypto_bigint::{I128, U128};
127    ///
128    /// let three = U128::from(3u32).to_nz().unwrap();
129    /// assert_eq!(
130    ///     I128::from(8).div_rem_floor_uint(&three),
131    ///     (I128::from(2), U128::from(2u32))
132    /// );
133    /// assert_eq!(
134    ///     I128::from(-8).div_rem_floor_uint(&three),
135    ///     (I128::from(-3), U128::ONE)
136    /// );
137    /// ```
138    pub fn div_rem_floor_uint(&self, rhs: &NonZero<Uint<LIMBS>>) -> (Self, Uint<LIMBS>) {
139        let (quotient, remainder, lhs_sgn) = self.div_rem_base_uint(rhs);
140
141        // Increase the quotient by one when self is negative and there is a non-zero remainder.
142        let modify = remainder.is_nonzero().and(lhs_sgn);
143        let quotient = Uint::select(&quotient, &quotient.wrapping_add(&Uint::ONE), modify);
144
145        // Invert the remainder when self is negative and there is a non-zero remainder.
146        let remainder = Uint::select(&remainder, &rhs.wrapping_sub(&remainder), modify);
147
148        // Negate if applicable
149        let quotient = Self(quotient).wrapping_neg_if(lhs_sgn);
150
151        (quotient, remainder)
152    }
153
154    /// Perform checked division.
155    /// Note: this operation rounds down.
156    ///
157    /// Example:
158    /// ```
159    /// use crypto_bigint::{I128, U128};
160    /// assert_eq!(
161    ///     I128::from(8).div_floor_uint(&U128::from(3u32).to_nz().unwrap()),
162    ///     I128::from(2)
163    /// );
164    /// assert_eq!(
165    ///     I128::from(-8).div_floor_uint(&U128::from(3u32).to_nz().unwrap()),
166    ///     I128::from(-3)
167    /// );
168    /// ```
169    pub fn div_floor_uint(&self, rhs: &NonZero<Uint<LIMBS>>) -> Self {
170        let (q, _) = self.div_rem_floor_uint(rhs);
171        q
172    }
173
174    /// Compute `self % rhs` and return the result contained in the interval `[0, rhs)`.
175    ///
176    /// Example:
177    /// ```
178    /// use crypto_bigint::{I128, U128};
179    /// assert_eq!(
180    ///     I128::from(8).normalized_rem(&U128::from(3u32).to_nz().unwrap()),
181    ///     U128::from(2u32)
182    /// );
183    /// assert_eq!(
184    ///     I128::from(-8).normalized_rem(&U128::from(3u32).to_nz().unwrap()),
185    ///     U128::ONE
186    /// );
187    /// ```
188    pub fn normalized_rem(&self, rhs: &NonZero<Uint<LIMBS>>) -> Uint<LIMBS> {
189        let (_, r) = self.div_rem_floor_uint(rhs);
190        r
191    }
192}
193
194/// Vartime checked div-floor operations
195impl<const LIMBS: usize> Int<LIMBS> {
196    /// Variable time equivalent of [Self::div_rem_floor_uint`].
197    ///
198    /// This is variable only with respect to `rhs`.
199    ///
200    /// When used with a fixed `rhs`, this function is constant-time with respect
201    /// to `self`.
202    pub fn div_rem_floor_uint_vartime<const RHS_LIMBS: usize>(
203        &self,
204        rhs: &NonZero<Uint<RHS_LIMBS>>,
205    ) -> (Self, Uint<RHS_LIMBS>) {
206        let (quotient, remainder, lhs_sgn) = self.div_rem_base_uint_vartime(rhs);
207
208        // Increase the quotient by one when self is negative and there is a non-zero remainder.
209        let modify = remainder.is_nonzero().and(lhs_sgn);
210        let quotient = Uint::select(&quotient, &quotient.wrapping_add(&Uint::ONE), modify);
211
212        // Invert the remainder when self is negative and there is a non-zero remainder.
213        let remainder = Uint::select(&remainder, &rhs.wrapping_sub(&remainder), modify);
214
215        // Negate if applicable
216        let quotient = Self(quotient).wrapping_neg_if(lhs_sgn);
217
218        (quotient, remainder)
219    }
220
221    /// Variable time equivalent of [Self::div_floor_uint`].
222    ///
223    /// This is variable only with respect to `rhs`.
224    ///
225    /// When used with a fixed `rhs`, this function is constant-time with respect
226    /// to `self`.
227    pub fn div_floor_uint_vartime<const RHS_LIMBS: usize>(
228        &self,
229        rhs: &NonZero<Uint<RHS_LIMBS>>,
230    ) -> Self {
231        let (q, _) = self.div_rem_floor_uint_vartime(rhs);
232        q
233    }
234
235    /// Variable time equivalent of [Self::normalized_rem`].
236    ///
237    /// This is variable only with respect to `rhs`.
238    ///
239    /// When used with a fixed `rhs`, this function is constant-time with respect
240    /// to `self`.
241    pub fn normalized_rem_vartime<const RHS_LIMBS: usize>(
242        &self,
243        rhs: &NonZero<Uint<RHS_LIMBS>>,
244    ) -> Uint<RHS_LIMBS> {
245        let (_, r) = self.div_rem_floor_uint_vartime(rhs);
246        r
247    }
248}
249
250impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Int<LIMBS> {
251    type Output = Int<LIMBS>;
252
253    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
254        *self / *rhs
255    }
256}
257
258impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Int<LIMBS> {
259    type Output = Int<LIMBS>;
260
261    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
262        self / *rhs
263    }
264}
265
266impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Int<LIMBS> {
267    type Output = Int<LIMBS>;
268
269    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
270        *self / rhs
271    }
272}
273
274impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Int<LIMBS> {
275    type Output = Int<LIMBS>;
276
277    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
278        self.div_uint(&rhs)
279    }
280}
281
282impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Int<LIMBS> {
283    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
284        *self /= *rhs
285    }
286}
287
288impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Int<LIMBS> {
289    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
290        *self = *self / rhs;
291    }
292}
293
294impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
295    type Output = Wrapping<Int<LIMBS>>;
296
297    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
298        Wrapping(self.0 / rhs)
299    }
300}
301
302impl<const LIMBS: usize> Div<NonZero<Uint<LIMBS>>> for &Wrapping<Int<LIMBS>> {
303    type Output = Wrapping<Int<LIMBS>>;
304
305    fn div(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
306        *self / rhs
307    }
308}
309
310impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for &Wrapping<Int<LIMBS>> {
311    type Output = Wrapping<Int<LIMBS>>;
312
313    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
314        *self / *rhs
315    }
316}
317
318impl<const LIMBS: usize> Div<&NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
319    type Output = Wrapping<Int<LIMBS>>;
320
321    fn div(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
322        self / *rhs
323    }
324}
325
326impl<const LIMBS: usize> DivAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
327    fn div_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
328        *self = Wrapping(self.0 / rhs);
329    }
330}
331
332impl<const LIMBS: usize> DivAssign<NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
333    fn div_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
334        *self /= &rhs;
335    }
336}
337
338impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Int<LIMBS> {
339    type Output = Int<LIMBS>;
340
341    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
342        *self % *rhs
343    }
344}
345
346impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Int<LIMBS> {
347    type Output = Int<LIMBS>;
348
349    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
350        self % *rhs
351    }
352}
353
354impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Int<LIMBS> {
355    type Output = Int<LIMBS>;
356
357    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
358        *self % rhs
359    }
360}
361
362impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Int<LIMBS> {
363    type Output = Int<LIMBS>;
364
365    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
366        Self::rem_uint(&self, &rhs)
367    }
368}
369
370impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Int<LIMBS> {
371    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
372        *self %= *rhs
373    }
374}
375
376impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Int<LIMBS> {
377    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
378        *self = *self % rhs;
379    }
380}
381
382impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
383    type Output = Wrapping<Int<LIMBS>>;
384
385    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
386        Wrapping(self.0 % rhs)
387    }
388}
389
390impl<const LIMBS: usize> Rem<NonZero<Uint<LIMBS>>> for &Wrapping<Int<LIMBS>> {
391    type Output = Wrapping<Int<LIMBS>>;
392
393    fn rem(self, rhs: NonZero<Uint<LIMBS>>) -> Self::Output {
394        *self % rhs
395    }
396}
397
398impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for &Wrapping<Int<LIMBS>> {
399    type Output = Wrapping<Int<LIMBS>>;
400
401    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
402        *self % *rhs
403    }
404}
405
406impl<const LIMBS: usize> Rem<&NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
407    type Output = Wrapping<Int<LIMBS>>;
408
409    fn rem(self, rhs: &NonZero<Uint<LIMBS>>) -> Self::Output {
410        self % *rhs
411    }
412}
413
414impl<const LIMBS: usize> RemAssign<NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
415    fn rem_assign(&mut self, rhs: NonZero<Uint<LIMBS>>) {
416        *self %= &rhs;
417    }
418}
419
420impl<const LIMBS: usize> RemAssign<&NonZero<Uint<LIMBS>>> for Wrapping<Int<LIMBS>> {
421    fn rem_assign(&mut self, rhs: &NonZero<Uint<LIMBS>>) {
422        *self = Wrapping(self.0 % rhs)
423    }
424}
425
426#[cfg(test)]
427mod tests {
428    #[cfg(feature = "rand_core")]
429    use {
430        crate::{Random, I1024, U1024, U512},
431        rand_core::OsRng,
432    };
433
434    use crate::{I128, U128};
435
436    #[test]
437    fn test_div_uint() {
438        // lhs = min
439        assert_eq!(I128::MIN / U128::ONE.to_nz().unwrap(), I128::MIN);
440        assert_eq!(I128::MIN / U128::MAX.to_nz().unwrap(), I128::ZERO);
441
442        // lhs = -1
443        assert_eq!(
444            I128::MINUS_ONE / U128::ONE.to_nz().unwrap(),
445            I128::MINUS_ONE
446        );
447        assert_eq!(I128::MINUS_ONE / U128::MAX.to_nz().unwrap(), I128::ZERO);
448
449        // lhs = 0
450        assert_eq!(I128::ZERO / U128::ONE.to_nz().unwrap(), I128::ZERO);
451        assert_eq!(I128::ZERO / U128::MAX.to_nz().unwrap(), I128::ZERO);
452
453        // lhs = 1
454        assert_eq!(I128::ONE / U128::ONE.to_nz().unwrap(), I128::ONE);
455        assert_eq!(I128::ONE / U128::MAX.to_nz().unwrap(), I128::ZERO);
456
457        // lhs = max
458        assert_eq!(I128::MAX / U128::ONE.to_nz().unwrap(), I128::MAX);
459        assert_eq!(I128::MAX / U128::MAX.to_nz().unwrap(), I128::ZERO);
460    }
461
462    #[cfg(feature = "rand_core")]
463    #[test]
464    fn test_div_ct_vs_vt() {
465        for _ in 0..50 {
466            let num = I1024::random(&mut OsRng);
467            let denom = U1024::from(&U512::random(&mut OsRng)).to_nz().unwrap();
468
469            assert_eq!(num.div_uint(&denom), num.div_uint_vartime(&denom))
470        }
471    }
472
473    #[test]
474    fn test_div_rem_floor_uint() {
475        // lhs = min
476        assert_eq!(
477            I128::MIN.div_rem_floor_uint(&U128::ONE.to_nz().unwrap()),
478            (I128::MIN, U128::ZERO)
479        );
480        assert_eq!(
481            I128::MIN.div_rem_floor_uint(&U128::MAX.to_nz().unwrap()),
482            (
483                I128::MINUS_ONE,
484                I128::MIN.as_uint().wrapping_sub(&U128::ONE)
485            )
486        );
487
488        // lhs = -1
489        assert_eq!(
490            I128::MINUS_ONE.div_rem_floor_uint(&U128::ONE.to_nz().unwrap()),
491            (I128::MINUS_ONE, U128::ZERO)
492        );
493        assert_eq!(
494            I128::MINUS_ONE.div_rem_floor_uint(&U128::MAX.to_nz().unwrap()),
495            (I128::MINUS_ONE, U128::MAX.wrapping_sub(&U128::ONE))
496        );
497
498        // lhs = 0
499        assert_eq!(
500            I128::ZERO.div_rem_floor_uint(&U128::ONE.to_nz().unwrap()),
501            (I128::ZERO, U128::ZERO)
502        );
503        assert_eq!(
504            I128::ZERO.div_rem_floor_uint(&U128::MAX.to_nz().unwrap()),
505            (I128::ZERO, U128::ZERO)
506        );
507
508        // lhs = 1
509        assert_eq!(
510            I128::ONE.div_rem_floor_uint(&U128::ONE.to_nz().unwrap()),
511            (I128::ONE, U128::ZERO)
512        );
513        assert_eq!(
514            I128::ONE.div_rem_floor_uint(&U128::MAX.to_nz().unwrap()),
515            (I128::ZERO, U128::ONE)
516        );
517
518        // lhs = max
519        assert_eq!(
520            I128::MAX.div_rem_floor_uint(&U128::ONE.to_nz().unwrap()),
521            (I128::MAX, U128::ZERO)
522        );
523        assert_eq!(
524            I128::MAX.div_rem_floor_uint(&U128::MAX.to_nz().unwrap()),
525            (I128::ZERO, *I128::MAX.as_uint())
526        );
527    }
528
529    #[cfg(feature = "rand_core")]
530    #[test]
531    fn test_div_floor_ct_vs_vt() {
532        for _ in 0..50 {
533            let num = I1024::random(&mut OsRng);
534            let denom = U1024::from(&U512::random(&mut OsRng)).to_nz().unwrap();
535
536            assert_eq!(
537                num.div_floor_uint(&denom),
538                num.div_floor_uint_vartime(&denom)
539            )
540        }
541    }
542}
crypto_bigint/int/div_uint.rs

crypto_bigint/int/
div_uint.rs
