modulo_n_tools/
lib.rs

1#![no_std]
2//! modulo_tools
3//! ```
4//! use modulo_n_tools::*;
5//! use modulo_n_tools::montgomery::*;
6//! let a = add_mod(&3, &4, &5);
7//! assert_eq!(a, 2);
8//! let b = mul_mod(&3, &a, &5);
9//! assert_eq!(b, 1);
10//! let c = pow_mod(2, 6, &7);
11//! assert_eq!(c, 1);
12//! let m = Montgomery64::new(57);
13//! let d = m.powmod(5, 42);
14//! assert_eq!(d, 7);
15//! ```
16use core::ops::{Add, AddAssign, BitAnd, Mul, Neg, Rem, ShrAssign, Sub, SubAssign};
17pub mod montgomery;
18
19fn reduce<T>(mut a: T, modulo: &T) -> T
20where
21    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
22    for<'x> &'x T: Neg<Output = T>,
23{
24    if &a >= modulo {
25        a -= modulo;
26    } else if a <= -modulo {
27        a += modulo
28    }
29    a
30}
31
32/// $`a + b \bmod n`$
33///
34/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
35/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
36/// ```
37/// use modulo_n_tools::add_mod;
38/// assert_eq!(add_mod(&3, &4, &5), 2);
39/// assert_eq!(add_mod(&2, &5, &6), 1);
40/// assert_eq!(add_mod(&-3, &-2, &4), -1);
41/// assert_eq!(add_mod(&2, &3, &5), 0);
42/// ```
43pub fn add_mod<T>(a: &T, b: &T, modulo: &T) -> T
44where
45    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
46    for<'x> &'x T: Add<Output = T> + Neg<Output = T>,
47{
48    let c = a + b;
49    reduce(c, modulo)
50}
51
52/// $`a - b \bmod n`$
53///
54/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
55/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
56/// ```
57/// use modulo_n_tools::sub_mod;
58/// assert_eq!(sub_mod(&3, &4, &5), -1);
59/// assert_eq!(sub_mod(&2, &-5, &6), 1);
60/// assert_eq!(sub_mod(&-2, &-3, &4), 1);
61/// assert_eq!(sub_mod(&2, &2, &5), 0);
62/// ```
63pub fn sub_mod<T>(a: &T, b: &T, modulo: &T) -> T
64where
65    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
66    for<'x> &'x T: Sub<Output = T> + Neg<Output = T>,
67{
68    let c = a - b;
69    reduce(c, modulo)
70}
71
72/// $`ab \bmod n`$
73///
74/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
75/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
76/// ```
77/// use modulo_n_tools::mul_mod;
78/// assert_eq!(mul_mod(&3, &4, &5), 2);
79/// assert_eq!(mul_mod(&2, &5, &6), 4);
80/// assert_eq!(mul_mod(&-2, &-3, &4), 2);
81/// assert_eq!(mul_mod(&2, &3, &6), 0);
82/// ```
83pub fn mul_mod<T>(a: &T, b: &T, modulo: &T) -> T
84where
85    for<'x> &'x T: Mul<Output = T> + Rem<Output = T>,
86{
87    &(a * b) % modulo
88}
89
90/// $`a^b \bmod n`$
91///
92/// Input: $`-\text{modulo} \leq a \leq \text{modulo}`$,
93/// b is non-negative integer.  
94/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
95/// ```
96/// use modulo_n_tools::pow_mod;
97/// assert_eq!(pow_mod(3, 4, &5), 1);
98/// assert_eq!(pow_mod(2, 5, &6), 2);
99/// assert_eq!(pow_mod(-2, 3, &4), 0);
100/// assert_eq!(pow_mod(2, 3, &7), 1);
101/// ```
102pub fn pow_mod<T, U>(a: T, mut b: U, modulo: &T) -> T
103where
104    T: From<u8>,
105    for<'x> &'x T: Mul<Output = T> + Rem<Output = T>,
106    U: Ord + ShrAssign<u8> + From<u8>,
107    for<'x> &'x U: BitAnd<Output = U>,
108{
109    let c0 = U::from(0);
110    let c1 = U::from(1);
111    let mut x = a;
112    let mut y = T::from(1);
113    while b > c0 {
114        if &b & &c1 != c0 {
115            y = mul_mod(&x, &y, modulo);
116        }
117        x = mul_mod(&x, &x, modulo);
118        b >>= 1;
119    }
120    y
121}
122
123/// $`a\cdot b^p \bmod n`$
124///
125/// Input: $`-\text{modulo} \leq b \leq \text{modulo}`$,
126/// c is non-negative integer.  
127/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
128/// ```
129/// use modulo_n_tools::mul_pow_mod;
130/// assert_eq!(mul_pow_mod(1, 3, 4, &5), 1);
131/// assert_eq!(mul_pow_mod(1, 2, 5, &6), 2);
132/// assert_eq!(mul_pow_mod(1, -2, 3, &4), 0);
133/// assert_eq!(mul_pow_mod(1, 2, 3, &7), 1);
134/// ```
135pub fn mul_pow_mod<T, U>(a: T, base: T, mut power: U, modulo: &T) -> T
136where
137    for<'x> &'x T: Mul<Output = T> + Rem<Output = T>,
138    U: Ord + ShrAssign<u8> + From<u8>,
139    for<'x> &'x U: BitAnd<Output = U>,
140{
141    let c0 = U::from(0);
142    let c1 = U::from(1);
143    let mut x = base;
144    let mut y = a;
145    while power > c0 {
146        if &power & &c1 != c0 {
147            y = mul_mod(&x, &y, modulo);
148        }
149        x = mul_mod(&x, &x, modulo);
150        power >>= 1;
151    }
152    y
153}
modulo_n_tools/lib.rs

modulo_n_tools/
lib.rs
