use super::PrimalityTest;
use num_traits::{PrimInt, ToPrimitive, FromPrimitive, Unsigned};
#[derive(Default)]
pub struct MillerRabinAlgorithm;
impl<N: PrimInt + ToPrimitive + FromPrimitive + Unsigned> PrimalityTest<N> for MillerRabinAlgorithm {
fn name(&self) -> &'static str {
"Miller-Rabin"
}
fn is_prime(&self, n: N) -> bool {
is_prime_miller_rabin(n, 20)
}
}
pub fn is_prime_miller_rabin<N: PrimInt + ToPrimitive + FromPrimitive + Unsigned>(n: N, _k: u32) -> bool {
let zero = N::zero();
let one = N::one();
let two = N::from_u64(2).unwrap();
let three = N::from_u64(3).unwrap();
if n <= one {
return false;
}
if n == two || n == three {
return true;
}
if n % two == zero {
return false;
}
let mut d = n - one;
let mut r = 0u32;
while d % two == zero {
d = d / two;
r += 1;
}
let witnesses = [2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
for &a in &witnesses {
let a_n = N::from_u64(a).unwrap();
if a_n >= n {
continue;
}
if !check_composite(a_n, d, r, n) {
return false;
}
}
true
}
fn check_composite<N: PrimInt + ToPrimitive + FromPrimitive + Unsigned>(a: N, d: N, r: u32, n: N) -> bool {
let one = N::one();
let mut x = pow_mod(a, d, n);
if x == one || x == n - one {
return true;
}
for _ in 0..r - 1 {
x = mul_mod(x, x, n);
if x == n - one {
return true;
}
}
false
}
fn mul_mod<N: PrimInt + ToPrimitive + FromPrimitive>(a: N, b: N, n: N) -> N {
let a_u128 = a.to_u128().unwrap();
let b_u128 = b.to_u128().unwrap();
let n_u128 = n.to_u128().unwrap();
let result = (a_u128 * b_u128) % n_u128;
N::from_u128(result).unwrap()
}
fn pow_mod<N: PrimInt + ToPrimitive + FromPrimitive + Unsigned>(mut base: N, mut exp: N, modulo: N) -> N {
let zero = N::zero();
let one = N::one();
let two = N::from_u64(2).unwrap();
let mut result = one;
base = base % modulo;
while exp > zero {
if exp % two == one {
result = mul_mod(result, base, modulo);
}
exp = exp >> 1;
base = mul_mod(base, base, modulo);
}
result
}