1#[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#[derive(Clone, Debug, PartialEq, Eq)]
34pub enum ModpOutcome {
35 Sat(Vec<u64>),
38 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#[inline]
70fn inv(a: u64, p: u64) -> u64 {
71 powm(a, p - 2, p)
72}
73
74pub fn solve(equations: &[ModpEquation], num_vars: usize, p: u64) -> ModpOutcome {
77 let m = equations.len();
78 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 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 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 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 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#[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 pub fn count(&self) -> u128 {
173 (self.p as u128).pow(self.kernel_basis.len() as u32)
174 }
175
176 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
198pub 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 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 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 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 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
280pub 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
291pub 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
301pub 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#[derive(Clone, Debug)]
334pub struct ModpRecovery {
335 pub modulus: u64,
336 pub num_vars: usize,
338 pub equations: Vec<ModpEquation>,
339 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
357fn 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
407fn 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 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 let total = mm.checked_pow(k as u32)?;
441 if total.checked_mul(total)? > (1u128 << 24) {
442 return None; }
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
473pub 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 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 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; }
540 }
541 groups.push(g.clone());
542 }
543 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 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; }
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; }
563 }
564 if !c.iter().all(|l| !l.is_positive()) {
565 return None; }
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; }
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 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; }
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
627pub 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
636pub 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
665pub 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;