num_prime/
mint.rs

1//! Wrapper of integer to makes it efficient in modular arithmetics but still have the same
2//! API of normal integers.
3
4use core::ops::*;
5use either::*;
6use num_integer::{Integer, Roots};
7use num_modular::{
8    ModularCoreOps, ModularInteger, ModularPow, ModularSymbols, ModularUnaryOps, Montgomery,
9    ReducedInt, Reducer,
10};
11use num_traits::{FromPrimitive, Num, One, Pow, ToPrimitive, Zero};
12
13use crate::{BitTest, ExactRoots};
14
15/// Integer with fast modular arithmetics support, based on [MontgomeryInt] under the hood
16///
17/// This struct only designed to be working with this crate. Most binary operators assume that
18/// the modulus of two operands (when in montgomery form) are the same, and most implicit conversions
19/// between conventional form and montgomery form will be forbidden
20#[derive(Debug, Clone, Copy)]
21pub struct Mint<T: Integer, R: Reducer<T>>(Either<T, ReducedInt<T, R>>);
22
23impl<T: Integer, R: Reducer<T>> From<T> for Mint<T, R> {
24    #[inline(always)]
25    fn from(v: T) -> Self {
26        Self(Left(v))
27    }
28}
29impl<T: Integer, R: Reducer<T>> From<ReducedInt<T, R>> for Mint<T, R> {
30    #[inline(always)]
31    fn from(v: ReducedInt<T, R>) -> Self {
32        Self(Right(v))
33    }
34}
35
36#[inline(always)]
37fn left_only<T: Integer, R: Reducer<T>>(lhs: Mint<T, R>, rhs: Mint<T, R>) -> (T, T) {
38    match (lhs.0, rhs.0) {
39        (Left(v1), Left(v2)) => (v1, v2),
40        (_, _) => unreachable!(),
41    }
42}
43
44#[inline(always)]
45fn left_ref_only<'a, T: Integer, R: Reducer<T>>(
46    lhs: &'a Mint<T, R>,
47    rhs: &'a Mint<T, R>,
48) -> (&'a T, &'a T) {
49    match (&lhs.0, &rhs.0) {
50        (Left(v1), Left(v2)) => (v1, v2),
51        (_, _) => unreachable!(),
52    }
53}
54
55macro_rules! forward_binops_left_ref_only {
56    ($method:ident) => {
57        #[inline(always)]
58        fn $method(&self, other: &Self) -> Self {
59            let (v1, v2) = left_ref_only(self, other);
60            Self(Left(v1.$method(v2)))
61        }
62    };
63    ($method:ident => $return:ty) => {
64        #[inline(always)]
65        fn $method(&self, other: &Self) -> $return {
66            let (v1, v2) = left_ref_only(self, other);
67            v1.$method(v2)
68        }
69    };
70}
71
72macro_rules! forward_uops_ref {
73    ($method:ident => $return:ty) => {
74        #[inline(always)]
75        fn $method(&self) -> $return {
76            match &self.0 {
77                Left(v) => v.$method(),
78                Right(m) => m.residue().$method(),
79            }
80        }
81    };
82}
83
84impl<T: Integer + Clone, R: Reducer<T>> PartialEq for Mint<T, R> {
85    fn eq(&self, other: &Self) -> bool {
86        match (&self.0, &other.0) {
87            (Left(v1), Left(v2)) => v1 == v2,
88            (Right(v1), Right(v2)) => v1 == v2,
89            (_, _) => unreachable!(), // force optimization of equality test
90        }
91    }
92}
93impl<T: Integer + Clone, R: Reducer<T>> Eq for Mint<T, R> {}
94
95impl<T: Integer + Clone, R: Reducer<T> + Clone> PartialOrd for Mint<T, R> {
96    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
97        match (&self.0, &other.0) {
98            (Left(v1), Left(v2)) => v1.partial_cmp(v2),
99            (Left(v1), Right(v2)) => v1.partial_cmp(&v2.residue()),
100            (Right(v1), Left(v2)) => v1.residue().partial_cmp(v2),
101            (Right(v1), Right(v2)) => {
102                debug_assert!(v1.modulus() == v2.modulus());
103                v1.residue().partial_cmp(&v2.residue())
104            }
105        }
106    }
107}
108impl<T: Integer + Clone, R: Reducer<T> + Clone> Ord for Mint<T, R> {
109    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
110        match (&self.0, &other.0) {
111            (Left(v1), Left(v2)) => v1.cmp(v2),
112            (Left(v1), Right(v2)) => v1.cmp(&v2.residue()),
113            (Right(v1), Left(v2)) => v1.residue().cmp(v2),
114            (Right(v1), Right(v2)) => v1.residue().cmp(&v2.residue()),
115        }
116    }
117}
118
119impl<T: Integer + Clone, R: Reducer<T> + Clone> Mint<T, R> {
120    #[inline(always)]
121    pub fn value(&self) -> T {
122        match &self.0 {
123            Left(v) => v.clone(),
124            Right(m) => m.residue(),
125        }
126    }
127}
128
129// forward binary operators by converting result to MontgomeryInt whenever possible
130macro_rules! forward_binops_right {
131    (impl $imp:ident, $method:ident) => {
132        impl<T: Integer + Clone, R: Reducer<T> + Clone> $imp for Mint<T, R> {
133            type Output = Self;
134            #[inline]
135            fn $method(self, rhs: Self) -> Self::Output {
136                Self(match (self.0, rhs.0) {
137                    (Left(v1), Left(v2)) => Left(v1.$method(v2)),
138                    (Left(v1), Right(v2)) => Right(v2.convert(v1).$method(v2)),
139                    (Right(v1), Left(v2)) => {
140                        let v2 = v1.convert(v2);
141                        Right(v1.$method(v2))
142                    }
143                    (Right(v1), Right(v2)) => Right(v1.$method(v2)),
144                })
145            }
146        }
147
148        impl<T: Integer + Clone + for<'r> $imp<&'r T, Output = T>, R: Reducer<T> + Clone>
149            $imp<&Self> for Mint<T, R>
150        {
151            type Output = Mint<T, R>;
152            #[inline]
153            fn $method(self, rhs: &Self) -> Self::Output {
154                Mint(match (self.0, &rhs.0) {
155                    (Left(v1), Left(v2)) => Left(v1.$method(v2)),
156                    (Left(v1), Right(v2)) => Right(v2.convert(v1).$method(v2)),
157                    (Right(v1), Left(v2)) => {
158                        let v2 = v1.convert(v2.clone());
159                        Right(v1.$method(v2))
160                    }
161                    (Right(v1), Right(v2)) => Right(v1.$method(v2)),
162                })
163            }
164        }
165
166        impl<T: Integer + Clone, R: Reducer<T> + Clone> $imp<Mint<T, R>> for &Mint<T, R> {
167            type Output = Mint<T, R>;
168            // FIXME: additional clone here due to https://github.com/rust-lang/rust/issues/39959
169            // (same for ref & ref operation below, and those for Div and Rem)
170            #[inline]
171            fn $method(self, rhs: Mint<T, R>) -> Self::Output {
172                Mint(match (&self.0, rhs.0) {
173                    (Left(v1), Left(v2)) => Left(v1.clone().$method(v2)),
174                    (Left(v1), Right(v2)) => Right(v2.convert(v1.clone()).$method(v2)),
175                    (Right(v1), Left(v2)) => {
176                        let v2 = v1.convert(v2);
177                        Right(v1.clone().$method(v2))
178                    }
179                    (Right(v1), Right(v2)) => Right(v1.$method(v2)),
180                })
181            }
182        }
183        impl<
184                'a,
185                'b,
186                T: Integer + Clone + for<'r> $imp<&'r T, Output = T>,
187                R: Reducer<T> + Clone,
188            > $imp<&'b Mint<T, R>> for &'a Mint<T, R>
189        {
190            type Output = Mint<T, R>;
191            #[inline]
192            fn $method(self, rhs: &Mint<T, R>) -> Self::Output {
193                Mint(match (&self.0, &rhs.0) {
194                    (Left(v1), Left(v2)) => Left(v1.clone().$method(v2)),
195                    (Left(v1), Right(v2)) => Right(v2.convert(v1.clone()).$method(v2)),
196                    (Right(v1), Left(v2)) => {
197                        let v2 = v1.convert(v2.clone());
198                        Right(v1.clone().$method(v2))
199                    }
200                    (Right(v1), Right(v2)) => Right(v1.$method(v2)),
201                })
202            }
203        }
204    };
205}
206
207forward_binops_right!(impl Add, add);
208forward_binops_right!(impl Sub, sub);
209forward_binops_right!(impl Mul, mul);
210
211impl<T: Integer + Clone, R: Reducer<T>> Div for Mint<T, R> {
212    type Output = Self;
213
214    #[inline]
215    fn div(self, rhs: Self) -> Self::Output {
216        let (v1, v2) = left_only(self, rhs);
217        Self(Left(v1.div(v2)))
218    }
219}
220impl<T: Integer + Clone + for<'r> Div<&'r T, Output = T>, R: Reducer<T>> Div<&Self> for Mint<T, R> {
221    type Output = Self;
222
223    #[inline]
224    fn div(self, rhs: &Self) -> Self::Output {
225        match (self.0, &rhs.0) {
226            (Left(v1), Left(v2)) => Self(Left(v1.div(v2))),
227            (_, _) => unreachable!(),
228        }
229    }
230}
231impl<T: Integer + Clone, R: Reducer<T>> Div<Mint<T, R>> for &Mint<T, R> {
232    type Output = Mint<T, R>;
233
234    #[inline]
235    fn div(self, rhs: Mint<T, R>) -> Self::Output {
236        match (&self.0, rhs.0) {
237            (Left(v1), Left(v2)) => Mint(Left(v1.clone().div(v2))),
238            (_, _) => unreachable!(),
239        }
240    }
241}
242impl<'a, 'b, T: Integer + Clone + for<'r> Div<&'r T, Output = T>, R: Reducer<T>> Div<&'b Mint<T, R>>
243    for &'a Mint<T, R>
244{
245    type Output = Mint<T, R>;
246    #[inline]
247    fn div(self, rhs: &Mint<T, R>) -> Self::Output {
248        match (&self.0, &rhs.0) {
249            (Left(v1), Left(v2)) => Mint(Left(v1.clone().div(v2))),
250            (_, _) => unreachable!(),
251        }
252    }
253}
254
255impl<T: Integer + Clone, R: Reducer<T> + Clone> Rem for Mint<T, R> {
256    type Output = Self;
257
258    #[inline]
259    fn rem(self, rhs: Self) -> Self::Output {
260        match (self.0, rhs.0) {
261            (Left(v1), Left(v2)) => Self(Right(ReducedInt::new(v1, &v2))),
262            (Right(v1), Left(v2)) => {
263                debug_assert!(v1.modulus() == v2);
264                Self(Right(v1))
265            }
266            (_, _) => unreachable!(),
267        }
268    }
269}
270impl<T: Integer + Clone, R: Reducer<T> + Clone> Rem<&Self> for Mint<T, R> {
271    type Output = Self;
272
273    #[inline]
274    fn rem(self, rhs: &Self) -> Self::Output {
275        match (self.0, &rhs.0) {
276            (Left(v1), Left(v2)) => Self(Right(ReducedInt::new(v1, v2))),
277            (Right(v1), Left(v2)) => {
278                debug_assert!(&v1.modulus() == v2);
279                Self(Right(v1))
280            }
281            (_, _) => unreachable!(),
282        }
283    }
284}
285impl<T: Integer + Clone, R: Reducer<T> + Clone> Rem<Mint<T, R>> for &Mint<T, R> {
286    type Output = Mint<T, R>;
287
288    #[inline]
289    fn rem(self, rhs: Mint<T, R>) -> Self::Output {
290        match (&self.0, rhs.0) {
291            (Left(v1), Left(v2)) => Mint(Right(ReducedInt::new(v1.clone(), &v2))),
292            (Right(v1), Left(v2)) => {
293                debug_assert!(v1.modulus() == v2);
294                Mint(Right(v1.clone()))
295            }
296            (_, _) => unreachable!(),
297        }
298    }
299}
300impl<'a, 'b, T: Integer + Clone, R: Reducer<T> + Clone> Rem<&'b Mint<T, R>> for &'a Mint<T, R> {
301    type Output = Mint<T, R>;
302
303    #[inline]
304    fn rem(self, rhs: &Mint<T, R>) -> Self::Output {
305        match (&self.0, &rhs.0) {
306            (Left(v1), Left(v2)) => Mint(Right(ReducedInt::new(v1.clone(), v2))),
307            (Right(v1), Left(v2)) => {
308                debug_assert!(&v1.modulus() == v2);
309                Mint(Right(v1.clone()))
310            }
311            (_, _) => unreachable!(),
312        }
313    }
314}
315
316impl<T: Integer + Clone, R: Reducer<T> + Clone> Zero for Mint<T, R> {
317    #[inline(always)]
318    fn zero() -> Self {
319        Self(Left(T::zero()))
320    }
321    #[inline(always)]
322    fn is_zero(&self) -> bool {
323        match &self.0 {
324            Left(v) => v.is_zero(),
325            Right(m) => m.is_zero(),
326        }
327    }
328}
329
330impl<T: Integer + Clone, R: Reducer<T> + Clone> One for Mint<T, R> {
331    #[inline(always)]
332    fn one() -> Self {
333        Self(Left(T::one()))
334    }
335    forward_uops_ref!(is_one => bool);
336}
337
338impl<T: Integer + Clone, R: Reducer<T> + Clone> Num for Mint<T, R> {
339    type FromStrRadixErr = <T as Num>::FromStrRadixErr;
340
341    #[inline(always)]
342    fn from_str_radix(str: &str, radix: u32) -> Result<Self, Self::FromStrRadixErr> {
343        T::from_str_radix(str, radix).map(|v| Self(Left(v)))
344    }
345}
346
347impl<T: Integer + Clone, R: Reducer<T> + Clone> Integer for Mint<T, R> {
348    forward_binops_left_ref_only!(div_floor);
349    forward_binops_left_ref_only!(mod_floor);
350    forward_binops_left_ref_only!(lcm);
351    forward_binops_left_ref_only!(divides => bool);
352    forward_binops_left_ref_only!(is_multiple_of => bool);
353    forward_uops_ref!(is_even => bool);
354    forward_uops_ref!(is_odd => bool);
355
356    #[inline(always)]
357    fn div_rem(&self, other: &Self) -> (Self, Self) {
358        let (v1, v2) = left_ref_only(self, other);
359        let (q, r) = v1.div_rem(v2);
360        (Self(Left(q)), Self(Left(r)))
361    }
362    #[inline(always)]
363    fn gcd(&self, other: &Self) -> Self {
364        Self(Left(match (&self.0, &other.0) {
365            (Left(v1), Left(v2)) => v1.gcd(v2),
366            (Right(v1), Left(v2)) => v1.residue().gcd(v2),
367            (Left(v1), Right(v2)) => v1.gcd(&v2.residue()),
368            (Right(v1), Right(v2)) => v1.residue().gcd(&v2.residue()),
369        }))
370    }
371}
372
373impl<T: Integer + Clone + Roots, R: Reducer<T> + Clone> Roots for Mint<T, R> {
374    #[inline]
375    fn nth_root(&self, n: u32) -> Self {
376        match &self.0 {
377            Left(v) => Self(Left(v.nth_root(n))),
378            Right(_) => unreachable!(),
379        }
380    }
381}
382
383impl<T: Integer + Clone + FromPrimitive, R: Reducer<T>> FromPrimitive for Mint<T, R> {
384    #[inline]
385    fn from_f64(n: f64) -> Option<Self> {
386        T::from_f64(n).map(|v| Self(Left(v)))
387    }
388    #[inline]
389    fn from_i64(n: i64) -> Option<Self> {
390        T::from_i64(n).map(|v| Self(Left(v)))
391    }
392    #[inline]
393    fn from_u64(n: u64) -> Option<Self> {
394        T::from_u64(n).map(|v| Self(Left(v)))
395    }
396}
397
398impl<T: Integer + Clone + ToPrimitive, R: Reducer<T> + Clone> ToPrimitive for Mint<T, R> {
399    #[inline]
400    fn to_f64(&self) -> Option<f64> {
401        match &self.0 {
402            Left(v) => v.to_f64(),
403            Right(m) => m.residue().to_f64(),
404        }
405    }
406    #[inline]
407    fn to_i64(&self) -> Option<i64> {
408        match &self.0 {
409            Left(v) => v.to_i64(),
410            Right(m) => m.residue().to_i64(),
411        }
412    }
413    #[inline]
414    fn to_u64(&self) -> Option<u64> {
415        match &self.0 {
416            Left(v) => v.to_u64(),
417            Right(m) => m.residue().to_u64(),
418        }
419    }
420}
421
422impl<T: Integer + Clone + Pow<u32, Output = T>, R: Reducer<T>> Pow<u32> for Mint<T, R> {
423    type Output = Self;
424    #[inline]
425    fn pow(self, rhs: u32) -> Self::Output {
426        match self.0 {
427            Left(v) => Self(Left(v.pow(rhs))),
428            Right(_) => unreachable!(),
429        }
430    }
431}
432
433impl<T: Integer + Clone + ExactRoots, R: Reducer<T> + Clone> ExactRoots for Mint<T, R> {
434    #[inline]
435    fn nth_root_exact(&self, n: u32) -> Option<Self> {
436        match &self.0 {
437            Left(v) => v.nth_root_exact(n).map(|v| Self(Left(v))),
438            Right(_) => unreachable!(),
439        }
440    }
441}
442
443impl<T: Integer + Clone + BitTest, R: Reducer<T>> BitTest for Mint<T, R> {
444    #[inline]
445    fn bit(&self, position: usize) -> bool {
446        match &self.0 {
447            Left(v) => v.bit(position),
448            Right(_) => unreachable!(),
449        }
450    }
451    #[inline]
452    fn bits(&self) -> usize {
453        match &self.0 {
454            Left(v) => v.bits(),
455            Right(_) => unreachable!(),
456        }
457    }
458    #[inline]
459    fn trailing_zeros(&self) -> usize {
460        match &self.0 {
461            Left(v) => v.trailing_zeros(),
462            Right(_) => unreachable!(),
463        }
464    }
465}
466
467impl<T: Integer + Clone + Shr<usize, Output = T>, R: Reducer<T>> Shr<usize> for Mint<T, R> {
468    type Output = Self;
469    #[inline]
470    fn shr(self, rhs: usize) -> Self::Output {
471        match self.0 {
472            Left(v) => Self(Left(v >> rhs)),
473            Right(_) => unreachable!(),
474        }
475    }
476}
477impl<T: Integer + Clone + Shr<usize, Output = T>, R: Reducer<T>> Shr<usize> for &Mint<T, R> {
478    type Output = Mint<T, R>;
479    #[inline]
480    fn shr(self, rhs: usize) -> Self::Output {
481        match &self.0 {
482            Left(v) => Mint(Left(v.clone() >> rhs)),
483            Right(_) => unreachable!(),
484        }
485    }
486}
487
488impl<T: Integer + Clone, R: Reducer<T> + Clone> ModularCoreOps<&Self, &Self> for Mint<T, R> {
489    type Output = Self;
490    #[inline]
491    fn addm(self, rhs: &Self, m: &Self) -> Self::Output {
492        match (self.0, &rhs.0, &m.0) {
493            (Right(v1), Right(v2), Left(m)) => {
494                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
495                Self(Right(v1 + v2))
496            }
497            (_, _, _) => unreachable!(),
498        }
499    }
500    #[inline]
501    fn subm(self, rhs: &Self, m: &Self) -> Self::Output {
502        match (self.0, &rhs.0, &m.0) {
503            (Right(v1), Right(v2), Left(m)) => {
504                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
505                Self(Right(v1 - v2))
506            }
507            (_, _, _) => unreachable!(),
508        }
509    }
510    #[inline]
511    fn mulm(self, rhs: &Self, m: &Self) -> Self::Output {
512        match (self.0, &rhs.0, &m.0) {
513            (Right(v1), Right(v2), Left(m)) => {
514                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
515                Self(Right(v1 * v2))
516            }
517            (_, _, _) => unreachable!(),
518        }
519    }
520}
521impl<'a, 'b, T: Integer + Clone, R: Reducer<T> + Clone>
522    ModularCoreOps<&'b Mint<T, R>, &'b Mint<T, R>> for &'a Mint<T, R>
523{
524    type Output = Mint<T, R>;
525    #[inline]
526    fn addm(self, rhs: &Mint<T, R>, m: &Mint<T, R>) -> Self::Output {
527        match (&self.0, &rhs.0, &m.0) {
528            (Right(v1), Right(v2), Left(m)) => {
529                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
530                Mint(Right(v1 + v2))
531            }
532            (_, _, _) => unreachable!(),
533        }
534    }
535    #[inline]
536    fn subm(self, rhs: &Mint<T, R>, m: &Mint<T, R>) -> Self::Output {
537        match (&self.0, &rhs.0, &m.0) {
538            (Right(v1), Right(v2), Left(m)) => {
539                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
540                Mint(Right(v1 - v2))
541            }
542            (_, _, _) => unreachable!(),
543        }
544    }
545    #[inline]
546    fn mulm(self, rhs: &Mint<T, R>, m: &Mint<T, R>) -> Self::Output {
547        match (&self.0, &rhs.0, &m.0) {
548            (Right(v1), Right(v2), Left(m)) => {
549                debug_assert!(&v1.modulus() == m && &v2.modulus() == m);
550                Mint(Right(v1 * v2))
551            }
552            (_, _, _) => unreachable!(),
553        }
554    }
555}
556
557impl<T: Integer + Clone, R: Reducer<T> + Clone> ModularUnaryOps<&Self> for Mint<T, R> {
558    type Output = Self;
559    #[inline]
560    fn negm(self, m: &Self) -> Self::Output {
561        Self(Right(match (self.0, &m.0) {
562            (Left(v), Left(m)) => ReducedInt::new(v, m).neg(),
563            (Right(v), Left(m)) => {
564                debug_assert!(&v.modulus() == m);
565                v.neg()
566            }
567            (_, Right(_)) => unreachable!(),
568        }))
569    }
570    fn invm(self, _: &Self) -> Option<Self::Output> {
571        unreachable!() // not used in this crate
572    }
573    #[inline]
574    fn dblm(self, m: &Self) -> Self::Output {
575        Self(Right(match (self.0, &m.0) {
576            (Left(v), Left(m)) => ReducedInt::new(v, m).double(),
577            (Right(v), Left(m)) => {
578                debug_assert!(&v.modulus() == m);
579                v.double()
580            }
581            (_, Right(_)) => unreachable!(),
582        }))
583    }
584    #[inline]
585    fn sqm(self, m: &Self) -> Self::Output {
586        Self(Right(match (self.0, &m.0) {
587            (Left(v), Left(m)) => ReducedInt::new(v, m).square(),
588            (Right(v), Left(m)) => {
589                debug_assert!(&v.modulus() == m);
590                v.square()
591            }
592            (_, Right(_)) => unreachable!(),
593        }))
594    }
595}
596impl<'a, 'b, T: Integer + Clone, R: Reducer<T> + Clone> ModularUnaryOps<&'b Mint<T, R>>
597    for &'a Mint<T, R>
598{
599    type Output = Mint<T, R>;
600    #[inline]
601    fn negm(self, m: &Mint<T, R>) -> Self::Output {
602        Mint(Right(match (&self.0, &m.0) {
603            (Left(v), Left(m)) => ReducedInt::new(v.clone(), m).neg(),
604            (Right(v), Left(m)) => {
605                debug_assert!(&v.modulus() == m);
606                v.clone().neg()
607            }
608            (_, Right(_)) => unreachable!(),
609        }))
610    }
611    fn invm(self, _: &Mint<T, R>) -> Option<Self::Output> {
612        unreachable!() // not used in this crate
613    }
614    #[inline]
615    fn dblm(self, m: &Mint<T, R>) -> Self::Output {
616        Mint(Right(match (&self.0, &m.0) {
617            (Left(v), Left(m)) => ReducedInt::new(v.clone(), m).double(),
618            (Right(v), Left(m)) => {
619                debug_assert!(&v.modulus() == m);
620                v.clone().double()
621            }
622            (_, Right(_)) => unreachable!(),
623        }))
624    }
625    #[inline]
626    fn sqm(self, m: &Mint<T, R>) -> Self::Output {
627        Mint(Right(match (&self.0, &m.0) {
628            (Left(v), Left(m)) => ReducedInt::new(v.clone(), m).square(),
629            (Right(v), Left(m)) => {
630                debug_assert!(&v.modulus() == m);
631                v.clone().square()
632            }
633            (_, Right(_)) => unreachable!(),
634        }))
635    }
636}
637
638impl<T: Integer + Clone + for<'r> ModularSymbols<&'r T>, R: Reducer<T> + Clone>
639    ModularSymbols<&Self> for Mint<T, R>
640{
641    #[inline]
642    fn checked_jacobi(&self, n: &Self) -> Option<i8> {
643        match (&self.0, &n.0) {
644            (Left(a), Left(n)) => a.checked_jacobi(n),
645            (Right(a), Left(n)) => a.residue().checked_jacobi(n),
646            (_, Right(_)) => unreachable!(),
647        }
648    }
649    #[inline]
650    fn checked_legendre(&self, n: &Self) -> Option<i8> {
651        match (&self.0, &n.0) {
652            (Left(a), Left(n)) => a.checked_legendre(n),
653            (Right(a), Left(n)) => a.residue().checked_legendre(n),
654            (_, Right(_)) => unreachable!(),
655        }
656    }
657    #[inline]
658    fn kronecker(&self, n: &Self) -> i8 {
659        match (&self.0, &n.0) {
660            (Left(a), Left(n)) => a.kronecker(n),
661            (Right(a), Left(n)) => a.residue().kronecker(n),
662            (_, Right(_)) => unreachable!(),
663        }
664    }
665}
666
667impl<T: Integer + Clone, R: Reducer<T> + Clone> ModularPow<&Self, &Self> for Mint<T, R> {
668    type Output = Self;
669    #[inline]
670    fn powm(self, exp: &Self, m: &Self) -> Self::Output {
671        Self(Right(match (self.0, &exp.0, &m.0) {
672            (Left(v), Left(e), Left(m)) => ReducedInt::new(v, m).pow(e.clone()),
673            (Right(v), Left(e), Left(m)) => {
674                debug_assert!(&v.modulus() == m);
675                v.pow(e.clone())
676            }
677            (_, _, _) => unreachable!(),
678        }))
679    }
680}
681
682pub type SmallMint<T> = Mint<T, Montgomery<T, T>>;
683
684#[cfg(test)]
685mod tests {
686    use super::*;
687
688    #[test]
689    fn test_basics() {
690        let a: SmallMint<u32> = 19.into();
691        let b: SmallMint<u32> = 8.into();
692        assert_eq!(a + b, 27.into());
693    }
694}
num_prime/mint.rs

num_prime/
mint.rs
