Struct QdrtPowPrec 

struct QdrtPowPrec {
    br_qdrt: BarrettReduction<u64>,
    p0: Vec<u64>,
    p1: Vec<u64>,
    p2: Vec<u64>,
    p3: Vec<u64>,
}

Fields

br_qdrt: BarrettReduction<u64>

p0: Vec<u64>

p1: Vec<u64>

p2: Vec<u64>

p3: Vec<u64>

Implementations

impl QdrtPowPrec

fn new(a: u64, ord: u64, br: &BarrettReduction<u128>) -> Self

Examples found in repository

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

    fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self {
        let ord = p - 1;
        let g = primitive_root(p);
        let br = BarrettReduction::<u128>::new(p as u128);
        let prec = QdrtPowPrec::new(g, ord, &br);
        let coeff = index_calculus_for_primitive_root(p, ord, br_primes, &prec);
        Self {
            p,
            ord,
            prec,
            coeff,
        }
    }

fn pow(&self, k: u64, br: &BarrettReduction<u128>) -> u64

Examples found in repository

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

fn index_calculus_for_primitive_root(
    p: u64,
    ord: u64,
    br_primes: &[BarrettReduction<u64>],
    prec: &QdrtPowPrec,
) -> Vec<u64> {
    let br_ord = BarrettReduction::<u128>::new(ord as u128);
    let mul = |x: u64, y: u64| br_ord.rem(x as u128 * y as u128) as u64;
    let sub = |x: u64, y: u64| if x < y { x + ord - y } else { x - y };

    let pc = br_primes.len();
    let mut mat: Vec<Vec<u64>> = vec![];
    let mut rows: Vec<Vec<u64>> = vec![];

    let mut rng = Xorshift::default();
    let br = BarrettReduction::<u128>::new(p as u128);

    for i in 0..pc {
        for ri in 0usize.. {
            let mut row = vec![0u64; pc + 1];
            let mut kk = rng.rand(ord - 1) + 1;
            let mut gkk = prec.pow(kk, &br);
            let mut k = kk;
            let mut gk = gkk;
            while ri >= rows.len() {
                row[pc] = k;
                if factorize_smooth(gk, &mut row, br_primes) {
                    rows.push(row);
                    break;
                }
                if k + kk < ord {
                    k += kk;
                    gk = br.rem(gk as u128 * gkk as u128) as u64;
                } else {
                    kk = rng.rand(ord - 1) + 1;
                    gkk = prec.pow(kk, &br);
                    k = kk;
                    gk = gkk;
                }
            }
            let row = &mut rows[ri];
            for j in 0..i {
                if row[j] != 0 {
                    let b = mul(modinv(mat[j][j], ord), row[j]);
                    for (r, a) in row[j..].iter_mut().zip(&mat[j][j..]) {
                        *r = sub(*r, mul(*a, b));
                    }
                }
                assert_eq!(row[j], 0);
            }
            if gcd(row[i], ord) == 1 {
                let last = rows.len() - 1;
                rows.swap(ri, last);
                mat.push(rows.pop().unwrap());
                break;
            }
        }
    }
    for i in (0..pc).rev() {
        for j in i + 1..pc {
            mat[i][pc] = sub(mat[i][pc], mul(mat[i][j], mat[j][pc]));
        }
        mat[i][pc] = mul(mat[i][pc], modinv(mat[i][i], ord));
    }
    (0..pc).map(|i| mat[i][pc]).collect()
}

#[derive(Debug)]
struct IndexCalculusWithPrimitiveRoot {
    p: u64,
    ord: u64,
    prec: QdrtPowPrec,
    coeff: Vec<u64>,
}

impl IndexCalculusWithPrimitiveRoot {
    fn new(p: u64, br_primes: &[BarrettReduction<u64>]) -> Self {
        let ord = p - 1;
        let g = primitive_root(p);
        let br = BarrettReduction::<u128>::new(p as u128);
        let prec = QdrtPowPrec::new(g, ord, &br);
        let coeff = index_calculus_for_primitive_root(p, ord, br_primes, &prec);
        Self {
            p,
            ord,
            prec,
            coeff,
        }
    }
    fn index_calculus(&self, a: u64, br_primes: &[BarrettReduction<u64>]) -> Option<u64> {
        let p = self.p;
        let ord = self.ord;
        let br = BarrettReduction::<u128>::new(p as u128);
        let a = br.rem(a as _) as u64;
        if a == 1 {
            return Some(0);
        }
        if p == 2 {
            return None;
        }

        let mut rng = Xorshift::new();
        let mut row = vec![0u64; br_primes.len()];
        let mut kk = rng.rand(ord - 1) + 1;
        let mut gkk = self.prec.pow(kk, &br);
        let mut k = kk;
        let mut gk = br.rem(gkk as u128 * a as u128) as u64;
        loop {
            if factorize_smooth(gk, &mut row, br_primes) {
                let mut res = ord - k;
                for (&c, &r) in self.coeff.iter().zip(&row) {
                    for _ in 0..r {
                        res += c;
                        if res >= ord {
                            res -= ord;
                        }
                    }
                }
                return Some(res);
            }
            if k + kk < ord {
                k += kk;
                gk = br.rem(gk as u128 * gkk as u128) as u64;
            } else {
                kk = rng.rand(ord - 1) + 1;
                gkk = self.prec.pow(kk, &br);
                k = kk;
                gk = br.rem(gkk as u128 * a as u128) as u64;
            }
        }
    }

Trait Implementations

impl Debug for QdrtPowPrec

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.