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 122)
121pub fn miller_rabin(n: u64) -> bool {
122    miller_rabin_with_br(n, &BarrettReduction::<u128>::new(n as u128))
123}
More examples
Hide additional examples
crates/competitive/src/math/prime_factors.rs (line 5)
3fn find_factor(n: u64) -> Option<u64> {
4    let br = BarrettReduction::<u128>::new(n as u128);
5    if miller_rabin_with_br(n, &br) {
6        return None;
7    }
8    let m = 1u64 << ((63 - n.leading_zeros()) / 5);
9    let sub = |x: u64, y: u64| if x > y { x - y } else { y - x };
10    let mul = |x: u64, y: u64| br.rem(x as u128 * y as u128) as u64;
11    for c in 12.. {
12        let f = |x: u64| (br.rem(x as u128 * x as u128) + c) as u64;
13        let (mut x, mut y, mut r, mut g, mut k, mut ys) = (0, 2, 1, 1, 0, 0);
14        while g == 1 {
15            x = y;
16            for _ in 0..r {
17                y = f(y);
18            }
19            while r > k && g == 1 {
20                ys = y;
21                let mut q = 1;
22                for _ in 0..m.min(r - k) {
23                    y = f(y);
24                    q = mul(q, sub(x, y));
25                }
26                g = gcd(q, n);
27                k += m;
28            }
29            r <<= 1;
30        }
31        if g == n {
32            g = 1;
33            while g == 1 {
34                ys = f(ys);
35                g = gcd(sub(x, ys), n);
36            }
37        }
38        if g < n {
39            return Some(g);
40        }
41    }
42    unreachable!();
43}