1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// Copyright © 2026 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
use crate::integer::Integer;
use crate::natural::Natural;
use malachite_base::num::arithmetic::traits::{
AddMul, Crt, ExtendedGcd, Mod, ModMul, ModSub, UnsignedAbs,
};
// A simple reference implementation of `Crt`, computing the inverse through the public
// `ExtendedGcd` rather than the FLINT-derived kernels. The CRT solution is unique, so any algorithm
// agrees with any other.
pub fn crt_simple(r1: Natural, m1: Natural, r2: Natural, m2: Natural) -> Option<Natural> {
assert!(r1 < m1);
assert!(r2 < m2);
let (g, a, _) = (&m1).extended_gcd(&m2);
if g != 1u32 {
return None;
}
// a * m1 + b * m2 = 1, so a is an inverse of m1 modulo m2; lift it to [0, m2).
let inv = a.mod_op(Integer::from(&m2)).unsigned_abs();
let s = r2.mod_sub(&r1 % &m2, &m2).mod_mul(inv, m2);
Some(r1.add_mul(m1, s))
}
// A simple reference implementation of multi-modulus Chinese remaindering: a left fold of the pair
// combination `crt`. It diverges from `MultiCrt` on lists that contain a 1 among two or more
// moduli: the pair combination treats a modulus of 1 as a vacuous congruence, while `MultiCrt::new`
// rejects it. Callers should avoid such lists.
pub fn multi_crt_simple(moduli: &[Natural], values: &[Natural]) -> Option<Natural> {
assert_eq!(moduli.len(), values.len());
if moduli[0] == 0u32 {
return None;
}
let mut x = values[0].clone();
let mut m = moduli[0].clone();
for (mi, v) in moduli.iter().zip(values.iter()).skip(1) {
x = (&x).crt(&m, v, mi)?;
m *= mi;
}
Some(x)
}