Test Miller'a-Rabin'a - wykłada się dla małej liczby pierwszej

0

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) % &num;
            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?

0

Co znaczy "wykłada się"? Zła odpowiedź czy segfault?
Aby wykluczyć losowe liczby wykorzystaj to:
jeśli n < 341,550,071,728,321, wystarczy sprawdzić a = 2, 3, 5, 7, 11, 13 i 17 (za wiki).

0

Liczby mają być znacznie większe niż 341,550,071,728,321 (docelowo 1024+ bitów) więc nie wystarczy mi taka dokładność, musi być pełen Miller-Rabin (niestety).

PS - Wykłada się to znaczy "zła odpowiedź", w Ruscie praktycznie nie da się mieć segfaulta z definicji (bezpieczeństwo pamięci jest zapewnione w czasie kompilacji).

EDIT:

Błąd znaleziony, oczywiście linijka:

if x == one() || x == (&num - BigUint::one()) { return Result::Composite }

Powinna zwracać Result::PropablyPrime zamiast Result::Composite.

Epic fail.

1 użytkowników online, w tym zalogowanych: 0, gości: 1