Skip to main content

logicaffeine_proof/
modm.rs

1//! Linear algebra over `ℤ/m` for **composite** `m`, by the Chinese Remainder Theorem — the
2//! multiplicative symmetry break. A system `Σ aᵢ·xᵢ ≡ c (mod m)` over a **squarefree** modulus
3//! `m = p₁·…·p_t` factors, through the ring isomorphism `ℤ/m ≅ GF(p₁) × … × GF(p_t)`, into one
4//! independent system over each prime field — each decided by [`crate::modp::solve`] — and the
5//! per-field solutions are recombined by CRT. The *factorization of the modulus* is the symmetry that
6//! splits the problem; the prime fields are the irreducible pieces:
7//!
8//! - **consistent mod `m`  ⟺  consistent over every prime factor `pᵢ`**, and the recombined residues
9//!   give an assignment over `ℤ/m` that re-checks ([`satisfies`]);
10//! - **inconsistent mod `m`  ⟺  some prime factor's system is inconsistent**, and that prime together
11//!   with its GF(p) refutation combination is the re-checkable witness ([`crate::modp::is_refutation`]).
12//!
13//! This is [`crate::modp`] (the prime-field cut, itself the prime generalization of the GF(2) parity
14//! cut) carried up onto the composites by multiplication. Prime-power moduli `p^k` need the residue
15//! *ring* `ℤ/p^k` (a different object — `p` is a zero divisor), a separate rung; this module is exact
16//! and complete for squarefree `m`.
17
18use crate::modp::{self, ModpEquation, ModpOutcome};
19
20fn gcd_i128(a: i128, b: i128) -> i128 {
21    let (mut a, mut b) = (a.abs(), b.abs());
22    while b != 0 {
23        let t = a % b;
24        a = b;
25        b = t;
26    }
27    a
28}
29
30/// Extended Euclid: `(g, x, y)` with `a·x + b·y = g = gcd(a,b)`.
31fn egcd(a: i128, b: i128) -> (i128, i128, i128) {
32    if b == 0 {
33        (a, 1, 0)
34    } else {
35        let (g, x, y) = egcd(b, a % b);
36        (g, y, x - (a / b) * y)
37    }
38}
39
40/// Inverse of `a` mod `n` (n need not be prime), assuming `gcd(a, n) = 1`; result in `0..n`.
41fn modinv(a: i128, n: i128) -> i128 {
42    let (_, x, _) = egcd(a.rem_euclid(n), n);
43    x.rem_euclid(n)
44}
45
46/// The distinct prime factors of `m`, in increasing order — or `None` if `m < 2` or `m` is not
47/// squarefree (some `p² | m`). Squarefreeness is exactly the condition under which `ℤ/m` is a product
48/// of fields, so the CRT-over-prime-fields decision procedure below is complete.
49pub fn squarefree_primes(m: u64) -> Option<Vec<u64>> {
50    if m < 2 {
51        return None;
52    }
53    let mut primes = Vec::new();
54    let mut x = m;
55    let mut d = 2u64;
56    while d * d <= x {
57        if x % d == 0 {
58            x /= d;
59            if x % d == 0 {
60                return None; // p² | m ⇒ ℤ/m is not a product of fields
61            }
62            primes.push(d);
63        }
64        d += 1;
65    }
66    if x > 1 {
67        primes.push(x);
68    }
69    Some(primes)
70}
71
72/// The outcome of deciding a linear system over `ℤ/m`.
73#[derive(Clone, Debug, PartialEq, Eq)]
74pub enum ModmOutcome {
75    /// Satisfiable, with an assignment over `0..m` for each variable (re-checkable via [`satisfies`]).
76    Sat(Vec<u64>),
77    /// Unsatisfiable: inconsistent already over the quotient ring `ℤ/modulus` for a prime-power factor
78    /// `modulus = pᵏ` of `m` (a prime field when `k = 1`), witnessed by a combination of the equations
79    /// whose left side cancels mod `modulus` while the right side does not. Because `modulus | m`, any
80    /// solution mod `m` would reduce to one mod `modulus`, so this certifies UNSAT mod `m`. Re-checkable
81    /// via [`is_refutation`].
82    Unsat {
83        modulus: u64,
84        combo: Vec<(usize, u64)>,
85    },
86}
87
88/// Re-check a refutation over `ℤ/modulus`: the chosen combination of equations has every variable
89/// coefficient `≡ 0` and a nonzero right-hand side mod `modulus` — a solver-free certificate that the
90/// system is inconsistent over that quotient ring (and hence over any `ℤ/m` with `modulus | m`).
91pub fn is_refutation(
92    equations: &[ModpEquation],
93    num_vars: usize,
94    modulus: u64,
95    combo: &[(usize, u64)],
96) -> bool {
97    if combo.is_empty() {
98        return false;
99    }
100    let mm = modulus as u128;
101    let mut lhs = vec![0u128; num_vars];
102    let mut rhs = 0u128;
103    for &(idx, mult) in combo {
104        let Some(eq) = equations.get(idx) else {
105            return false;
106        };
107        for &(v, a) in &eq.coeffs {
108            if v < num_vars {
109                lhs[v] = (lhs[v] + mult as u128 * a as u128) % mm;
110            }
111        }
112        rhs = (rhs + mult as u128 * eq.rhs as u128) % mm;
113    }
114    lhs.iter().all(|&x| x == 0) && rhs != 0
115}
116
117/// Decide a linear system over `ℤ/m` for **squarefree** `m`, via CRT over the prime fields. Returns
118/// `None` only when `m` is not squarefree (the prime-power ring is a separate rung). The first prime
119/// factor whose system is inconsistent is reported as the witness — by CRT, the whole composite system
120/// is then inconsistent.
121pub fn solve_squarefree(
122    equations: &[ModpEquation],
123    num_vars: usize,
124    m: u64,
125) -> Option<ModmOutcome> {
126    let primes = squarefree_primes(m)?;
127    let mut per_prime: Vec<(u64, Vec<u64>)> = Vec::with_capacity(primes.len());
128    for &p in &primes {
129        match modp::solve(equations, num_vars, p) {
130            ModpOutcome::Sat(a) => per_prime.push((p, a)),
131            ModpOutcome::Unsat(combo) => return Some(ModmOutcome::Unsat { modulus: p, combo }),
132        }
133    }
134    // Every prime field is consistent: recombine each variable's residues into a value mod m by CRT.
135    let mut assignment = vec![0u64; num_vars];
136    for (i, slot) in assignment.iter_mut().enumerate() {
137        let residues: Vec<(u64, u64)> = per_prime.iter().map(|(p, a)| (a[i], *p)).collect();
138        *slot = crt(&residues);
139    }
140    Some(ModmOutcome::Sat(assignment))
141}
142
143/// Combine residues `(rᵢ mod mᵢ)` with pairwise-coprime moduli (primes or prime powers) into the unique
144/// value mod `∏ mᵢ`, by incremental CRT: `x ≡ acc (mod M)` and `x ≡ r (mod mᵢ)` ⟹
145/// `x = acc + M·((r−acc)·M⁻¹ mod mᵢ)`.
146fn crt(residues: &[(u64, u64)]) -> u64 {
147    let mut acc_r = 0i128;
148    let mut acc_m = 1i128;
149    for &(r, modu) in residues {
150        let modu = modu as i128;
151        let diff = (r as i128 - acc_r).rem_euclid(modu);
152        let t = (diff * modinv(acc_m.rem_euclid(modu), modu)).rem_euclid(modu);
153        acc_r += acc_m * t;
154        acc_m *= modu;
155        acc_r = acc_r.rem_euclid(acc_m);
156    }
157    acc_r as u64
158}
159
160/// The forced-value structure of a `ℤ/m` system over a **squarefree** `m`.
161pub enum ForcedM {
162    /// Inconsistent over `ℤ/m` (UNSAT) — some prime field is inconsistent.
163    Inconsistent,
164    /// `forced[g] = Some(v)` iff `x_g ≡ v (mod m)` in *every* solution, else `None`.
165    Forced(Vec<Option<u64>>),
166}
167
168/// Which variables a **squarefree** `ℤ/m` system forces to a single value, by CRT of the `GF(pᵢ)` solution
169/// spaces (`ℤ/m ≅ ∏ GF(pᵢ)`): a variable is forced mod `m` iff it is forced mod *every* prime factor
170/// ([`crate::modp::solve_space`] — its kernel never moves it), and the value is the CRT of those residues.
171/// `None` if `m` is not squarefree (the prime-power case needs Smith normal form, not handled here). This
172/// is the substrate of the composite affine SAT-side break.
173pub fn forced_values_squarefree(
174    equations: &[ModpEquation],
175    num_vars: usize,
176    m: u64,
177) -> Option<ForcedM> {
178    let primes = squarefree_primes(m)?;
179    let mut per_prime: Vec<(u64, Vec<Option<u64>>)> = Vec::with_capacity(primes.len());
180    for &p in &primes {
181        let Some(ss) = crate::modp::solve_space(equations, num_vars, p) else {
182            return Some(ForcedM::Inconsistent);
183        };
184        let forced_p: Vec<Option<u64>> = (0..num_vars)
185            .map(|g| {
186                ss.kernel_basis
187                    .iter()
188                    .all(|k| k[g] == 0)
189                    .then(|| ss.particular[g])
190            })
191            .collect();
192        per_prime.push((p, forced_p));
193    }
194    let forced: Vec<Option<u64>> = (0..num_vars)
195        .map(|g| {
196            let residues: Option<Vec<(u64, u64)>> = per_prime
197                .iter()
198                .map(|(p, f)| f[g].map(|v| (v, *p)))
199                .collect();
200            residues.map(|res| crt(&res))
201        })
202        .collect();
203    Some(ForcedM::Forced(forced))
204}
205
206/// The complete solution space of a `ℤ/pᵏ` linear system, in symmetry-broken form: a particular solution
207/// plus a generating set of the kernel **submodule** (each generator is a column of the Smith transform
208/// `V` scaled by its pivot's freedom `q/gcd(dₜ,q)`). The prime-power analogue of
209/// [`crate::modp::SolutionSpaceP`] over a local ring — and the substrate of the *scalable* forced/linked
210/// break: a variable the kernel never moves is forced.
211pub struct SolutionSpaceM {
212    pub num_vars: usize,
213    pub m: u64,
214    pub particular: Vec<u64>,
215    pub kernel_basis: Vec<Vec<u64>>,
216}
217
218/// The outcome of [`solve_space_prime_power`].
219pub enum PrimePowerSpace {
220    Inconsistent,
221    Space(SolutionSpaceM),
222}
223
224/// Solve a `ℤ/pᵏ` system for its full solution **space** via Smith normal form `U·A·V = D` — the scalable
225/// analogue of [`crate::modp::solve_space`] over a prime-power ring (where `p` is a zero-divisor, so field
226/// Gaussian fails). Returns the particular solution plus the kernel generators (so a variable the kernel
227/// never moves is forced), or `Inconsistent`. `None` only when the integer Smith reduction overflows
228/// `GROWTH_CAP`. `k = 1` delegates to the prime-field solver.
229pub fn solve_space_prime_power(
230    equations: &[ModpEquation],
231    num_vars: usize,
232    p: u64,
233    k: u32,
234) -> Option<PrimePowerSpace> {
235    if k == 1 {
236        return Some(match crate::modp::solve_space(equations, num_vars, p) {
237            None => PrimePowerSpace::Inconsistent,
238            Some(ss) => PrimePowerSpace::Space(SolutionSpaceM {
239                num_vars,
240                m: p,
241                particular: ss.particular,
242                kernel_basis: ss.kernel_basis,
243            }),
244        });
245    }
246    let q = (p as i128).pow(k);
247    let (m, n) = (equations.len(), num_vars);
248    let mut a = vec![vec![0i128; n]; m];
249    let mut b = vec![0i128; m];
250    let mut u = vec![vec![0i128; m]; m];
251    let mut v = vec![vec![0i128; n]; n];
252    for (i, ui) in u.iter_mut().enumerate() {
253        ui[i] = 1;
254    }
255    for (j, vj) in v.iter_mut().enumerate() {
256        vj[j] = 1;
257    }
258    for (i, eq) in equations.iter().enumerate() {
259        for &(var, coef) in &eq.coeffs {
260            if var < n {
261                a[i][var] = (a[i][var] + coef as i128).rem_euclid(q);
262            }
263        }
264        b[i] = (eq.rhs as i128).rem_euclid(q);
265    }
266    let exceeds = |a: &[Vec<i128>], u: &[Vec<i128>], v: &[Vec<i128>]| {
267        a.iter()
268            .chain(u)
269            .chain(v)
270            .any(|r| r.iter().any(|&x| x.abs() > GROWTH_CAP))
271    };
272    let mut rank = 0usize;
273    for t in 0..m.min(n) {
274        loop {
275            let mut best: Option<(usize, usize, i128)> = None;
276            for (i, row) in a.iter().enumerate().skip(t) {
277                for (j, &val) in row.iter().enumerate().skip(t) {
278                    if val != 0 && best.is_none_or(|(_, _, bv)| val.abs() < bv) {
279                        best = Some((i, j, val.abs()));
280                    }
281                }
282            }
283            let Some((pi, pj, _)) = best else { break };
284            if pi != t {
285                a.swap(pi, t);
286                u.swap(pi, t);
287            }
288            if pj != t {
289                for row in a.iter_mut() {
290                    row.swap(pj, t);
291                }
292                for row in v.iter_mut() {
293                    row.swap(pj, t);
294                }
295            }
296            let piv = a[t][t];
297            for i in 0..m {
298                if i != t && a[i][t] != 0 {
299                    let f = a[i][t].div_euclid(piv);
300                    if f != 0 {
301                        for j in 0..n {
302                            a[i][j] -= f * a[t][j];
303                        }
304                        for j in 0..m {
305                            u[i][j] -= f * u[t][j];
306                        }
307                    }
308                }
309            }
310            for j in 0..n {
311                if j != t && a[t][j] != 0 {
312                    let f = a[t][j].div_euclid(piv);
313                    if f != 0 {
314                        for row in a.iter_mut() {
315                            row[j] -= f * row[t];
316                        }
317                        for row in v.iter_mut() {
318                            row[j] -= f * row[t];
319                        }
320                    }
321                }
322            }
323            if exceeds(&a, &u, &v) {
324                return None;
325            }
326            if (0..m).all(|i| i == t || a[i][t] == 0) && (0..n).all(|j| j == t || a[t][j] == 0) {
327                break;
328            }
329        }
330        if a[t][t] != 0 {
331            rank = t + 1;
332        } else {
333            break;
334        }
335    }
336    let ub: Vec<i128> = (0..m)
337        .map(|i| {
338            (0..m)
339                .fold(0i128, |acc, r| acc + u[i][r] * b[r])
340                .rem_euclid(q)
341        })
342        .collect();
343
344    // Solve D·y ≡ ub for the particular y, recording each coordinate's freedom step hₜ = q/gcd(dₜ,q)
345    // (= q ⇒ forced; < q ⇒ the kernel can move yₜ by hₜ). Free columns (t ≥ rank) move by 1.
346    let mut y = vec![0i128; n];
347    let mut freedom = vec![1i128; n];
348    for t in 0..rank {
349        let d = a[t][t].rem_euclid(q);
350        let g = gcd_i128(d, q);
351        if ub[t].rem_euclid(g) != 0 {
352            return Some(PrimePowerSpace::Inconsistent);
353        }
354        let qg = q / g;
355        y[t] = if qg == 1 {
356            0
357        } else {
358            (ub[t] / g).rem_euclid(qg) * modinv(d / g, qg) % qg
359        };
360        freedom[t] = qg;
361    }
362    for &ubt in ub.iter().skip(rank) {
363        if ubt != 0 {
364            return Some(PrimePowerSpace::Inconsistent); // a zero row with nonzero rhs ⇒ UNSAT
365        }
366    }
367    let particular: Vec<u64> = (0..n)
368        .map(|i| {
369            (0..n)
370                .fold(0i128, |acc, j| acc + v[i][j] * y[j])
371                .rem_euclid(q) as u64
372        })
373        .collect();
374    // Kernel generators: δx = hₜ·(t-th column of V), for every coordinate with genuine freedom (hₜ < q).
375    let mut kernel_basis: Vec<Vec<u64>> = Vec::new();
376    for t in 0..n {
377        if freedom[t] >= q {
378            continue;
379        }
380        let gen: Vec<u64> = (0..n)
381            .map(|i| (v[i][t] * freedom[t]).rem_euclid(q) as u64)
382            .collect();
383        if gen.iter().any(|&x| x != 0) {
384            kernel_basis.push(gen);
385        }
386    }
387    Some(PrimePowerSpace::Space(SolutionSpaceM {
388        num_vars: n,
389        m: q as u64,
390        particular,
391        kernel_basis,
392    }))
393}
394
395/// Which variables a `ℤ/m` system forces, for **any** composite `m` — by CRT over its prime-power
396/// components (`ℤ/m ≅ ∏ ℤ/pᵢ^{kᵢ}`), each solved scalably by Smith normal form
397/// ([`solve_space_prime_power`]): a variable is forced mod `m` iff its kernel never moves it in *every*
398/// component, and the value is the CRT of the residues. This is the Smith-form generalization that
399/// replaces the old bounded brute force — no size cap; `None` only on Smith overflow. `Inconsistent` when
400/// any component is.
401pub fn forced_values_prime_power(
402    equations: &[ModpEquation],
403    num_vars: usize,
404    m: u64,
405) -> Option<ForcedM> {
406    let factors = prime_power_factorize(m)?;
407    let mut per_component: Vec<(u64, Vec<Option<u64>>)> = Vec::with_capacity(factors.len());
408    for (p, k) in factors {
409        match solve_space_prime_power(equations, num_vars, p, k)? {
410            PrimePowerSpace::Inconsistent => return Some(ForcedM::Inconsistent),
411            PrimePowerSpace::Space(ss) => {
412                let forced_c: Vec<Option<u64>> = (0..num_vars)
413                    .map(|g| {
414                        ss.kernel_basis
415                            .iter()
416                            .all(|kk| kk[g] == 0)
417                            .then(|| ss.particular[g])
418                    })
419                    .collect();
420                per_component.push((p.pow(k), forced_c));
421            }
422        }
423    }
424    let forced: Vec<Option<u64>> = (0..num_vars)
425        .map(|g| {
426            let residues: Option<Vec<(u64, u64)>> = per_component
427                .iter()
428                .map(|(q, f)| f[g].map(|v| (v, *q)))
429                .collect();
430            residues.map(|res| crt(&res))
431        })
432        .collect();
433    Some(ForcedM::Forced(forced))
434}
435
436/// The per-variable **allowed-value congruence** of a `ℤ/m` system, for any composite `m`. By CRT over the
437/// prime-power components, each variable's solution-projection is a coset `x_g ≡ residue (mod modulus)` —
438/// the *tightest* congruence the system forces on it. Generalizes forcing: `modulus = m` is a single value
439/// (fully forced), `1 < modulus < m` is **partial** (confined to a value-subset), `modulus = 1` is free.
440/// Within each prime-power component the coset modulus is `gcd(p^k, kernel column at g)` from
441/// [`solve_space_prime_power`]; the components recombine by CRT. `Inconsistent` if any component is.
442pub enum AllowedOutcome {
443    Inconsistent,
444    Allowed(Vec<(u64, u64)>),
445}
446
447/// See [`AllowedOutcome`]. `None` only on Smith overflow.
448pub fn allowed_residues(
449    equations: &[ModpEquation],
450    num_vars: usize,
451    m: u64,
452) -> Option<AllowedOutcome> {
453    let factors = prime_power_factorize(m)?;
454    let mut per_component: Vec<Vec<(u64, u64)>> = Vec::with_capacity(factors.len());
455    for (p, k) in factors {
456        let q = p.pow(k);
457        match solve_space_prime_power(equations, num_vars, p, k)? {
458            PrimePowerSpace::Inconsistent => return Some(AllowedOutcome::Inconsistent),
459            PrimePowerSpace::Space(ss) => {
460                let pv: Vec<(u64, u64)> = (0..num_vars)
461                    .map(|g| {
462                        // The coset modulus in this component: gcd of the ring order with the kernel's
463                        // moves of x_g (an empty kernel ⇒ gcd = q ⇒ fully pinned).
464                        let d = ss
465                            .kernel_basis
466                            .iter()
467                            .fold(q, |acc, kk| gcd_i128(acc as i128, kk[g] as i128) as u64);
468                        (ss.particular[g] % d, d)
469                    })
470                    .collect();
471                per_component.push(pv);
472            }
473        }
474    }
475    let residues: Vec<(u64, u64)> = (0..num_vars)
476        .map(|g| {
477            // CRT the constrained components (their moduli are pairwise-coprime prime powers); a component
478            // that leaves x_g free (modulus 1) contributes nothing.
479            let pairs: Vec<(u64, u64)> = per_component
480                .iter()
481                .map(|pv| pv[g])
482                .filter(|&(_, d)| d > 1)
483                .collect();
484            if pairs.is_empty() {
485                (0, 1)
486            } else {
487                (crt(&pairs), pairs.iter().map(|&(_, d)| d).product())
488            }
489        })
490        .collect();
491    Some(AllowedOutcome::Allowed(residues))
492}
493
494/// Re-check a satisfying assignment over `ℤ/m`: every congruence holds mod `m`.
495pub fn satisfies(equations: &[ModpEquation], assignment: &[u64], m: u64) -> bool {
496    let mm = m as u128;
497    equations.iter().all(|eq| {
498        let lhs = eq.coeffs.iter().fold(0u128, |acc, &(v, a)| {
499            (acc + a as u128 * *assignment.get(v).unwrap_or(&0) as u128) % mm
500        });
501        lhs == (eq.rhs as u128 % mm)
502    })
503}
504
505/// The scalable composite obstruction: the `n`-cycle of differences `xᵢ − x_{i+1} ≡ 1 (mod m)`,
506/// inconsistent **exactly when `m ∤ n`** (summing telescopes the left to `0`, the right to `n`). The
507/// coefficient `−1` is written `m − 1`. Reuses [`crate::modp::cycle_system`]'s shape across the field.
508pub fn cycle_system(n: usize, m: u64) -> Vec<ModpEquation> {
509    modp::cycle_system(n, m)
510}
511
512/// The prime-power factorization of `m` (`m = ∏ pᵢ^{kᵢ}`), or `None` if `m < 2`.
513pub fn prime_power_factorize(m: u64) -> Option<Vec<(u64, u32)>> {
514    if m < 2 {
515        return None;
516    }
517    let mut out = Vec::new();
518    let mut x = m;
519    let mut d = 2u64;
520    while d * d <= x {
521        if x % d == 0 {
522            let mut k = 0u32;
523            while x % d == 0 {
524                x /= d;
525                k += 1;
526            }
527            out.push((d, k));
528        }
529        d += 1;
530    }
531    if x > 1 {
532        out.push((x, 1));
533    }
534    Some(out)
535}
536
537/// Integer-magnitude ceiling for the Smith diagonalization; beyond it we decline rather than risk
538/// `i128` overflow. Small prime-power components stay far below this.
539const GROWTH_CAP: i128 = 1i128 << 60;
540
541/// Decide a linear system over the residue **ring** `ℤ/pᵏ`. For `k = 1` this is the prime field, handed
542/// to the proven [`crate::modp::solve`]. For `k ≥ 2` the ring has zero divisors, so we diagonalize over
543/// the integers — `U·A·V = D` with `U, V` unimodular (Smith-style: gcd row/column reduction) — after
544/// which each `dₜ·yₜ ≡ (U·b)ₜ (mod pᵏ)` is an independent 1-D congruence, solvable iff
545/// `gcd(dₜ, pᵏ) ∣ (U·b)ₜ`. `U` yields both the satisfying assignment (`x = V·y`) and, on failure, the
546/// re-checkable refutation (a row of `U`, scaled to annihilate the coefficients mod `pᵏ`). Returns
547/// `None` only if the integer entries would exceed `GROWTH_CAP`.
548pub fn solve_prime_power(
549    equations: &[ModpEquation],
550    num_vars: usize,
551    p: u64,
552    k: u32,
553) -> Option<ModmOutcome> {
554    if k == 1 {
555        return Some(match modp::solve(equations, num_vars, p) {
556            ModpOutcome::Sat(a) => ModmOutcome::Sat(a),
557            ModpOutcome::Unsat(combo) => ModmOutcome::Unsat { modulus: p, combo },
558        });
559    }
560    let q = (p as i128).pow(k);
561    let m = equations.len();
562    let n = num_vars;
563    if m == 0 {
564        return Some(ModmOutcome::Sat(vec![0u64; n]));
565    }
566
567    // Working matrix `a = U·A·V`, with U (m×m) and V (n×n) the accumulated unimodular transforms, and
568    // `b` the original right-hand side (so `U·b` is the transformed rhs). All over ℤ.
569    let mut a = vec![vec![0i128; n]; m];
570    let mut b = vec![0i128; m];
571    let mut u = vec![vec![0i128; m]; m];
572    let mut v = vec![vec![0i128; n]; n];
573    for (i, ui) in u.iter_mut().enumerate() {
574        ui[i] = 1;
575    }
576    for (j, vj) in v.iter_mut().enumerate() {
577        vj[j] = 1;
578    }
579    for (i, eq) in equations.iter().enumerate() {
580        for &(var, coef) in &eq.coeffs {
581            if var < n {
582                a[i][var] = (a[i][var] + coef as i128).rem_euclid(q);
583            }
584        }
585        b[i] = (eq.rhs as i128).rem_euclid(q);
586    }
587
588    let exceeds_cap = |a: &[Vec<i128>], u: &[Vec<i128>], v: &[Vec<i128>]| {
589        a.iter()
590            .chain(u)
591            .chain(v)
592            .any(|r| r.iter().any(|&x| x.abs() > GROWTH_CAP))
593    };
594
595    let mut rank = 0usize;
596    for t in 0..m.min(n) {
597        loop {
598            // Pivot on the minimal-magnitude nonzero entry of the active submatrix — the gcd descent.
599            let mut best: Option<(usize, usize, i128)> = None;
600            for (i, row) in a.iter().enumerate().skip(t) {
601                for (j, &val) in row.iter().enumerate().skip(t) {
602                    if val != 0 && best.is_none_or(|(_, _, bv)| val.abs() < bv) {
603                        best = Some((i, j, val.abs()));
604                    }
605                }
606            }
607            let Some((pi, pj, _)) = best else { break };
608            if pi != t {
609                a.swap(pi, t);
610                u.swap(pi, t);
611            }
612            if pj != t {
613                for row in a.iter_mut() {
614                    row.swap(pj, t);
615                }
616                for row in v.iter_mut() {
617                    row.swap(pj, t);
618                }
619            }
620            let piv = a[t][t];
621            for i in 0..m {
622                if i != t && a[i][t] != 0 {
623                    let f = a[i][t].div_euclid(piv);
624                    if f != 0 {
625                        for j in 0..n {
626                            a[i][j] -= f * a[t][j];
627                        }
628                        for j in 0..m {
629                            u[i][j] -= f * u[t][j];
630                        }
631                    }
632                }
633            }
634            for j in 0..n {
635                if j != t && a[t][j] != 0 {
636                    let f = a[t][j].div_euclid(piv);
637                    if f != 0 {
638                        for row in a.iter_mut() {
639                            row[j] -= f * row[t];
640                        }
641                        for row in v.iter_mut() {
642                            row[j] -= f * row[t];
643                        }
644                    }
645                }
646            }
647            if exceeds_cap(&a, &u, &v) {
648                return None;
649            }
650            let col_clean = (0..m).all(|i| i == t || a[i][t] == 0);
651            let row_clean = (0..n).all(|j| j == t || a[t][j] == 0);
652            if col_clean && row_clean {
653                break;
654            }
655        }
656        if a[t][t] != 0 {
657            rank = t + 1;
658        } else {
659            break;
660        }
661    }
662
663    let ub: Vec<i128> = (0..m)
664        .map(|i| {
665            (0..m)
666                .fold(0i128, |acc, r| acc + u[i][r] * b[r])
667                .rem_euclid(q)
668        })
669        .collect();
670    let combo_from_row = |row: &[i128], lambda: i128| -> Vec<(usize, u64)> {
671        row.iter()
672            .enumerate()
673            .map(|(i, &c)| (i, (lambda * c).rem_euclid(q) as u64))
674            .filter(|&(_, mlt)| mlt != 0)
675            .collect()
676    };
677
678    let mut y = vec![0i128; n];
679    for t in 0..rank {
680        let d = a[t][t].rem_euclid(q);
681        let rhs = ub[t];
682        let g = gcd_i128(d, q);
683        if rhs.rem_euclid(g) != 0 {
684            // No solution to dₜ·yₜ ≡ rhs: scale this row by q/g to annihilate the coefficients mod q.
685            return Some(ModmOutcome::Unsat {
686                modulus: q as u64,
687                combo: combo_from_row(&u[t], q / g),
688            });
689        }
690        let qg = q / g;
691        y[t] = if qg == 1 {
692            0
693        } else {
694            (rhs / g).rem_euclid(qg) * modinv(d / g, qg) % qg
695        };
696    }
697    for (t, &ubt) in ub.iter().enumerate().skip(rank) {
698        // A zero row of D with a nonzero transformed rhs: uₜ·A = 0 over ℤ, so uₜ is the refutation.
699        if ubt != 0 {
700            return Some(ModmOutcome::Unsat {
701                modulus: q as u64,
702                combo: combo_from_row(&u[t], 1),
703            });
704        }
705    }
706
707    let x: Vec<u64> = (0..n)
708        .map(|i| {
709            (0..n)
710                .fold(0i128, |acc, j| acc + v[i][j] * y[j])
711                .rem_euclid(q) as u64
712        })
713        .collect();
714    debug_assert!(
715        satisfies(equations, &x, q as u64),
716        "the ring model must satisfy mod p^k"
717    );
718    Some(ModmOutcome::Sat(x))
719}
720
721/// Decide a linear system over `ℤ/m` for **any** `m ≥ 2`, closing every composite modulus. By CRT,
722/// `ℤ/m ≅ ∏ ℤ/pᵢ^{kᵢ}`: solve each prime-power component ([`solve_prime_power`]) and recombine the
723/// residues. Consistent mod `m` ⟺ consistent over every prime-power factor; the first inconsistent
724/// factor is the witness (and certifies UNSAT mod `m`, since that factor divides `m`). Returns `None`
725/// only if `m < 2`, or a component is too large / overflows the integer Smith reduction.
726pub fn solve(equations: &[ModpEquation], num_vars: usize, m: u64) -> Option<ModmOutcome> {
727    let factors = prime_power_factorize(m)?;
728    let mut per_component: Vec<(u64, Vec<u64>)> = Vec::with_capacity(factors.len());
729    for (p, k) in factors {
730        let q = p.pow(k);
731        if q as u128 > 1_000_000_000 {
732            return None; // decline an oversized prime-power component
733        }
734        match solve_prime_power(equations, num_vars, p, k)? {
735            ModmOutcome::Sat(a) => per_component.push((q, a)),
736            unsat @ ModmOutcome::Unsat { .. } => return Some(unsat),
737        }
738    }
739    let mut assignment = vec![0u64; num_vars];
740    for (i, slot) in assignment.iter_mut().enumerate() {
741        let residues: Vec<(u64, u64)> = per_component.iter().map(|(q, a)| (a[i], *q)).collect();
742        *slot = crt(&residues);
743    }
744    Some(ModmOutcome::Sat(assignment))
745}
746
747#[cfg(test)]
748#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/modm/tests.rs"]
749mod tests;