使用 Z3 求解线性方程

Question

我有以下线性方程。

m = 2 ** 31 - 1

(207560540 ∗ a + b) modulo m = 956631177
(956631177 ∗ a + b) modulo m = 2037688522

求解这些方程最有效的方法是什么？

我使用了 Z3，但是没有找到任何解决方案。我的 Z3 求解上述方程的代码是：

#! /usr/bin/python

from z3 import *

a = Int('a')
b = Int('b')

s = Solver()

s.add((a * 207560540 + b) % 2147483647 == 956631177)
s.add((a * 956631177 + b) % 2147483647 == 2037688522)

print s.check()
print s.model()

我知道解法是：a = 16807，b = 78125，但是，请问Z3怎么解呢？

我尝试的另一种方法是将 a 和 b 设置为 BitVec() 而不是整数，如下所示：

a = BitVec('a', 32)
b = BitVec('b', 32)

这给了我一个不正确的解决方案，如下所示：

[b = 3637638538, a = 4177905984]

有没有办法用Z3解决？

谢谢。

Answer 1

关于位向量的旁白：当您使用位向量时，所有操作都以模 2^N 完成，其中 N 是位向量大小。所以，z3 没有给你一个 incorrect 解决方案：如果你对 2^32 进行数学模运算，你会发现它找到的模型确实是正确的。

看来您的问题确实需要无界整数，并且由于模 2^31-1 而不是真正的线性问题。（线性意味着乘以一个常数；模数乘以一个常数会让你进入一个不同的领域。）模数并不容易推理；我不认为 z3 是解决此类问题的正确工具，也不是任何其他 SMT 求解器。在这种情况下，mathematica、wolfram-alpha 等工具可能是更好的选择；例如，参见：wolfram-alpha solution

使用 Z3 求解线性方程

Solving linear equations using Z3

python

z3py