#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
#[derive(Clone, Copy, Debug)]
pub struct Md {
pub p: u64,
r: u64,
}
impl Md {
pub fn new(p: u64) -> Self {
assert!(p < (1 << 31), "the modulus must fit 31 bits");
assert!(
is_prime(p),
"the modulus must be prime: Fermat inversion is silently wrong mod {p}"
);
Md {
p,
r: ((1u128 << 62) / p as u128) as u64,
}
}
#[inline]
pub fn red(&self, x: u64) -> u64 {
debug_assert!(x < 1 << 62);
let q = ((x as u128 * self.r as u128) >> 62) as u64;
let mut v = x - q * self.p;
while v >= self.p {
v -= self.p;
}
v
}
#[inline]
pub fn mul(&self, a: u64, b: u64) -> u64 {
self.red(a * b)
}
#[inline]
pub fn add(&self, a: u64, b: u64) -> u64 {
let s = a + b;
if s >= self.p {
s - self.p
} else {
s
}
}
#[inline]
pub fn sub(&self, a: u64, b: u64) -> u64 {
if a >= b {
a - b
} else {
a + self.p - b
}
}
pub fn pow(&self, mut a: u64, mut e: u64) -> u64 {
let mut r = 1u64;
while e > 0 {
if e & 1 == 1 {
r = self.mul(r, a);
}
a = self.mul(a, a);
e >>= 1;
}
r
}
pub fn inv(&self, a: u64) -> u64 {
assert!(a != 0, "inverse of zero mod {}", self.p);
self.pow(a, self.p - 2)
}
#[allow(clippy::wrong_self_convention)]
#[inline]
pub fn from_i128(&self, v: i128) -> u64 {
v.rem_euclid(self.p as i128) as u64
}
#[allow(clippy::wrong_self_convention)]
#[inline]
pub fn from_u128(&self, v: u128) -> u64 {
(v % self.p as u128) as u64
}
}
#[inline]
pub fn mul(a: u64, b: u64, p: Md) -> u64 {
p.mul(a, b)
}
#[inline]
pub fn add(a: u64, b: u64, p: Md) -> u64 {
p.add(a, b)
}
#[inline]
pub fn sub(a: u64, b: u64, p: Md) -> u64 {
p.sub(a, b)
}
#[inline]
pub fn pow(a: u64, e: u64, p: Md) -> u64 {
p.pow(a, e)
}
#[inline]
pub fn inv(a: u64, p: Md) -> u64 {
p.inv(a)
}
#[inline]
pub fn from_i128(v: i128, p: Md) -> u64 {
p.from_i128(v)
}
pub fn is_prime(n: u64) -> bool {
if n < 2 {
return false;
}
for q in [2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
if n.is_multiple_of(q) {
return n == q;
}
}
let mut d = n - 1;
let mut s = 0;
while d.is_multiple_of(2) {
d /= 2;
s += 1;
}
let mulmod = |a: u64, b: u64| ((a as u128 * b as u128) % n as u128) as u64;
let powmod = |mut a: u64, mut e: u64| {
let mut r = 1u64;
while e > 0 {
if e & 1 == 1 {
r = mulmod(r, a);
}
a = mulmod(a, a);
e >>= 1;
}
r
};
'witness: for a in [2u64, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] {
let mut x = powmod(a, d);
if x == 1 || x == n - 1 {
continue;
}
for _ in 1..s {
x = mulmod(x, x);
if x == n - 1 {
continue 'witness;
}
}
return false;
}
true
}
pub fn prime_below(hi: u64) -> u64 {
let mut n = if hi.is_multiple_of(2) { hi - 1 } else { hi - 2 };
while !is_prime(n) {
n -= 2;
}
n
}
pub fn nth_prime(k: usize) -> Md {
Md::new(prime_below((1u64 << 31) - (k as u64) * (1 << 20)))
}
pub fn reconstruct(x: u128, m: u128, bound: u128) -> Option<(i128, u128)> {
debug_assert!(m < (1u128 << 127), "the modulus must fit a signed i128");
let (mut r0, mut r1) = (m as i128, x as i128);
let (mut t0, mut t1) = (0i128, 1i128);
while r1 > bound as i128 {
if r1 == 0 {
return None;
}
let q = r0 / r1;
let r = r0 - q * r1;
r0 = r1;
r1 = r;
let t = t0 - q * t1;
t0 = t1;
t1 = t;
}
let (mut num, mut den) = (r1, t1);
if den < 0 {
num = -num;
den = -den;
}
if den == 0 || den as u128 > bound {
return None;
}
Some((num, den as u128))
}
pub fn crt(residues: &[u64], primes: &[Md]) -> (u128, u128) {
assert!(
residues.len() == primes.len(),
"crt needs one residue per prime: {} residues against {} primes",
residues.len(),
primes.len()
);
assert!(!residues.is_empty(), "crt needs at least one residue");
let mut x = residues[0] as u128;
let mut m = primes[0].p as u128;
for (&a, &q) in residues.iter().zip(primes.iter()).skip(1) {
let m_mod = q.from_u128(m);
let diff = q.sub(a % q.p, q.from_u128(x));
let k = q.mul(diff, q.inv(m_mod));
x += m * k as u128;
m *= q.p as u128;
}
(x, m)
}
pub fn bound_for(modulus: u128) -> u128 {
isqrt128(modulus / 2)
}
pub fn isqrt128(n: u128) -> u128 {
if n == 0 {
return 0;
}
let mut r = 1u128 << ((128 - n.leading_zeros()).div_ceil(2));
loop {
let next = (r + n / r) / 2;
if next >= r {
break;
}
r = next;
}
r
}
pub fn gcd128(mut a: u128, mut b: u128) -> u128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
}
#[allow(dead_code)]
pub fn interpolate(xs: &[u64], ys: &[u64], p: Md) -> Vec<u64> {
let n = xs.len();
let mut out = vec![0u64; n];
for i in 0..n {
let mut denom = 1u64;
for j in 0..n {
if j != i {
denom = mul(denom, sub(xs[i], xs[j], p), p);
}
}
let scale = mul(ys[i], inv(denom, p), p);
if scale == 0 {
continue;
}
let basis = basis_poly(xs, i, p);
for d in 0..n {
out[d] = add(out[d], mul(basis[d], scale, p), p);
}
}
out
}
fn basis_poly(xs: &[u64], i: usize, p: Md) -> Vec<u64> {
let n = xs.len();
let mut basis = vec![0u64; n];
basis[0] = 1;
let mut deg = 0usize;
for j in 0..n {
if j == i {
continue;
}
for d in (0..=deg).rev() {
let v = basis[d];
basis[d + 1] = add(basis[d + 1], v, p);
basis[d] = mul(v, sub(0, xs[j], p), p);
}
deg += 1;
}
basis
}
#[allow(dead_code)]
pub fn shift_by(coeffs: &[u64], shift: u64, p: Md) -> Vec<u64> {
let n = coeffs.len();
let mut out = vec![0u64; n];
for (k, &c) in coeffs.iter().enumerate() {
if c == 0 {
continue;
}
let mut binom = 1u64;
for j in 0..=k {
let w = mul(binom, pow(shift, (k - j) as u64, p), p);
out[j] = add(out[j], mul(c, w, p), p);
binom = mul(
mul(binom, (k - j) as u64 % p.p, p),
inv((j + 1) as u64 % p.p, p),
p,
);
}
}
out
}
pub fn lagrange_matrix(xs: &[u64], shift: u64, p: Md) -> Vec<Vec<u64>> {
let n = xs.len();
let mut a = vec![vec![0u64; n]; n];
for i in 0..n {
let mut denom = 1u64;
for j in 0..n {
if j != i {
denom = mul(denom, sub(xs[i], xs[j], p), p);
}
}
let scale = inv(denom, p);
let basis = basis_poly(xs, i, p);
for d in 0..n {
a[d][i] = mul(basis[d], scale, p);
}
}
let mut binom = vec![vec![0u64; n]; n];
for d in 0..n {
binom[d][0] = 1;
for j in 1..=d {
binom[d][j] = add(binom[d - 1][j - 1], binom[d - 1][j], p);
}
}
let mut t = vec![vec![0u64; n]; n];
for j in 0..n {
for d in j..n {
let c = mul(binom[d][j], pow(shift, (d - j) as u64, p), p);
if c == 0 {
continue;
}
for i in 0..n {
t[j][i] = add(t[j][i], mul(c, a[d][i], p), p);
}
}
}
t
}
pub fn apply_matrix(t: &[Vec<u64>], ys: &[u64], p: Md) -> Vec<u64> {
t.iter()
.map(|row| {
let mut acc = 0u64;
for (r, y) in row.iter().zip(ys.iter()) {
if *y != 0 {
acc = add(acc, mul(*r, *y, p), p);
}
}
acc
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_primes_are_actually_prime() {
for k in 0..8 {
let q = nth_prime(k).p;
assert!(is_prime(q), "{q} is not prime");
assert!(q < (1 << 31), "{q} does not fit 31 bits");
}
let all: Vec<u64> = (0..8).map(|k| nth_prime(k).p).collect();
for i in 0..all.len() {
for j in i + 1..all.len() {
assert_ne!(all[i], all[j]);
}
}
assert!(!is_prime(3215031751), "a strong pseudoprime to 2,3,5,7");
assert!(!is_prime(1u64 << 40));
assert!(is_prime(2));
}
#[test]
fn barrett_agrees_with_division() {
for k in 0..4 {
let p = nth_prime(k);
for x in [0u64, 1, p.p - 1, p.p, p.p + 1, (1 << 62) - 1] {
assert_eq!(p.red(x), x % p.p, "red({x}) mod {}", p.p);
}
for &(a, b) in &[(0u64, 0u64), (1, 1), (p.p - 1, p.p - 1), (p.p - 1, 2)] {
assert_eq!(p.mul(a, b), (a as u128 * b as u128 % p.p as u128) as u64);
}
}
}
#[test]
fn rational_reconstruction_round_trips() {
let primes: Vec<Md> = (0..3).map(nth_prime).collect();
let m: u128 = primes.iter().map(|q| q.p as u128).product();
let bound = bound_for(m);
assert!(bound > (1u128 << 45), "three primes must buy a 2^46 bound");
for &(num, den) in &[
(1i128, 1u128),
(-7, 1),
(3, 4),
(123456, 7),
(-99991, 65537),
(1234567890123, 1),
(-12345678901234, 1000003),
] {
assert!(num.unsigned_abs() <= bound && den <= bound);
let residues: Vec<u64> = primes
.iter()
.map(|q| q.mul(q.from_i128(num), q.inv(q.from_u128(den))))
.collect();
let (x, mm) = crt(&residues, &primes);
assert_eq!(mm, m);
assert_eq!(reconstruct(x, m, bound), Some((num, den)), "{num}/{den}");
}
let (num, den) = (-98765432109876i128, 1000003u128);
assert!(num.unsigned_abs() > bound);
let residues: Vec<u64> = primes
.iter()
.map(|q| q.mul(q.from_i128(num), q.inv(q.from_u128(den))))
.collect();
let (x, _) = crt(&residues, &primes);
assert_ne!(reconstruct(x, m, bound), Some((num, den)));
}
#[test]
#[should_panic(expected = "the modulus must be prime")]
fn a_composite_modulus_is_refused_at_construction() {
Md::new(15);
}
#[test]
#[should_panic(expected = "one residue per prime")]
fn crt_refuses_a_residue_list_shorter_than_the_primes() {
let primes: Vec<Md> = (0..3).map(nth_prime).collect();
crt(&[1, 2], &primes);
}
#[test]
fn crt_combines_residues() {
let primes: Vec<Md> = (0..3).map(nth_prime).collect();
for v in [0u128, 1, 42, 1u128 << 90, 123456789012345678901234567890] {
let residues: Vec<u64> = primes.iter().map(|q| q.from_u128(v)).collect();
let (x, m) = crt(&residues, &primes);
for q in &primes {
assert_eq!(x % q.p as u128, v % q.p as u128, "mod {}", q.p);
}
assert_eq!(x % m, v % m);
}
}
#[test]
fn interpolation_recovers_a_known_polynomial() {
let p = nth_prime(0);
let f = |x: u64| -> u64 {
let x = x as i128;
p.from_i128(5 - 3 * x + 2 * x * x * x)
};
let xs: Vec<u64> = (1..=6).collect();
let ys: Vec<u64> = xs.iter().map(|&x| f(x)).collect();
let got = interpolate(&xs, &ys, p);
let want = [5i128, -3, 0, 2, 0, 0].map(|c| p.from_i128(c));
assert_eq!(got, want.to_vec());
}
#[test]
fn the_matrix_composes_interpolation_with_the_shift() {
let p = nth_prime(1);
let xs: Vec<u64> = (1..=7).collect();
for shift in [0u64, 1, 5] {
let t = lagrange_matrix(&xs, shift, p);
for seed in [1i128, 2, 3] {
let ys: Vec<u64> = xs
.iter()
.map(|&x| p.from_i128(seed * (x as i128) * (x as i128) + 4 * x as i128 - 1))
.collect();
let direct = shift_by(&interpolate(&xs, &ys, p), shift, p);
assert_eq!(apply_matrix(&t, &ys, p), direct, "shift {shift}");
}
}
}
#[test]
fn the_shift_by_one_sends_alpha_to_one_plus_b() {
let p = nth_prime(0);
let got = shift_by(&[0, 0, 1], 1, p);
assert_eq!(got, vec![1, 2, 1]);
assert_eq!(shift_by(&[7, 0, 0], 1, p), vec![7, 0, 0]);
}
}