当我增加 Bitvector 的长度时，z3py solver.check() 从 "sat" 变为 "unknown"

Question

我想在 Z3 中用 Bitvectors 对数字 n 进行因式分解。我使用 Bitvectores 是因为我想限制 p 和 q 中的单个位。这个简单的例子确实有效，求解器 returns "sat".

from z3 import *

Bits = 32

n = 12
p_vec = BitVec('p', Bits)
q_vec = BitVec('q', Bits)
n_vec = BitVecVal(n,Bits)

s = Solver()
s.add(p_vec * q_vec == n_vec)
s.add(p_vec > 1, q_vec > 1)
s.add(BVMulNoOverflow(p_vec,q_vec,False))

print (s.check())

但现在我想分解另一个 4096 位的数字 n。所以我在示例中更改了 Bits=4096 并使用了相同的数字。求解器现在给我 "unknow" 而不是 "sat"。似乎求解器在某个时候停止了。我是否必须更改某些求解器设置或是否有其他方法可以做到这一点。

Answer 1

当我运行你的程序使用 Bits = 4096 时，它 而不是 说 unknown。它根本没有很快完成（我等了几分钟），我不希望它完成。

Bitvector 求解器已完成。也就是说，如果您等待的时间足够长，它最终会 return sat 或 unsat，假设您没有运行内存不足（和耐心）。然而，对于这个问题，您将等待的时间实际上可能是无限的，而且您很可能运行在此之前很长时间计算机内存不足。所以，我不确定您是如何获得 unknown 的。也许您正在使用一些超时选项，或者您未在此处显示的其他内容。

您可以尝试添加以下形式的约束：p_vec < n 和 q_vec < p_vec 来打破对称性。在某些情况下它确实有帮助，因为 n 是一个常数。但这通常是徒劳的，对于密码实践中使用的任何合理的位大小，求解器实际上将永远循环。

由于显而易见的原因，因式分解是一个难题，SMT 求解器绝对不是适合它的工具。早先的讨论见此处：

当我增加 Bitvector 的长度时，z3py solver.check() 从 "sat" 变为 "unknown"

z3py solver.check() goes from "sat" to "unknown" when I increase length of Bitvector

solver

bitvector

python-3.x

z3