adele_ring/
reconstruct.rs

1//! Rational reconstruction — turns the original engine's worst failure mode
2//! (silent aliasing mod `M`) into a clean, checkable event.
3//!
4//! Given a residue `x = value mod M`, recover the unique reduced `p/q` with
5//! `|p|, |q| <= sqrt(M/2)` such that `p ≡ q·x (mod M)`. When no such fraction
6//! exists within the bound, the basis was too small: the caller extends it and
7//! retries (see [`crate::basis::Basis::extend_to_bits`]).
8
9use num_bigint::{BigInt, BigUint, Sign};
10use num_integer::Integer;
11use num_traits::{One, Signed, Zero};
12
13/// Balanced (symmetric) lift of `x mod m` into `(-m/2, m/2]`.
14pub fn balanced_lift(x: &BigUint, m: &BigUint) -> BigInt {
15    let x = BigInt::from(x.clone());
16    let m_big = BigInt::from(m.clone());
17    if &x * 2 > m_big {
18        x - BigInt::from(m.clone())
19    } else {
20        x
21    }
22}
23
24/// Recover the unique reduced `p/q` with `|p|, |q| <= sqrt(M/2)` and
25/// `p ≡ q·x (mod M)`, or `None` if none exists within the bound.
26pub fn rational_reconstruct(x: &BigUint, m: &BigUint) -> Option<(BigInt, BigInt)> {
27    if m.is_zero() {
28        return None;
29    }
30    let x = x % m;
31    if x.is_zero() {
32        return Some((BigInt::zero(), BigInt::one()));
33    }
34
35    // Bound N = floor(sqrt(M/2)).
36    let bound = BigInt::from((m / 2u32).sqrt());
37
38    let m_big = BigInt::from(m.clone());
39    let x_big = BigInt::from(x);
40
41    // Extended Euclid on (m, x), tracking only the `t` coefficients.
42    let mut r0 = m_big.clone();
43    let mut r1 = x_big.clone();
44    let mut t0 = BigInt::zero();
45    let mut t1 = BigInt::one();
46
47    while r1 > bound {
48        let q = &r0 / &r1;
49        let r2 = &r0 - &q * &r1;
50        r0 = r1;
51        r1 = r2;
52        let t2 = &t0 - &q * &t1;
53        t0 = t1;
54        t1 = t2;
55    }
56
57    // Candidate fraction p/q = r1 / t1.
58    let mut p = r1;
59    let mut q = t1;
60    if q.is_zero() {
61        return None;
62    }
63    if q.sign() == Sign::Minus {
64        p = -p;
65        q = -q;
66    }
67
68    // Validate: denominator within bound, reduced, and congruence holds.
69    if q.abs() > bound || p.abs() > bound {
70        return None;
71    }
72    if p.gcd(&q) != BigInt::one() {
73        return None;
74    }
75    let check = (&p - &q * &x_big).mod_floor(&m_big);
76    if !check.is_zero() {
77        return None;
78    }
79    Some((p, q))
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    fn encode(p: i64, q: i64, m: &BigUint) -> BigUint {
87        // x = p * q^{-1} mod m
88        let m_big = BigInt::from(m.clone());
89        let qi = BigInt::from(q);
90        let inv = mod_inverse_big(&qi, &m_big).unwrap();
91        let x = (BigInt::from(p) * inv).mod_floor(&m_big);
92        x.to_biguint().unwrap()
93    }
94
95    fn mod_inverse_big(a: &BigInt, m: &BigInt) -> Option<BigInt> {
96        let g = a.extended_gcd(m);
97        if g.gcd != BigInt::one() {
98            return None;
99        }
100        Some(g.x.mod_floor(m))
101    }
102
103    #[test]
104    fn round_trip() {
105        let m = BigUint::from(1u32) << 64;
106        let x = encode(3, 7, &m);
107        assert_eq!(rational_reconstruct(&x, &m), Some((BigInt::from(3), BigInt::from(7))));
108        let x = encode(-5, 11, &m);
109        assert_eq!(rational_reconstruct(&x, &m), Some((BigInt::from(-5), BigInt::from(11))));
110    }
111
112    #[test]
113    fn integer_round_trip() {
114        let m = BigUint::from(1u32) << 64;
115        let x = BigUint::from(42u32);
116        assert_eq!(rational_reconstruct(&x, &m), Some((BigInt::from(42), BigInt::one())));
117    }
118
119    #[test]
120    fn out_of_range_fails() {
121        // m too small for p/q with 2*max(|p|,|q|)^2 < M
122        let m = BigUint::from(50u32);
123        let x = encode(7, 9, &m); // 2*81 = 162 > 50 → not reconstructible
124        assert_eq!(rational_reconstruct(&x, &m), None);
125    }
126}
adele_ring/reconstruct.rs

adele_ring/
reconstruct.rs
