Skip to main content

logicaffeine_proof/
modp.rs

1//! Linear algebra over `GF(p)` — the mod-`p` generalization of the GF(2) parity cut ([`crate::xorsat`]).
2//!
3//! A system of congruences `Σ aᵢ·xᵢ ≡ c (mod p)` is decided in **polynomial time** by Gaussian
4//! elimination with modular inverses, and it is **certified**: an inconsistent system yields a
5//! re-checkable linear-dependency refutation — a combination of the original equations whose left side
6//! cancels to `0` while the right side is some nonzero residue, i.e. `0 ≡ r ≢ 0 (mod p)`. A consistent
7//! system yields a satisfying assignment over `GF(p)`.
8//!
9//! This matters because the parity cut only speaks GF(2). The mod-`p` *counting principles* (`Count_p`:
10//! "partition a set whose size is not a multiple of `p` into `p`-blocks") are resolution-hard, and a
11//! polynomial-calculus proof over the *wrong* characteristic cannot refute them either — but Gaussian
12//! elimination over the *right* `GF(p)` decides them instantly. A genuinely new invariant, the parity
13//! crush carried to every prime.
14
15/// A congruence `Σ (a·x) ≡ rhs (mod p)`. Coefficients and `rhs` are reduced mod `p`. `p` must be prime
16/// (so every nonzero element is invertible, via Fermat).
17#[derive(Clone, Debug, PartialEq, Eq)]
18pub struct ModpEquation {
19    pub coeffs: Vec<(usize, u64)>,
20    pub rhs: u64,
21}
22
23impl ModpEquation {
24    pub fn new(coeffs: impl Into<Vec<(usize, u64)>>, rhs: u64) -> Self {
25        ModpEquation {
26            coeffs: coeffs.into(),
27            rhs,
28        }
29    }
30}
31
32/// The outcome of solving a mod-`p` linear system.
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub enum ModpOutcome {
35    /// Satisfiable, with an assignment over `0..p` for each of `0..num_vars` (re-checkable via
36    /// [`satisfies`]).
37    Sat(Vec<u64>),
38    /// Unsatisfiable, witnessed by a combination `Σ (multiplier · equationᵢ)` whose left side cancels
39    /// while the right side is nonzero — re-checkable via [`is_refutation`].
40    Unsat(Vec<(usize, u64)>),
41}
42
43#[inline]
44fn add(a: u64, b: u64, p: u64) -> u64 {
45    (a + b) % p
46}
47#[inline]
48fn sub(a: u64, b: u64, p: u64) -> u64 {
49    (a + p - b % p) % p
50}
51#[inline]
52fn mul(a: u64, b: u64, p: u64) -> u64 {
53    (a % p) * (b % p) % p
54}
55#[inline]
56fn powm(mut a: u64, mut e: u64, p: u64) -> u64 {
57    let mut r = 1u64 % p;
58    a %= p;
59    while e > 0 {
60        if e & 1 == 1 {
61            r = mul(r, a, p);
62        }
63        a = mul(a, a, p);
64        e >>= 1;
65    }
66    r
67}
68/// Modular inverse of a nonzero `a` over a prime field (Fermat: `a^{p-2}`).
69#[inline]
70fn inv(a: u64, p: u64) -> u64 {
71    powm(a, p - 2, p)
72}
73
74/// Decide a mod-`p` linear system by Gaussian elimination over `GF(p)`. Returns a satisfying
75/// assignment, or an inconsistency-witnessing combination of the original equations. `p` must be prime.
76pub fn solve(equations: &[ModpEquation], num_vars: usize, p: u64) -> ModpOutcome {
77    let m = equations.len();
78    // Each row carries its variable coefficients, its rhs, and its provenance (how it is built from the
79    // original equations — a coefficient per original equation). All arithmetic is mod p.
80    let mut coeff: Vec<Vec<u64>> = Vec::with_capacity(m);
81    let mut rhs: Vec<u64> = Vec::with_capacity(m);
82    let mut prov: Vec<Vec<u64>> = Vec::with_capacity(m);
83    for (i, eq) in equations.iter().enumerate() {
84        let mut c = vec![0u64; num_vars];
85        for &(v, a) in &eq.coeffs {
86            if v < num_vars {
87                c[v] = add(c[v], a, p);
88            }
89        }
90        coeff.push(c);
91        rhs.push(eq.rhs % p);
92        let mut pr = vec![0u64; m];
93        pr[i] = 1 % p;
94        prov.push(pr);
95    }
96
97    let mut pivot_col_of_row: Vec<usize> = Vec::new();
98    let mut row = 0usize;
99    for col in 0..num_vars {
100        let Some(sel) = (row..coeff.len()).find(|&r| coeff[r][col] != 0) else {
101            continue;
102        };
103        coeff.swap(row, sel);
104        rhs.swap(row, sel);
105        prov.swap(row, sel);
106        // Normalize the pivot row so its pivot coefficient is 1.
107        let factor = inv(coeff[row][col], p);
108        for v in 0..num_vars {
109            coeff[row][v] = mul(coeff[row][v], factor, p);
110        }
111        rhs[row] = mul(rhs[row], factor, p);
112        for k in 0..m {
113            prov[row][k] = mul(prov[row][k], factor, p);
114        }
115        // Eliminate this column from every other row.
116        for r in 0..coeff.len() {
117            if r != row && coeff[r][col] != 0 {
118                let f = coeff[r][col];
119                for v in 0..num_vars {
120                    coeff[r][v] = sub(coeff[r][v], mul(f, coeff[row][v], p), p);
121                }
122                rhs[r] = sub(rhs[r], mul(f, rhs[row], p), p);
123                for k in 0..m {
124                    prov[r][k] = sub(prov[r][k], mul(f, prov[row][k], p), p);
125                }
126            }
127        }
128        pivot_col_of_row.push(col);
129        row += 1;
130        if row == coeff.len() {
131            break;
132        }
133    }
134
135    // An all-zero row with a nonzero rhs is `0 ≡ nonzero` — a refutation; its provenance is the combo.
136    for r in 0..coeff.len() {
137        if coeff[r].iter().all(|&x| x == 0) && rhs[r] != 0 {
138            let combo: Vec<(usize, u64)> = prov[r]
139                .iter()
140                .enumerate()
141                .filter(|&(_, &m)| m != 0)
142                .map(|(i, &m)| (i, m))
143                .collect();
144            return ModpOutcome::Unsat(combo);
145        }
146    }
147
148    // Consistent: free variables take 0, each pivot variable takes its (reduced) rhs.
149    let mut assignment = vec![0u64; num_vars];
150    for (r, &col) in pivot_col_of_row.iter().enumerate() {
151        assignment[col] = rhs[r];
152    }
153    ModpOutcome::Sat(assignment)
154}
155
156/// The **complete solution space** of a `GF(p)` linear system `A x = b`, in symmetry-broken form: one
157/// particular solution `x₀` plus a basis of the kernel (null space). Every solution is `x₀ +` a `GF(p)`
158/// combination of the kernel basis, so all `p^{n−rank}` solutions are generated from this compressed
159/// witness. The kernel is the **translation symmetry** of the solution coset — the `GF(p)` analogue of
160/// [`crate::gf2::SolutionSpace`], and the substrate of the affine SAT-side break: a variable the kernel
161/// never moves is forced to a single value.
162#[derive(Clone, Debug, PartialEq, Eq)]
163pub struct SolutionSpaceP {
164    pub num_vars: usize,
165    pub p: u64,
166    pub particular: Vec<u64>,
167    pub kernel_basis: Vec<Vec<u64>>,
168}
169
170impl SolutionSpaceP {
171    /// The number of solutions: `p^{dim kernel}`.
172    pub fn count(&self) -> u128 {
173        (self.p as u128).pow(self.kernel_basis.len() as u32)
174    }
175
176    /// Generate **every** solution: `x₀` plus each `GF(p)` combination of the kernel basis.
177    pub fn enumerate(&self) -> Vec<Vec<u64>> {
178        let k = self.kernel_basis.len();
179        let total = (self.p as u128).pow(k as u32);
180        (0..total as u64)
181            .map(|mut code| {
182                let mut x = self.particular.clone();
183                for b in 0..k {
184                    let coef = code % self.p;
185                    code /= self.p;
186                    if coef != 0 {
187                        for v in 0..self.num_vars {
188                            x[v] = add(x[v], mul(coef, self.kernel_basis[b][v], self.p), self.p);
189                        }
190                    }
191                }
192                x
193            })
194            .collect()
195    }
196}
197
198/// Solve a `GF(p)` system for its **entire** solution space via Gaussian elimination to reduced row
199/// echelon form, returning the symmetry-broken [`SolutionSpaceP`] (particular solution + kernel basis),
200/// or `None` iff the system is inconsistent. Generalizes [`solve`], which returns just one witness, to the
201/// full coset — the `GF(p)` analogue of [`crate::gf2::solve_gf2`]. `p` must be prime.
202pub fn solve_space(equations: &[ModpEquation], num_vars: usize, p: u64) -> Option<SolutionSpaceP> {
203    let mut coeff: Vec<Vec<u64>> = Vec::with_capacity(equations.len());
204    let mut rhs: Vec<u64> = Vec::with_capacity(equations.len());
205    for eq in equations {
206        let mut c = vec![0u64; num_vars];
207        for &(v, a) in &eq.coeffs {
208            if v < num_vars {
209                c[v] = add(c[v], a, p);
210            }
211        }
212        coeff.push(c);
213        rhs.push(eq.rhs % p);
214    }
215
216    let mut pivot_col_of_row: Vec<usize> = Vec::new();
217    let mut row = 0usize;
218    for col in 0..num_vars {
219        let Some(sel) = (row..coeff.len()).find(|&r| coeff[r][col] != 0) else {
220            continue;
221        };
222        coeff.swap(row, sel);
223        rhs.swap(row, sel);
224        let factor = inv(coeff[row][col], p);
225        for v in 0..num_vars {
226            coeff[row][v] = mul(coeff[row][v], factor, p);
227        }
228        rhs[row] = mul(rhs[row], factor, p);
229        // Full reduction: clear this pivot column from every other row.
230        for r in 0..coeff.len() {
231            if r != row && coeff[r][col] != 0 {
232                let f = coeff[r][col];
233                for v in 0..num_vars {
234                    coeff[r][v] = sub(coeff[r][v], mul(f, coeff[row][v], p), p);
235                }
236                rhs[r] = sub(rhs[r], mul(f, rhs[row], p), p);
237            }
238        }
239        pivot_col_of_row.push(col);
240        row += 1;
241    }
242
243    // Inconsistent: a fully-reduced row with no coefficients but a nonzero right-hand side (0 = c ≠ 0).
244    for r in 0..coeff.len() {
245        if coeff[r].iter().all(|&x| x == 0) && rhs[r] != 0 {
246            return None;
247        }
248    }
249
250    let mut is_pivot = vec![false; num_vars];
251    for &c in &pivot_col_of_row {
252        is_pivot[c] = true;
253    }
254    // Particular: free variables 0, each pivot variable = its row's right-hand side.
255    let mut particular = vec![0u64; num_vars];
256    for (r, &pc) in pivot_col_of_row.iter().enumerate() {
257        particular[pc] = rhs[r];
258    }
259    // Kernel: one vector per free column f — set x_f = 1, each pivot var = −(its row's f-coefficient).
260    let mut kernel_basis = Vec::new();
261    for f in 0..num_vars {
262        if is_pivot[f] {
263            continue;
264        }
265        let mut kv = vec![0u64; num_vars];
266        kv[f] = 1;
267        for (r, &pc) in pivot_col_of_row.iter().enumerate() {
268            kv[pc] = sub(0, coeff[r][f], p);
269        }
270        kernel_basis.push(kv);
271    }
272    Some(SolutionSpaceP {
273        num_vars,
274        p,
275        particular,
276        kernel_basis,
277    })
278}
279
280/// The canonical scalable mod-`p` obstruction: a cycle of differences `xᵢ − x_{i+1} ≡ 1 (mod p)` around
281/// an `n`-cycle. Summing all `n` equations telescopes the left side to `0` and the right to `n`, so the
282/// system is inconsistent **exactly when `n` is not a multiple of `p`** — the mod-`p` counting fact. For
283/// even `n` with `p > 2 ∤ n` it is satisfiable over `GF(2)` yet refuted over `GF(p)`: a family the parity
284/// cut cannot see. (`x − y` is written `x + (p−1)y`.)
285pub fn cycle_system(n: usize, p: u64) -> Vec<ModpEquation> {
286    (0..n)
287        .map(|i| ModpEquation::new(vec![(i, 1), ((i + 1) % n, p - 1)], 1))
288        .collect()
289}
290
291/// Re-check a satisfying assignment: every congruence holds mod `p`.
292pub fn satisfies(equations: &[ModpEquation], assignment: &[u64], p: u64) -> bool {
293    equations.iter().all(|eq| {
294        let lhs = eq.coeffs.iter().fold(0u64, |acc, &(v, a)| {
295            add(acc, mul(a, *assignment.get(v).unwrap_or(&0), p), p)
296        });
297        lhs == eq.rhs % p
298    })
299}
300
301/// Re-check a refutation: the chosen combination of equations has every variable coefficient `≡ 0` and
302/// a nonzero right-hand side mod `p` — a solver-free certificate of inconsistency.
303pub fn is_refutation(
304    equations: &[ModpEquation],
305    num_vars: usize,
306    p: u64,
307    combo: &[(usize, u64)],
308) -> bool {
309    if combo.is_empty() {
310        return false;
311    }
312    let mut lhs = vec![0u64; num_vars];
313    let mut rhs = 0u64;
314    for &(idx, mult) in combo {
315        let Some(eq) = equations.get(idx) else {
316            return false;
317        };
318        for &(v, a) in &eq.coeffs {
319            if v < num_vars {
320                lhs[v] = add(lhs[v], mul(mult, a, p), p);
321            }
322        }
323        rhs = add(rhs, mul(mult, eq.rhs, p), p);
324    }
325    lhs.iter().all(|&x| x == 0) && rhs != 0
326}
327
328/// A mod-`m` linear system recovered from an opaque Boolean CNF: the one-hot groups (each a `ℤ/m`
329/// variable, with the boolean var ids listed in value order) plus the congruences fitted to the
330/// forbidden-combination clauses. The recovered system is **equisatisfiable** to the source CNF, so the
331/// modular verdict carries back — over the prime field [`solve`] when `modulus` is prime, over the
332/// composite ring [`crate::modm::solve`] otherwise. See [`recover_from_cnf`].
333#[derive(Clone, Debug)]
334pub struct ModpRecovery {
335    pub modulus: u64,
336    /// One `ℤ/modulus` variable per one-hot group.
337    pub num_vars: usize,
338    pub equations: Vec<ModpEquation>,
339    /// `groups[g][val]` = the boolean variable that means "variable `g` takes value `val`".
340    pub groups: Vec<Vec<u32>>,
341}
342
343pub fn is_prime(p: u64) -> bool {
344    if p < 2 {
345        return false;
346    }
347    let mut d = 2u64;
348    while d * d <= p {
349        if p % d == 0 {
350            return false;
351        }
352        d += 1;
353    }
354    true
355}
356
357/// A basis of the null space `{ a : (row · a) ≡ 0 for every row }` over `GF(p)`, by reduced row echelon
358/// form: each non-pivot (free) column yields one basis vector. Used to fit a congruence's coefficient
359/// vector as the (unique up to scalar) normal of the hyperplane spanned by the allowed value tuples.
360fn nullspace(rows: &[Vec<u64>], k: usize, p: u64) -> Vec<Vec<u64>> {
361    let mut m: Vec<Vec<u64>> = rows
362        .iter()
363        .map(|r| r.iter().map(|&x| x % p).collect())
364        .collect();
365    let mut where_pivot: Vec<isize> = vec![-1; k];
366    let mut row = 0usize;
367    for col in 0..k {
368        let Some(sel) = (row..m.len()).find(|&r| m[r][col] != 0) else {
369            continue;
370        };
371        m.swap(row, sel);
372        let finv = inv(m[row][col], p);
373        for c in 0..k {
374            m[row][c] = mul(m[row][c], finv, p);
375        }
376        for r in 0..m.len() {
377            if r != row && m[r][col] != 0 {
378                let f = m[r][col];
379                for c in 0..k {
380                    m[r][c] = sub(m[r][c], mul(f, m[row][c], p), p);
381                }
382            }
383        }
384        where_pivot[col] = row as isize;
385        row += 1;
386        if row == m.len() {
387            break;
388        }
389    }
390    let mut basis = Vec::new();
391    for free in 0..k {
392        if where_pivot[free] != -1 {
393            continue;
394        }
395        let mut v = vec![0u64; k];
396        v[free] = 1;
397        for (col, &pr) in where_pivot.iter().enumerate() {
398            if pr != -1 {
399                v[col] = sub(0, m[pr as usize][free], p);
400            }
401        }
402        basis.push(v);
403    }
404    basis
405}
406
407/// Fit the unique linear congruence `Σ aᵢ·tᵢ ≡ c (mod m)` whose solution set is EXACTLY `allowed` (the
408/// complement of the forbidden tuples). Over a **prime field** this is the hyperplane normal — the
409/// `allowed` set must be `m^{k-1}` points and `a` is the (up-to-scalar unique) null vector of their
410/// differences. Over a **composite ring** there is no field inverse, so `a` is found by a bounded search
411/// over coefficient vectors (`c` is forced once `a` and a base point are fixed). Either way the returned
412/// `(a, c)` is re-verified to reproduce the split exactly, so soundness never depends on which branch
413/// fired. Returns `None` when no single congruence reproduces the split (then the caller declines).
414fn fit_congruence(
415    k: usize,
416    allowed: &[Vec<u64>],
417    forbidden: &[Vec<u64>],
418    m: u64,
419) -> Option<(Vec<u64>, u64)> {
420    let t0 = allowed.first()?;
421    let mm = m as u128;
422    let eval = |a: &[u64], t: &[u64]| -> u64 {
423        (0..k).fold(0u128, |acc, i| (acc + a[i] as u128 * t[i] as u128) % mm) as u64
424    };
425    let candidate: Option<Vec<u64>> = if is_prime(m) {
426        // Prime field: a single congruence has exactly m^{k-1} solutions, and its normal is the unique
427        // null direction of the allowed-tuple differences.
428        if (allowed.len() as u128) != mm.pow((k - 1) as u32) {
429            return None;
430        }
431        let diffs: Vec<Vec<u64>> = allowed
432            .iter()
433            .skip(1)
434            .map(|t| (0..k).map(|i| sub(t[i], t0[i], m)).collect())
435            .collect();
436        let basis = nullspace(&diffs, k, m);
437        (basis.len() == 1 && basis[0].iter().any(|&x| x != 0)).then(|| basis[0].clone())
438    } else {
439        // Composite ring: bounded brute search over the coefficient vectors.
440        let total = mm.checked_pow(k as u32)?;
441        if total.checked_mul(total)? > (1u128 << 24) {
442            return None; // refuse an oversized ring fit; let CDCL have it
443        }
444        let mut found = None;
445        for code in 0..total {
446            let mut a = vec![0u64; k];
447            let mut x = code;
448            for slot in a.iter_mut() {
449                *slot = (x % mm) as u64;
450                x /= mm;
451            }
452            if a.iter().all(|&v| v == 0) {
453                continue;
454            }
455            let c = eval(&a, t0);
456            if allowed.iter().all(|t| eval(&a, t) == c)
457                && forbidden.iter().all(|f| eval(&a, f) != c)
458            {
459                found = Some(a);
460                break;
461            }
462        }
463        found
464    };
465    let a = candidate?;
466    let c = eval(&a, t0);
467    if allowed.iter().any(|t| eval(&a, t) != c) || forbidden.iter().any(|f| eval(&a, f) == c) {
468        return None;
469    }
470    Some((a, c))
471}
472
473/// **Lift an opaque Boolean CNF onto `ℤ/m`.** Recognize the canonical one-hot encoding of a mod-`m`
474/// linear system — each variable a group of `m` bits with an at-least-one clause and the full pairwise
475/// at-most-one, plus all-negative "forbidden combination" clauses pinning the congruences — and recover
476/// the system over `ℤ/m`. The modulus `m` is the group size; it may be prime (a field) or composite
477/// (a ring), and `fit_congruence` handles both. Returns `None` (declining, never guessing) unless
478/// every clause fits the pattern and every forbidden set is **exactly** the complement of a single
479/// congruence: then the recovered system is equisatisfiable to the CNF, so the modular solver's verdict
480/// transfers (UNSAT certificate carries; a SAT model is re-checked against the clauses by the caller).
481/// The `m = 2` case is the parity cut; this is that cut generalized to every modulus — the obstruction
482/// GF(2) is blind to, decided in polynomial time where resolution (CDCL, Z3, Kissat) needs `2^Ω(n)`.
483pub fn recover_from_cnf(
484    num_bool_vars: usize,
485    clauses: &[Vec<crate::cdcl::Lit>],
486) -> Option<ModpRecovery> {
487    use std::collections::{BTreeMap, HashMap, HashSet};
488    if clauses.is_empty() {
489        return None;
490    }
491
492    // Pass 1 — discover one-hot groups (all-positive clauses of size ≥ 2) and the at-most-one pairs.
493    let mut group_candidates: Vec<Vec<u32>> = Vec::new();
494    let mut neg_pairs: HashSet<(u32, u32)> = HashSet::new();
495    let mut appears: HashSet<u32> = HashSet::new();
496    for c in clauses {
497        for l in c {
498            appears.insert(l.var());
499        }
500        if c.len() >= 2 && c.iter().all(|l| l.is_positive()) {
501            let mut g: Vec<u32> = c.iter().map(|l| l.var()).collect();
502            g.sort_unstable();
503            g.dedup();
504            if g.len() != c.len() {
505                return None;
506            }
507            group_candidates.push(g);
508        } else if c.len() == 2 && c.iter().all(|l| !l.is_positive()) {
509            let (a, b) = (c[0].var(), c[1].var());
510            neg_pairs.insert((a.min(b), a.max(b)));
511        }
512    }
513    if group_candidates.is_empty() {
514        return None;
515    }
516    let m = group_candidates[0].len() as u64;
517    if m < 2 {
518        return None;
519    }
520
521    // Validate groups: uniform size, disjoint, full pairwise at-most-one present.
522    let mut var_to_group: HashMap<u32, usize> = HashMap::new();
523    let mut groups: Vec<Vec<u32>> = Vec::new();
524    for g in &group_candidates {
525        if g.len() as u64 != m {
526            return None;
527        }
528        for i in 0..g.len() {
529            for j in (i + 1)..g.len() {
530                if !neg_pairs.contains(&(g[i], g[j])) {
531                    return None;
532                }
533            }
534        }
535        let gid = groups.len();
536        for &v in g {
537            if var_to_group.insert(v, gid).is_some() {
538                return None; // a variable in two groups: not a clean one-hot partition
539            }
540        }
541        groups.push(g.clone());
542    }
543    // Every variable that appears must belong to a group, or the encoding is not pure one-hot.
544    if appears.iter().any(|v| !var_to_group.contains_key(v)) {
545        return None;
546    }
547    let _ = num_bool_vars;
548    let pos_in_group =
549        |v: u32, gid: usize| groups[gid].iter().position(|&x| x == v).unwrap() as u64;
550
551    // Pass 2 — classify every clause; collect forbidden tuples per scope (a sorted set of groups).
552    let mut scopes: BTreeMap<Vec<usize>, Vec<Vec<u64>>> = BTreeMap::new();
553    for c in clauses {
554        if c.len() >= 2 && c.iter().all(|l| l.is_positive()) {
555            continue; // at-least-one of a group: one-hot structure
556        }
557        if c.len() == 2 && c.iter().all(|l| !l.is_positive()) {
558            let g0 = *var_to_group.get(&c[0].var())?;
559            let g1 = *var_to_group.get(&c[1].var())?;
560            if g0 == g1 {
561                continue; // at-most-one within a group: one-hot structure
562            }
563        }
564        if !c.iter().all(|l| !l.is_positive()) {
565            return None; // anything mixing polarities is not part of the recognized encoding
566        }
567        let mut pairs: Vec<(usize, u64)> = Vec::new();
568        let mut seen = HashSet::new();
569        for l in c {
570            let g = *var_to_group.get(&l.var())?;
571            if !seen.insert(g) {
572                return None; // two bits of the same group in one forbidden combo
573            }
574            pairs.push((g, pos_in_group(l.var(), g)));
575        }
576        pairs.sort_by_key(|&(g, _)| g);
577        let scope: Vec<usize> = pairs.iter().map(|&(g, _)| g).collect();
578        let tuple: Vec<u64> = pairs.iter().map(|&(_, v)| v).collect();
579        scopes.entry(scope).or_default().push(tuple);
580    }
581    if scopes.is_empty() {
582        return None;
583    }
584
585    // For each scope, fit the unique congruence whose violated set is EXACTLY the forbidden tuples.
586    let mut equations: Vec<ModpEquation> = Vec::new();
587    for (scope, forbidden) in &scopes {
588        let k = scope.len();
589        let total = (m as u128).checked_pow(k as u32)?;
590        if total > (1u128 << 22) {
591            return None; // refuse to enumerate an oversized scope; let CDCL have it
592        }
593        let forbidden_set: HashSet<Vec<u64>> = forbidden.iter().cloned().collect();
594        let mut allowed: Vec<Vec<u64>> = Vec::new();
595        for idx in 0..total {
596            let mut t = vec![0u64; k];
597            let mut x = idx;
598            for slot in t.iter_mut() {
599                *slot = (x % m as u128) as u64;
600                x /= m as u128;
601            }
602            if !forbidden_set.contains(&t) {
603                allowed.push(t);
604            }
605        }
606        let (a, c) = fit_congruence(k, &allowed, forbidden, m)?;
607        let coeffs: Vec<(usize, u64)> = scope
608            .iter()
609            .enumerate()
610            .map(|(i, &g)| (g, a[i]))
611            .filter(|&(_, ai)| ai != 0)
612            .collect();
613        if coeffs.is_empty() {
614            return None;
615        }
616        equations.push(ModpEquation::new(coeffs, c));
617    }
618
619    Some(ModpRecovery {
620        modulus: m,
621        num_vars: groups.len(),
622        equations,
623        groups,
624    })
625}
626
627/// `|GL(n,p)|` over `GF(p)` via the orbit–stabilizer (ordered-basis) factorization
628/// `Π_{i=0}^{n-1}(pⁿ − pⁱ)`. `GL(n,p)` acts **simply transitively on ordered bases** of `GF(p)ⁿ`, so each
629/// factor `pⁿ − pⁱ` counts the vectors outside the i-dimensional span built so far — the same symmetry
630/// break as over `GF(2)`, now across the field. The `p = 2` case is `gf2::gl_order`.
631pub fn gl_order_p(n: u32, p: u64) -> u128 {
632    let pn = (p as u128).pow(n);
633    (0..n).map(|i| pn - (p as u128).pow(i)).product()
634}
635
636/// Is an `n×n` matrix over `GF(p)` invertible? Gaussian elimination with modular pivots: full rank `n`.
637/// `p` must be prime.
638pub fn is_invertible_modp(n: usize, p: u64, matrix: &[Vec<u64>]) -> bool {
639    let mut a: Vec<Vec<u64>> = matrix
640        .iter()
641        .map(|r| r.iter().map(|&x| x % p).collect())
642        .collect();
643    let mut rank = 0usize;
644    for col in 0..n {
645        if let Some(piv) = (rank..n).find(|&r| a[r][col] != 0) {
646            a.swap(rank, piv);
647            let pinv = inv(a[rank][col], p);
648            for c in 0..n {
649                a[rank][c] = mul(a[rank][c], pinv, p);
650            }
651            for r in 0..n {
652                if r != rank && a[r][col] != 0 {
653                    let f = a[r][col];
654                    for c in 0..n {
655                        a[r][c] = sub(a[r][c], mul(f, a[rank][c], p), p);
656                    }
657                }
658            }
659            rank += 1;
660        }
661    }
662    rank == n
663}
664
665/// The invertibility *density* over `GF(p)`: `Π_{j=1}^n (1 − p⁻ʲ) = |GL(n,p)| / p^{n²}`. As the field
666/// grows the density → 1 (fewer linear collisions); `p = 2` is the densest-collision regime, the smallest
667/// constant `φ(½) ≈ 0.28879`.
668pub fn invertibility_density_p(n: u32, p: u64) -> f64 {
669    (1..=n)
670        .map(|j| 1.0 - (p as f64).powi(-(j as i32)))
671        .product()
672}
673
674#[cfg(test)]
675#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/modp/tests.rs"]
676mod tests;