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

num_modular/
reduced.rs
