Struct IndexCalculusWithPrimitiveRoot

Source

struct IndexCalculusWithPrimitiveRoot {
    p: u64,
    ord: u64,
    prec: QdrtPowPrec,
    coeff: Vec<u64>,
}

Fields§

§p: u64§ord: u64§prec: QdrtPowPrec§coeff: Vec<u64>

Implementations§

Source §

impl IndexCalculusWithPrimitiveRoot

Source

fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self

Examples found in repository ?

crates/competitive/src/math/discrete_logarithm.rs (line 79)

67    fn discrete_logarithm(&mut self, a: u64, b: u64, p: u64) -> Option<(u64, u64)> {
68        let lim = ((((p as f64).log2() * (p as f64).log2().log2()).sqrt() / 2.0 + 1.).exp2() * 0.9)
69            as u64;
70        self.primes.reserve(lim);
71        let primes = self.primes.primes_lte(lim);
72        while self.br_primes.len() < primes.len() {
73            let br = BarrettReduction::<u64>::new(primes[self.br_primes.len()]);
74            self.br_primes.push(br);
75        }
76        let br_primes = &self.br_primes[..primes.len()];
77        self.ic
78            .entry(p)
79            .or_insert_with(|| IndexCalculusWithPrimitiveRoot::new(p, br_primes))
80            .discrete_logarithm(a, b, br_primes)
81    }

Source

fn index_calculus( &self, a: u64, br_primes: &[BarrettReduction<u64>], ) -> Option<u64>

Examples found in repository ?

crates/competitive/src/math/discrete_logarithm.rs (line 331)

313    fn discrete_logarithm(
314        &self,
315        a: u64,
316        b: u64,
317        br_primes: &[BarrettReduction<u64>],
318    ) -> Option<(u64, u64)> {
319        let p = self.p;
320        let ord = self.ord;
321        let br = BarrettReduction::<u128>::new(p as u128);
322        let a = br.rem(a as _) as u64;
323        let b = br.rem(b as _) as u64;
324        if a == 0 {
325            return if b == 0 { Some((1, 1)) } else { None };
326        }
327        if b == 0 {
328            return None;
329        }
330
331        let x = self.index_calculus(a, br_primes)?;
332        let y = self.index_calculus(b, br_primes)?;
333        solve_linear_congruence(x, y, ord)
334    }

Source

fn discrete_logarithm( &self, a: u64, b: u64, br_primes: &[BarrettReduction<u64>], ) -> Option<(u64, u64)>

Examples found in repository ?

crates/competitive/src/math/discrete_logarithm.rs (line 80)

67    fn discrete_logarithm(&mut self, a: u64, b: u64, p: u64) -> Option<(u64, u64)> {
68        let lim = ((((p as f64).log2() * (p as f64).log2().log2()).sqrt() / 2.0 + 1.).exp2() * 0.9)
69            as u64;
70        self.primes.reserve(lim);
71        let primes = self.primes.primes_lte(lim);
72        while self.br_primes.len() < primes.len() {
73            let br = BarrettReduction::<u64>::new(primes[self.br_primes.len()]);
74            self.br_primes.push(br);
75        }
76        let br_primes = &self.br_primes[..primes.len()];
77        self.ic
78            .entry(p)
79            .or_insert_with(|| IndexCalculusWithPrimitiveRoot::new(p, br_primes))
80            .discrete_logarithm(a, b, br_primes)
81    }