Skip to main content

miller_rabin_with_br

competitive::math

Function miller_rabin_with_br 

Source 
pub fn miller_rabin_with_br(n: u64, br: &BarrettReduction<u128>) -> bool
Examples found in repository?
crates/competitive/src/math/miller_rabin.rs (line 121)
120pub fn miller_rabin(n: u64) -> bool {
121    n >= 2 && miller_rabin_with_br(n, &BarrettReduction::<u128>::new(n as u128))
122}
More examples
Hide additional examples
crates/competitive/src/math/prime_factors.rs (line 34)
32fn find_factor(n: u64) -> Option<u64> {
33    let br = BarrettReduction::<u128>::new(n as u128);
34    if miller_rabin_with_br(n, &br) {
35        return None;
36    }
37    let mr = MontgomeryReduction64::new(n);
38    let mut rng = Xorshift::default();
39    let (mut y0, mut c) = (0, n - 1);
40    loop {
41        let (mut x, mut y, mut ys, mut g, mut q, mut r, mut k) = (0, y0, 0, 1, 1, 1, 0);
42        while g == 1 && r <= 1 << 20 {
43            x = y;
44            while k < r && g == 1 {
45                ys = y;
46                for _ in 0..1024.min(r - k) {
47                    y = mr.sub(mr.mul(y, y), c);
48                    q = mr.mul(q, mr.sub(x, y));
49                }
50                g = gcd(q, n);
51                k += 1024;
52            }
53            k = r;
54            r <<= 1;
55        }
56        if g == n {
57            g = 1;
58            y = ys;
59            while g == 1 {
60                y = mr.sub(mr.mul(y, y), c);
61                g = gcd(mr.sub(x, y), n);
62            }
63        }
64        if g != 1 && g != n {
65            return Some(g);
66        }
67        y0 = ((rng.rand64() as u128 * (n - 2) as u128) >> 64) as u64 + 2;
68        c = ((rng.rand64() as u128 * (n - 1) as u128) >> 64) as u64 + 1;
69    }
70}