1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

#![no_std]
//! modulo_tools
//! ```
//! use modulo_n_tools::*;
//! use modulo_n_tools::montgomery::*;
//! let a = add_mod(&3, &4, &5);
//! assert_eq!(a, 2);
//! let b = mul_mod(&3, &a, &5);
//! assert_eq!(b, 1);
//! let c = pow_mod(2, 6, &7);
//! assert_eq!(c, 1);
//! let m = Montgomery64::new(57);
//! let d = m.powmod(5, 42);
//! assert_eq!(d, 7);
//! ```
use core::ops::{Add, AddAssign, BitAnd, Mul, Neg, Rem, ShrAssign, Sub, SubAssign};
pub mod montgomery;

fn reduce<T>(mut a: T, modulo: &T) -> T
where
    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
    for<'x> &'x T: Neg<Output = T>,
{
    if &a >= modulo {
        a -= modulo;
    } else if a <= -modulo {
        a += modulo
    }
    a
}

/// $`a + b \bmod n`$
///
/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
/// ```
/// use modulo_n_tools::add_mod;
/// assert_eq!(add_mod(&3, &4, &5), 2);
/// assert_eq!(add_mod(&2, &5, &6), 1);
/// assert_eq!(add_mod(&-3, &-2, &4), -1);
/// assert_eq!(add_mod(&2, &3, &5), 0);
/// ```
pub fn add_mod<T>(a: &T, b: &T, modulo: &T) -> T
where
    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
    for<'x> &'x T: Add<Output = T> + Neg<Output = T>,
{
    let c = a + b;
    reduce(c, modulo)
}

/// $`a - b \bmod n`$
///
/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
/// ```
/// use modulo_n_tools::sub_mod;
/// assert_eq!(sub_mod(&3, &4, &5), -1);
/// assert_eq!(sub_mod(&2, &-5, &6), 1);
/// assert_eq!(sub_mod(&-2, &-3, &4), 1);
/// assert_eq!(sub_mod(&2, &2, &5), 0);
/// ```
pub fn sub_mod<T>(a: &T, b: &T, modulo: &T) -> T
where
    T: Ord + for<'x> AddAssign<&'x T> + for<'x> SubAssign<&'x T>,
    for<'x> &'x T: Sub<Output = T> + Neg<Output = T>,
{
    let c = a - b;
    reduce(c, modulo)
}

/// $`ab \bmod n`$
///
/// Input: $`-\text{modulo} \leq a,\, b \leq \text{modulo}`$  
/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
/// ```
/// use modulo_n_tools::mul_mod;
/// assert_eq!(mul_mod(&3, &4, &5), 2);
/// assert_eq!(mul_mod(&2, &5, &6), 4);
/// assert_eq!(mul_mod(&-2, &-3, &4), 2);
/// assert_eq!(mul_mod(&2, &3, &6), 0);
/// ```
pub fn mul_mod<T>(a: &T, b: &T, modulo: &T) -> T
where
    for<'x> &'x T: Mul<Output = T> + Rem<Output = T>,
{
    &(a * b) % modulo
}

/// $`a^b \bmod n`$
///
/// Input: $`-\text{modulo} \leq a \leq \text{modulo}`$,
/// b is non-negative integer.  
/// Output: $`-\text{modulo} \leq x \leq \text{modulo}`$
/// ```
/// use modulo_n_tools::pow_mod;
/// assert_eq!(pow_mod(3, 4, &5), 1);
/// assert_eq!(pow_mod(2, 5, &6), 2);
/// assert_eq!(pow_mod(-2, 3, &4), 0);
/// assert_eq!(pow_mod(2, 3, &7), 1);
/// ```
pub fn pow_mod<T, U>(a: T, mut b: U, modulo: &T) -> T
where
    T: From<u8>,
    for<'x> &'x T: Mul<Output = T> + Rem<Output = T>,
    U: Ord + ShrAssign<u8> + From<u8>,
    for<'x> &'x U: BitAnd<Output = U>,
{
    let c0 = U::from(0);
    let c1 = U::from(1);
    let mut x = a;
    let mut y = T::from(1);
    while b > c0 {
        if &b & &c1 != c0 {
            y = mul_mod(&x, &y, modulo);
        }
        x = mul_mod(&x, &x, modulo);
        b >>= 1;
    }
    y
}