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
//! Mersenne prime reduction for efficient modular arithmetic.
//!
//! A pseudo-Mersenne prime has the form p = 2^n - k, where n and k are
//! integers. For such primes, modular reduction can exploit the identity
//! 2^n = k (mod p) to avoid full division.
use crate::primitives::big_number::BigNumber;
use crate::primitives::reduction_context::MersennePrime;
/// Mersenne prime reduction context.
///
/// Stores a pseudo-Mersenne prime p = 2^n - k and uses the structure
/// to perform fast modular reduction via the split-and-multiply technique.
#[derive(Debug)]
pub struct Mersenne {
/// Name identifier for this prime.
pub name: String,
/// The prime p = 2^n - k.
pub prime: BigNumber,
/// k = 2^n - p (the small correction factor).
pub k: BigNumber,
/// n = bit_length(p).
pub n: usize,
}
impl Mersenne {
/// Create a new Mersenne context from a hex string for the prime.
pub fn new(name: &str, p_hex: &str) -> Result<Self, crate::primitives::PrimitivesError> {
// Remove spaces from hex string
let hex_clean: String = p_hex.chars().filter(|c| !c.is_whitespace()).collect();
let prime = BigNumber::from_hex(&hex_clean)?;
let n = prime.bit_length();
// k = 2^n - p
let two_n = BigNumber::one().ushln(n);
let k = two_n.sub(&prime);
Ok(Mersenne {
name: name.to_string(),
prime,
k,
n,
})
}
}
impl MersennePrime for Mersenne {
fn ireduce(&self, num: &mut BigNumber) {
// num = hi * 2^n + lo = hi * k + lo (mod p)
loop {
if num.bit_length() <= self.n {
break;
}
// hi = num >> n
let hi = num.ushrn(self.n);
// lo = num & (2^n - 1)
let lo = num.maskn(self.n);
// num = hi * k + lo
let hi_k = hi.mul(&self.k);
*num = hi_k.add(&lo);
}
// Final comparison
let cmp = num.ucmp(&self.prime);
if cmp == 0 {
*num = BigNumber::zero();
} else if cmp > 0 {
*num = num.sub(&self.prime);
}
}
fn p(&self) -> &BigNumber {
&self.prime
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_mersenne_basic() {
// M31: 2^31 - 1 = 2147483647
let m = Mersenne::new("M31", "7fffffff").unwrap();
assert_eq!(m.n, 31);
assert_eq!(m.k.to_number(), Some(1)); // k = 2^31 - (2^31 - 1) = 1
}
#[test]
fn test_mersenne_reduce() {
let m = Mersenne::new("M31", "7fffffff").unwrap();
let mut n = BigNumber::from_hex("80000000").unwrap(); // 2^31
m.ireduce(&mut n);
assert_eq!(n.to_number(), Some(1)); // 2^31 mod (2^31-1) = 1
}
#[test]
fn test_mersenne_reduce_within_range() {
let m = Mersenne::new("M31", "7fffffff").unwrap();
let mut n = BigNumber::from_number(42);
m.ireduce(&mut n);
assert_eq!(n.to_number(), Some(42));
}
}