sem2/src/algo.rs


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

use crate::mpn::Number;

pub fn rabin_miller_test(n: &Number, k: u32) -> bool {
    if n < &4.into() {
        todo!("реализация Рабина-Миллера для n < 4");
    }

    if n.clone() % 2.into() == 0.into() {
        return false;
    }

    let n1: Number = n.clone() - 1.into();

    let mut s = 0;
    let mut d = n1.clone();

    while d.clone() % 2.into() == 0.into() {
        s += 1u32;
        d = d / 2.into();
    }

    'outer: for _ in 0..k {
        let bound = n.clone() - 4.into();
        let a = bound.random_below() + 2.into();
        let mut x = a.pow_mod(&d, &n).unwrap();

        if x == 1.into() || x == n1 {
            continue;
        } else {
            for _ in 0..=s - 1 {
                x = x.pow_mod(&2.into(), &n).unwrap();
                if x == 1.into() {
                    return false;
                } else if x == n1 {
                    continue 'outer;
                }
            }
        }
        return false;
    }
    return true;
}