num_modular/
reduced.rs

1use crate::{udouble, ModularInteger, ModularUnaryOps, Reducer};
2use core::ops::*;
3#[cfg(feature = "num-traits")]
4use num_traits::{Inv, Pow};
5
6/// An integer in a modulo ring
7#[must_use]
8#[derive(Debug, Clone, Copy)]
9pub struct ReducedInt<T, R: Reducer<T>> {
10    /// The reduced representation of the integer in a modulo ring.
11    a: T,
12
13    /// The reducer for the integer
14    r: R,
15}
16
17impl<T, R: Reducer<T>> ReducedInt<T, R> {
18    /// Convert n into the modulo ring ℤ/mℤ (i.e. `n % m`)
19    #[inline]
20    pub fn new(n: T, m: &T) -> Self {
21        let r = R::new(m);
22        let a = r.transform(n);
23        Self { a, r }
24    }
25
26    #[inline(always)]
27    fn check_modulus_eq(&self, rhs: &Self)
28    where
29        T: PartialEq,
30    {
31        // we don't directly compare m because m could be empty in case of Mersenne modular integer
32        debug_assert!(
33            self.r.modulus() == rhs.r.modulus(),
34            "The modulus of two operators should be the same!"
35        );
36    }
37
38    #[inline(always)]
39    pub fn repr(&self) -> &T {
40        &self.a
41    }
42
43    #[inline(always)]
44    pub fn inv(self) -> Option<Self> {
45        Some(Self {
46            a: self.r.inv(self.a)?,
47            r: self.r,
48        })
49    }
50
51    #[inline(always)]
52    pub fn pow(self, exp: &T) -> Self {
53        Self {
54            a: self.r.pow(self.a, exp),
55            r: self.r,
56        }
57    }
58}
59
60impl<T: PartialEq, R: Reducer<T>> PartialEq for ReducedInt<T, R> {
61    #[inline]
62    fn eq(&self, other: &Self) -> bool {
63        self.check_modulus_eq(other);
64        self.a == other.a
65    }
66}
67
68macro_rules! impl_binops {
69    ($method:ident, impl $op:ident) => {
70        impl<T: PartialEq, R: Reducer<T>> $op for ReducedInt<T, R> {
71            type Output = Self;
72            fn $method(self, rhs: Self) -> Self::Output {
73                self.check_modulus_eq(&rhs);
74                let Self { a, r } = self;
75                let a = r.$method(&a, &rhs.a);
76                Self { a, r }
77            }
78        }
79
80        impl<T: PartialEq + Clone, R: Reducer<T>> $op<&Self> for ReducedInt<T, R> {
81            type Output = Self;
82            #[inline]
83            fn $method(self, rhs: &Self) -> Self::Output {
84                self.check_modulus_eq(&rhs);
85                let Self { a, r } = self;
86                let a = r.$method(&a, &rhs.a);
87                Self { a, r }
88            }
89        }
90
91        impl<T: PartialEq + Clone, R: Reducer<T>> $op<ReducedInt<T, R>> for &ReducedInt<T, R> {
92            type Output = ReducedInt<T, R>;
93            #[inline]
94            fn $method(self, rhs: ReducedInt<T, R>) -> Self::Output {
95                self.check_modulus_eq(&rhs);
96                let ReducedInt { a, r } = rhs;
97                let a = r.$method(&self.a, &a);
98                ReducedInt { a, r }
99            }
100        }
101
102        impl<T: PartialEq + Clone, R: Reducer<T> + Clone> $op<&ReducedInt<T, R>>
103            for &ReducedInt<T, R>
104        {
105            type Output = ReducedInt<T, R>;
106            #[inline]
107            fn $method(self, rhs: &ReducedInt<T, R>) -> Self::Output {
108                self.check_modulus_eq(&rhs);
109                let a = self.r.$method(&self.a, &rhs.a);
110                ReducedInt {
111                    a,
112                    r: self.r.clone(),
113                }
114            }
115        }
116
117        impl<T, R: Reducer<T>> $op<T> for ReducedInt<T, R> {
118            type Output = Self;
119            #[inline]
120            fn $method(self, rhs: T) -> Self::Output {
121                let Self { a, r } = self;
122                let rhs = r.transform(rhs);
123                let a = r.$method(&a, &rhs);
124                Self { a, r }
125            }
126        }
127
128        impl<T: PartialEq + Clone, R: Reducer<T>> $op<&T> for ReducedInt<T, R> {
129            type Output = Self;
130            #[inline]
131            fn $method(self, rhs: &T) -> Self::Output {
132                let Self { a, r } = self;
133                let rhs = r.transform(rhs.clone());
134                let a = r.$method(&a, &rhs);
135                Self { a, r }
136            }
137        }
138
139        impl<T, R: Reducer<T> + Clone> $op<T> for &ReducedInt<T, R> {
140            type Output = ReducedInt<T, R>;
141            #[inline]
142            fn $method(self, rhs: T) -> Self::Output {
143                let rhs = self.r.transform(rhs);
144                let a = self.r.$method(&self.a, &rhs);
145                ReducedInt {
146                    a,
147                    r: self.r.clone(),
148                }
149            }
150        }
151
152        impl<T: PartialEq + Clone, R: Reducer<T> + Clone> $op<&T> for &ReducedInt<T, R> {
153            type Output = ReducedInt<T, R>;
154            #[inline]
155            fn $method(self, rhs: &T) -> Self::Output {
156                let rhs = self.r.transform(rhs.clone());
157                let a = self.r.$method(&self.a, &rhs);
158                ReducedInt {
159                    a,
160                    r: self.r.clone(),
161                }
162            }
163        }
164    };
165}
166impl_binops!(add, impl Add);
167impl_binops!(sub, impl Sub);
168impl_binops!(mul, impl Mul);
169
170macro_rules! impl_assign_ops {
171    ($method:ident, impl $op:ident, with $reducer_method:ident) => {
172        impl<T: PartialEq, R: Reducer<T>> $op for ReducedInt<T, R> {
173            #[inline]
174            fn $method(&mut self, rhs: Self) {
175                self.check_modulus_eq(&rhs);
176                let Self { a, r } = self;
177                r.$reducer_method(a, &rhs.a);
178            }
179        }
180
181        impl<T: PartialEq, R: Reducer<T>> $op<&Self> for ReducedInt<T, R> {
182            #[inline]
183            fn $method(&mut self, rhs: &Self) {
184                self.check_modulus_eq(rhs);
185                let Self { a, r } = self;
186                r.$reducer_method(a, &rhs.a);
187            }
188        }
189
190        impl<T, R: Reducer<T>> $op<T> for ReducedInt<T, R> {
191            #[inline]
192            fn $method(&mut self, rhs: T) {
193                let Self { a, r } = self;
194                let rhs = r.transform(rhs);
195                r.$reducer_method(a, &rhs);
196            }
197        }
198
199        impl<T: PartialEq + Clone, R: Reducer<T>> $op<&T> for ReducedInt<T, R> {
200            #[inline]
201            fn $method(&mut self, rhs: &T) {
202                let Self { a, r } = self;
203                let rhs = r.transform(rhs.clone());
204                r.$reducer_method(a, &rhs);
205            }
206        }
207    };
208}
209impl_assign_ops!(add_assign, impl AddAssign, with add_in_place);
210impl_assign_ops!(sub_assign, impl SubAssign, with sub_in_place);
211impl_assign_ops!(mul_assign, impl MulAssign, with mul_in_place);
212
213impl<T: PartialEq, R: Reducer<T>> Neg for ReducedInt<T, R> {
214    type Output = Self;
215    #[inline]
216    fn neg(self) -> Self::Output {
217        let Self { a, r } = self;
218        let a = r.neg(a);
219        Self { a, r }
220    }
221}
222impl<T: PartialEq + Clone, R: Reducer<T> + Clone> Neg for &ReducedInt<T, R> {
223    type Output = ReducedInt<T, R>;
224    #[inline]
225    fn neg(self) -> Self::Output {
226        let a = self.r.neg(self.a.clone());
227        ReducedInt {
228            a,
229            r: self.r.clone(),
230        }
231    }
232}
233
234const INV_ERR_MSG: &str = "the modular inverse doesn't exist!";
235
236#[cfg(feature = "num-traits")]
237impl<T: PartialEq, R: Reducer<T>> Inv for ReducedInt<T, R> {
238    type Output = Self;
239    #[inline]
240    fn inv(self) -> Self::Output {
241        self.inv().expect(INV_ERR_MSG)
242    }
243}
244#[cfg(feature = "num-traits")]
245impl<T: PartialEq + Clone, R: Reducer<T> + Clone> Inv for &ReducedInt<T, R> {
246    type Output = ReducedInt<T, R>;
247    #[inline]
248    fn inv(self) -> Self::Output {
249        self.clone().inv().expect(INV_ERR_MSG)
250    }
251}
252
253impl<T: PartialEq, R: Reducer<T>> Div for ReducedInt<T, R> {
254    type Output = Self;
255    #[inline]
256    fn div(self, rhs: Self) -> Self::Output {
257        self.check_modulus_eq(&rhs);
258        let ReducedInt { a, r } = rhs;
259        let a = r.mul(&self.a, &r.inv(a).expect(INV_ERR_MSG));
260        ReducedInt { a, r }
261    }
262}
263impl<T: PartialEq + Clone, R: Reducer<T>> Div<&ReducedInt<T, R>> for ReducedInt<T, R> {
264    type Output = Self;
265    #[inline]
266    fn div(self, rhs: &Self) -> Self::Output {
267        self.check_modulus_eq(rhs);
268        let Self { a, r } = self;
269        let a = r.mul(&a, &r.inv(rhs.a.clone()).expect(INV_ERR_MSG));
270        ReducedInt { a, r }
271    }
272}
273impl<T: PartialEq + Clone, R: Reducer<T>> Div<ReducedInt<T, R>> for &ReducedInt<T, R> {
274    type Output = ReducedInt<T, R>;
275    #[inline]
276    fn div(self, rhs: ReducedInt<T, R>) -> Self::Output {
277        self.check_modulus_eq(&rhs);
278        let ReducedInt { a, r } = rhs;
279        let a = r.mul(&self.a, &r.inv(a).expect(INV_ERR_MSG));
280        ReducedInt { a, r }
281    }
282}
283impl<T: PartialEq + Clone, R: Reducer<T> + Clone> Div<&ReducedInt<T, R>> for &ReducedInt<T, R> {
284    type Output = ReducedInt<T, R>;
285    #[inline]
286    fn div(self, rhs: &ReducedInt<T, R>) -> Self::Output {
287        self.check_modulus_eq(rhs);
288        let a = self
289            .r
290            .mul(&self.a, &self.r.inv(rhs.a.clone()).expect(INV_ERR_MSG));
291        ReducedInt {
292            a,
293            r: self.r.clone(),
294        }
295    }
296}
297
298#[cfg(feature = "num-traits")]
299impl<T: PartialEq, R: Reducer<T>> Pow<T> for ReducedInt<T, R> {
300    type Output = Self;
301    #[inline]
302    fn pow(self, rhs: T) -> Self::Output {
303        ReducedInt::pow(self, &rhs)
304    }
305}
306#[cfg(feature = "num-traits")]
307impl<T: PartialEq + Clone, R: Reducer<T> + Clone> Pow<T> for &ReducedInt<T, R> {
308    type Output = ReducedInt<T, R>;
309    #[inline]
310    fn pow(self, rhs: T) -> Self::Output {
311        let a = self.r.pow(self.a.clone(), &rhs);
312        ReducedInt {
313            a,
314            r: self.r.clone(),
315        }
316    }
317}
318
319impl<T: PartialEq + Clone, R: Reducer<T> + Clone> ModularInteger for ReducedInt<T, R> {
320    type Base = T;
321
322    #[inline]
323    fn modulus(&self) -> T {
324        self.r.modulus()
325    }
326
327    #[inline(always)]
328    fn residue(&self) -> T {
329        debug_assert!(self.r.check(&self.a));
330        self.r.residue(self.a.clone())
331    }
332
333    #[inline(always)]
334    fn is_zero(&self) -> bool {
335        self.r.is_zero(&self.a)
336    }
337
338    #[inline]
339    fn convert(&self, n: T) -> Self {
340        Self {
341            a: self.r.transform(n),
342            r: self.r.clone(),
343        }
344    }
345
346    #[inline]
347    fn double(self) -> Self {
348        let Self { a, r } = self;
349        let a = r.dbl(a);
350        Self { a, r }
351    }
352
353    #[inline]
354    fn square(self) -> Self {
355        let Self { a, r } = self;
356        let a = r.sqr(a);
357        Self { a, r }
358    }
359}
360
361// An vanilla reducer is also provided here
362/// A plain reducer that just use normal [Rem] operators. It will keep the integer
363/// in range [0, modulus) after each operation.
364#[must_use]
365#[derive(Debug, Clone, Copy)]
366pub struct Vanilla<T>(T);
367
368macro_rules! impl_uprim_vanilla_core_const {
369    ($($T:ty)*) => {$(
370        // These methods are for internal use only, wait for the introduction of const Trait in Rust
371        impl Vanilla<$T> {
372            #[inline]
373            pub(crate) const fn add(m: &$T, lhs: $T, rhs: $T) -> $T {
374                let (sum, overflow) = lhs.overflowing_add(rhs);
375                if overflow || sum >= *m {
376                    let (sum2, overflow2) = sum.overflowing_sub(*m);
377                    debug_assert!(overflow == overflow2);
378                    sum2
379                } else {
380                    sum
381                }
382            }
383
384            #[inline]
385            pub(crate) const fn dbl(m: &$T, target: $T) -> $T {
386                Self::add(m, target, target)
387            }
388
389            #[inline]
390            pub(crate) const fn sub(m: &$T, lhs: $T, rhs: $T) -> $T {
391                // this implementation should be equivalent to using overflowing_add and _sub after optimization.
392                if lhs >= rhs {
393                    lhs - rhs
394                } else {
395                    *m - (rhs - lhs)
396                }
397            }
398
399            #[inline]
400            pub(crate) const fn neg(m: &$T, target: $T) -> $T {
401                match target {
402                    0 => 0,
403                    x => *m - x
404                }
405            }
406        }
407    )*};
408}
409impl_uprim_vanilla_core_const!(u8 u16 u32 u64 u128 usize);
410
411/// Generate the seven trivial `Reducer` trait methods that are identical
412/// across all fixed reducer types (check, modulus, is_zero, add, sub, dbl, neg).
413macro_rules! impl_reduced_ops {
414    ($T:ty) => {
415        #[inline]
416        fn check(&self, target: &$T) -> bool {
417            *target < Self::MODULUS
418        }
419        #[inline]
420        fn modulus(&self) -> $T {
421            Self::MODULUS
422        }
423        #[inline]
424        fn is_zero(&self, target: &$T) -> bool {
425            target == &0
426        }
427
428        #[inline]
429        fn add(&self, lhs: &$T, rhs: &$T) -> $T {
430            $crate::Vanilla::<$T>::add(&Self::MODULUS, *lhs, *rhs)
431        }
432        #[inline]
433        fn sub(&self, lhs: &$T, rhs: &$T) -> $T {
434            $crate::Vanilla::<$T>::sub(&Self::MODULUS, *lhs, *rhs)
435        }
436        #[inline]
437        fn dbl(&self, target: $T) -> $T {
438            $crate::Vanilla::<$T>::dbl(&Self::MODULUS, target)
439        }
440        #[inline]
441        fn neg(&self, target: $T) -> $T {
442            $crate::Vanilla::<$T>::neg(&Self::MODULUS, target)
443        }
444    };
445}
446
447pub(crate) use impl_reduced_ops;
448
449macro_rules! impl_reduced_binary_pow {
450    ($T:ty) => {
451        fn pow(&self, base: $T, exp: &$T) -> $T {
452            match *exp {
453                1 => base,
454                2 => self.sqr(base),
455                e => {
456                    let mut multi = base;
457                    let mut exp = e;
458                    let mut result = self.transform(1);
459                    while exp > 0 {
460                        if exp & 1 != 0 {
461                            result = self.mul(&result, &multi);
462                        }
463                        multi = self.sqr(multi);
464                        exp >>= 1;
465                    }
466                    result
467                }
468            }
469        }
470    };
471}
472
473pub(crate) use impl_reduced_binary_pow;
474
475macro_rules! impl_uprim_vanilla_core {
476    ($single:ty) => {
477        #[inline(always)]
478        fn new(m: &$single) -> Self {
479            assert!(m > &0);
480            Self(*m)
481        }
482        #[inline(always)]
483        fn transform(&self, target: $single) -> $single {
484            target % self.0
485        }
486        #[inline(always)]
487        fn check(&self, target: &$single) -> bool {
488            *target < self.0
489        }
490        #[inline(always)]
491        fn residue(&self, target: $single) -> $single {
492            target
493        }
494        #[inline(always)]
495        fn modulus(&self) -> $single {
496            self.0
497        }
498        #[inline(always)]
499        fn is_zero(&self, target: &$single) -> bool {
500            *target == 0
501        }
502
503        #[inline(always)]
504        fn add(&self, lhs: &$single, rhs: &$single) -> $single {
505            Vanilla::<$single>::add(&self.0, *lhs, *rhs)
506        }
507
508        #[inline(always)]
509        fn dbl(&self, target: $single) -> $single {
510            Vanilla::<$single>::dbl(&self.0, target)
511        }
512
513        #[inline(always)]
514        fn sub(&self, lhs: &$single, rhs: &$single) -> $single {
515            Vanilla::<$single>::sub(&self.0, *lhs, *rhs)
516        }
517
518        #[inline(always)]
519        fn neg(&self, target: $single) -> $single {
520            Vanilla::<$single>::neg(&self.0, target)
521        }
522
523        #[inline(always)]
524        fn inv(&self, target: $single) -> Option<$single> {
525            target.invm(&self.0)
526        }
527
528        impl_reduced_binary_pow!($single);
529    };
530}
531
532macro_rules! impl_uprim_vanilla {
533    ($t:ident, $ns:ident) => {
534        mod $ns {
535            use super::*;
536            use crate::word::$t::*;
537
538            impl Reducer<$t> for Vanilla<$t> {
539                impl_uprim_vanilla_core!($t);
540
541                #[inline]
542                fn mul(&self, lhs: &$t, rhs: &$t) -> $t {
543                    (wmul(*lhs, *rhs) % extend(self.0)) as $t
544                }
545
546                #[inline]
547                fn sqr(&self, target: $t) -> $t {
548                    (wsqr(target) % extend(self.0)) as $t
549                }
550            }
551        }
552    };
553}
554
555impl_uprim_vanilla!(u8, u8_impl);
556impl_uprim_vanilla!(u16, u16_impl);
557impl_uprim_vanilla!(u32, u32_impl);
558impl_uprim_vanilla!(u64, u64_impl);
559impl_uprim_vanilla!(usize, usize_impl);
560
561impl Reducer<u128> for Vanilla<u128> {
562    impl_uprim_vanilla_core!(u128);
563
564    #[inline]
565    fn mul(&self, lhs: &u128, rhs: &u128) -> u128 {
566        udouble::widening_mul(*lhs, *rhs) % self.0
567    }
568
569    #[inline]
570    fn sqr(&self, target: u128) -> u128 {
571        udouble::widening_square(target) % self.0
572    }
573}
574
575#[cfg(all(feature = "num-bigint", feature = "num-traits"))]
576mod bigint_impl {
577    use super::*;
578    use crate::ModularCoreOps;
579    use crate::ModularPow;
580    use num_bigint::BigUint;
581    use num_traits::Zero;
582
583    impl Reducer<BigUint> for Vanilla<BigUint> {
584        #[inline]
585        fn new(m: &BigUint) -> Self {
586            assert!(!m.is_zero());
587            Self(m.clone())
588        }
589
590        #[inline]
591        fn transform(&self, target: BigUint) -> BigUint {
592            target % &self.0
593        }
594
595        #[inline]
596        fn check(&self, target: &BigUint) -> bool {
597            target < &self.0
598        }
599
600        #[inline]
601        fn modulus(&self) -> BigUint {
602            self.0.clone()
603        }
604
605        #[inline]
606        fn residue(&self, target: BigUint) -> BigUint {
607            target
608        }
609
610        #[inline]
611        fn is_zero(&self, target: &BigUint) -> bool {
612            target.is_zero()
613        }
614
615        #[inline]
616        fn add(&self, lhs: &BigUint, rhs: &BigUint) -> BigUint {
617            lhs.addm(rhs, &self.0)
618        }
619
620        #[inline]
621        fn dbl(&self, target: BigUint) -> BigUint {
622            target.dblm(&self.0)
623        }
624
625        #[inline]
626        fn sub(&self, lhs: &BigUint, rhs: &BigUint) -> BigUint {
627            lhs.subm(rhs, &self.0)
628        }
629
630        #[inline]
631        fn neg(&self, target: BigUint) -> BigUint {
632            target.negm(&self.0)
633        }
634
635        #[inline]
636        fn mul(&self, lhs: &BigUint, rhs: &BigUint) -> BigUint {
637            lhs.mulm(rhs, &self.0)
638        }
639
640        #[inline]
641        fn inv(&self, target: BigUint) -> Option<BigUint> {
642            target.invm(&self.0)
643        }
644
645        #[inline]
646        fn sqr(&self, target: BigUint) -> BigUint {
647            target.sqm(&self.0)
648        }
649
650        #[inline]
651        fn pow(&self, base: BigUint, exp: &BigUint) -> BigUint {
652            base.powm(exp, &self.0)
653        }
654    }
655}
656
657/// An integer in modulo ring based on conventional [Rem] operations
658pub type VanillaInt<T> = ReducedInt<T, Vanilla<T>>;
659
660#[cfg(test)]
661pub(crate) mod tests {
662    use super::*;
663    use crate::{ModularCoreOps, ModularPow, ModularUnaryOps};
664    use core::marker::PhantomData;
665    use rand::random;
666
667    pub(crate) struct ReducedTester<T>(PhantomData<T>);
668
669    macro_rules! impl_reduced_test_for {
670        ($($T:ty)*) => {$(
671            impl ReducedTester<$T> {
672                /// Range of modulus:
673                /// - random_mode = 0: [1, $T::MAX]
674                /// - random_mode = 1: [1, $T::MAX] and odd
675                /// - random_mode = 2: [$T::MAX >> $T::BITS/2, $T::MAX]
676                pub fn test_against_modops<R: Reducer<$T> + Copy>(random_mode: i32) {
677                    let m = match random_mode {
678                        0 => random::<$T>().saturating_add(1),
679                        1 => random::<$T>().saturating_add(1) | 1,
680                        2 => random::<$T>().saturating_add(1 << (<$T>::BITS / 2)),
681                        _ => unreachable!()
682                    };
683
684                    let (a, b) = (random::<$T>(), random::<$T>());
685                    let am = ReducedInt::<$T, R>::new(a, &m);
686                    let bm = ReducedInt::<$T, R>::new(b, &m);
687                    assert_eq!((am + bm).residue(), a.addm(b, &m), "incorrect add");
688                    assert_eq!((am - bm).residue(), a.subm(b, &m), "incorrect sub");
689                    assert_eq!((am * bm).residue(), a.mulm(b, &m), "incorrect mul");
690                    assert_eq!(am.neg().residue(), a.negm(&m), "incorrect neg");
691                    assert_eq!(am.double().residue(), a.dblm(&m), "incorrect dbl");
692                    assert_eq!(am.square().residue(), a.sqm(&m), "incorrect sqr");
693
694                    let e = random::<u8>() as $T;
695                    assert_eq!(am.pow(&e).residue(), a.powm(e, &m), "incorrect pow");
696                    if let Some(v) = a.invm(&m) {
697                        assert_eq!(am.inv().unwrap().residue(), v, "incorrect inv");
698                    }
699
700                    // Test new binary operator variants
701                    // ReducedInt op &T
702                    assert_eq!((am + &b).residue(), a.addm(b, &m), "incorrect add<&T>");
703                    assert_eq!((am - &b).residue(), a.subm(b, &m), "incorrect sub<&T>");
704                    assert_eq!((am * &b).residue(), a.mulm(b, &m), "incorrect mul<&T>");
705                    // &ReducedInt op T
706                    assert_eq!((&am + a).residue(), a.addm(a, &m), "incorrect &add<T>");
707                    assert_eq!((&am - a).residue(), a.subm(a, &m), "incorrect &sub<T>");
708                    assert_eq!((&am * a).residue(), a.mulm(a, &m), "incorrect &mul<T>");
709                    // &ReducedInt op &T
710                    assert_eq!((&am + &b).residue(), a.addm(b, &m), "incorrect &add<&T>");
711                    assert_eq!((&am - &b).residue(), a.subm(b, &m), "incorrect &sub<&T>");
712                    assert_eq!((&am * &b).residue(), a.mulm(b, &m), "incorrect &mul<&T>");
713
714                    // Assign ops
715                    let mut tmp;
716                    tmp = am;
717                    tmp += bm;
718                    assert_eq!(tmp.residue(), a.addm(b, &m), "incorrect add_assign<Self>");
719                    tmp = am;
720                    tmp += &bm;
721                    assert_eq!(tmp.residue(), a.addm(b, &m), "incorrect add_assign<&Self>");
722                    tmp = am;
723                    tmp += b;
724                    assert_eq!(tmp.residue(), a.addm(b, &m), "incorrect add_assign<T>");
725                    tmp = am;
726                    tmp += &b;
727                    assert_eq!(tmp.residue(), a.addm(b, &m), "incorrect add_assign<&T>");
728
729                    tmp = am;
730                    tmp -= bm;
731                    assert_eq!(tmp.residue(), a.subm(b, &m), "incorrect sub_assign<Self>");
732                    tmp = am;
733                    tmp -= &bm;
734                    assert_eq!(tmp.residue(), a.subm(b, &m), "incorrect sub_assign<&Self>");
735                    tmp = am;
736                    tmp -= b;
737                    assert_eq!(tmp.residue(), a.subm(b, &m), "incorrect sub_assign<T>");
738                    tmp = am;
739                    tmp -= &b;
740                    assert_eq!(tmp.residue(), a.subm(b, &m), "incorrect sub_assign<&T>");
741
742                    tmp = am;
743                    tmp *= bm;
744                    assert_eq!(tmp.residue(), a.mulm(b, &m), "incorrect mul_assign<Self>");
745                    tmp = am;
746                    tmp *= &bm;
747                    assert_eq!(tmp.residue(), a.mulm(b, &m), "incorrect mul_assign<&Self>");
748                    tmp = am;
749                    tmp *= b;
750                    assert_eq!(tmp.residue(), a.mulm(b, &m), "incorrect mul_assign<T>");
751                    tmp = am;
752                    tmp *= &b;
753                    assert_eq!(tmp.residue(), a.mulm(b, &m), "incorrect mul_assign<&T>");
754                }
755            }
756        )*};
757    }
758    impl_reduced_test_for!(u8 u16 u32 u64 u128 usize);
759
760    #[test]
761    fn test_against_modops() {
762        for _ in 0..10 {
763            ReducedTester::<u8>::test_against_modops::<Vanilla<u8>>(0);
764            ReducedTester::<u16>::test_against_modops::<Vanilla<u16>>(0);
765            ReducedTester::<u32>::test_against_modops::<Vanilla<u32>>(0);
766            ReducedTester::<u64>::test_against_modops::<Vanilla<u64>>(0);
767            ReducedTester::<u128>::test_against_modops::<Vanilla<u128>>(0);
768            ReducedTester::<usize>::test_against_modops::<Vanilla<usize>>(0);
769        }
770    }
771
772    #[cfg(all(feature = "num-bigint", feature = "num-traits"))]
773    #[test]
774    fn test_binops_no_copy_compiles() {
775        use num_bigint::BigUint;
776
777        let mut m = VanillaInt::<BigUint>::new(0u8.into(), &10u8.into());
778        let v: BigUint = 0u8.into();
779
780        _ = m.clone() + m.clone();
781        _ = m.clone() + &m;
782        _ = &m + m.clone();
783        _ = &m + &m;
784
785        _ = m.clone() + v.clone();
786        _ = m.clone() + &v;
787        _ = &m + v.clone();
788        _ = &m + &v;
789
790        m += m.clone();
791        m += &m.clone();
792        m += v.clone();
793        m += &v;
794
795        m -= m.clone();
796        m -= &m.clone();
797        m -= v.clone();
798        m -= &v;
799
800        m *= m.clone();
801        m *= &m.clone();
802        m *= v.clone();
803        m *= &v;
804
805        assert_eq!(m.residue(), 0u8.into());
806    }
807}
num_modular/reduced.rs

num_modular/
reduced.rs
