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 81)

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 u32;
70        self.primes.reserve(lim);
71        let prime_count = self.primes.primes_lte(lim).count();
72        self.br_primes.extend(
73            self.primes
74                .primes_lte(lim)
75                .skip(self.br_primes.len())
76                .map(|p| BarrettReduction::<u64>::new(p.into())),
77        );
78        let br_primes = &self.br_primes[..prime_count];
79        self.ic
80            .entry(p)
81            .or_insert_with(|| IndexCalculusWithPrimitiveRoot::new(p, br_primes))
82            .discrete_logarithm(a, b, br_primes)
83    }

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 333)

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

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 82)

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 u32;
70        self.primes.reserve(lim);
71        let prime_count = self.primes.primes_lte(lim).count();
72        self.br_primes.extend(
73            self.primes
74                .primes_lte(lim)
75                .skip(self.br_primes.len())
76                .map(|p| BarrettReduction::<u64>::new(p.into())),
77        );
78        let br_primes = &self.br_primes[..prime_count];
79        self.ic
80            .entry(p)
81            .or_insert_with(|| IndexCalculusWithPrimitiveRoot::new(p, br_primes))
82            .discrete_logarithm(a, b, br_primes)
83    }