Primo: sorry za abstrakcyjny język, ale sądzę, że się połapiecie
To też, jak w tytule implementuję test Miller'a-Rabin'a w Ruscie:
#[derive(Debug, PartialEq, Eq, Copy, Clone)]
pub enum Result {
PropablyPrime,
Composite,
}
impl Result {
pub fn is_composite(&self) -> bool {
match self {
&Result::Composite => true,
_ => false
}
}
}
pub trait PrimeTest {
fn test(&mut self, num: &BigUint) -> Result;
fn test_loop(&mut self, num: &BigUint, times: usize) -> Result {
for _ in 0..times {
if self.test(&num).is_composite() { return Result::Composite }
}
Result::PropablyPrime
}
}
#[derive(Debug, PartialEq, Eq, Copy, Clone)]
pub enum Result {
PropablyPrime,
Composite,
}
impl Result {
pub fn is_composite(&self) -> bool {
match self {
&Result::Composite => true,
_ => false
}
}
}
pub trait PrimeTest {
fn test(&mut self, num: &BigUint) -> Result;
fn test_loop(&mut self, num: &BigUint, times: usize) -> Result {
for _ in 0..times {
if self.test(&num).is_composite() { return Result::Composite }
}
Result::PropablyPrime
}
}
pub struct MillerRabin<T: RandBigInt>(T);
impl<T: RandBigInt> MillerRabin<T> {
fn greatest_2_divisor(num: &BigUint) -> (usize, BigUint) {
let mut s = 0;
let mut num = num - BigUint::one();
while num.is_even() {
num = num >> 1;
s += 1;
}
(s, num)
}
fn witness(num: BigUint, a: BigUint, d: &BigUint, s: usize) -> Result {
let mut x = (&a).pow_mod(d, &num);
if x == one() || x == (&num - BigUint::one()) { return Result::Composite }
for _ in 0..s {
x = (&x * &x) % #
if x == one() { return Result::Composite }
if x == (&num - BigUint::one()) { return Result::PropablyPrime }
}
Result::Composite
}
}
impl<T: RandBigInt> PrimeTest for MillerRabin<T> {
fn test(&mut self, num: &BigUint) -> Result {
let a = self.0.gen_biguint_below(num);
let (s, d) = Self::greatest_2_divisor(&num);
Self::witness(num - BigUint::one(), a, &d, s)
}
}
No i szukam gdzie mam błąd, ale nawet z GDB mi idzie słabo. Ma ktoś jakiś pomysł?
Test, którego to nie przechodzi:
fn test_miller_rabin_prime() {
let res = miller_rabin().test_loop(&4393139u64.to_biguint().unwrap(), 20);
assert_eq!(res, Result::PropablyPrime);
}
To jest problem z moją implementacją czy z losowanymi wartościami?