Struct MontgomeryReduction64

Source

struct MontgomeryReduction64 {
    modulus: u64,
    inverse: u64,
}

Fields§

§modulus: u64§inverse: u64

Implementations§

Source §

impl MontgomeryReduction64

Source

fn new(modulus: u64) -> Self

Examples found in repository ?

crates/competitive/src/math/prime_factors.rs (line 37)

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}

Source

fn sub(&self, lhs: u64, rhs: u64) -> u64

Examples found in repository ?

crates/competitive/src/math/prime_factors.rs (line 47)

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}

Source

fn mul(&self, lhs: u64, rhs: u64) -> u64

Examples found in repository ?

crates/competitive/src/math/prime_factors.rs (line 47)

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}