1use 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
30fn 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
40fn modinv(a: i128, n: i128) -> i128 {
42 let (_, x, _) = egcd(a.rem_euclid(n), n);
43 x.rem_euclid(n)
44}
45
46pub 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; }
62 primes.push(d);
63 }
64 d += 1;
65 }
66 if x > 1 {
67 primes.push(x);
68 }
69 Some(primes)
70}
71
72#[derive(Clone, Debug, PartialEq, Eq)]
74pub enum ModmOutcome {
75 Sat(Vec<u64>),
77 Unsat {
83 modulus: u64,
84 combo: Vec<(usize, u64)>,
85 },
86}
87
88pub 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
117pub 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 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
143fn 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
160pub enum ForcedM {
162 Inconsistent,
164 Forced(Vec<Option<u64>>),
166}
167
168pub 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
206pub 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
218pub enum PrimePowerSpace {
220 Inconsistent,
221 Space(SolutionSpaceM),
222}
223
224pub 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 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); }
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 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
395pub 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
436pub enum AllowedOutcome {
443 Inconsistent,
444 Allowed(Vec<(u64, u64)>),
445}
446
447pub 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 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 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
494pub 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
505pub fn cycle_system(n: usize, m: u64) -> Vec<ModpEquation> {
509 modp::cycle_system(n, m)
510}
511
512pub 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
537const GROWTH_CAP: i128 = 1i128 << 60;
540
541pub 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 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 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 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 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
721pub 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; }
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;