找到一个乘法器，将给定的索引乘以比特的形式

Question

我有一组索引和一组位掩码（组的大小相同，在 6-4096 之间，但更接近下限）。我还有一个位掩码，我将其称为超集。我需要找到一个因子，如果对于我拥有的任何索引，如果我将因子、索引和掩码位与超集相乘，结果就是子集。掩码和因子均为 64 位宽。这个例子是8位的，因为我显然不能在这里写64位掩码

mask = 00111000         ((p * index) & mask) == subset
index=3 sub=00010000 => ((p * 3) & mask) == 00010000
index=5 sub=00100000 => ((p * 5) & mask) == 00100000

实际上，我的输入只是索引的集合 {i0, i1, ... iN}、掩码的 {s0, s1, ... sN} 和超集掩码。 当然，所有子集都是超集的子集。目前，对于不同的索引，可能会有相同的子集结果，但我会很高兴收到就好像这不是约束一样的解决方案。

我现在最好的尝试就是猜测因子的随机数，并检查每个指数子集对是否成立。如果没有，我就转到下一个号码。但对于这个问题的最小形式，我有 13 个这样的对，但由于暴力算法是

O(2^n)

，具有非常大的常数因子，所以我找不到一个即使对于 7 对也适用的因子！

我想到的是查看乘法的结果值。让我们从 8 位形式来看这个问题：（这里的 a、b、c、d 等表示是否在乘法结果中设置了第 i 位）

P * Index = 2^0*a + 2^1*b + 2^2*c + 2^3*d + 2^4*e + 2^5*f + 2^6*g + 2^7*h
P = (1a + 2b + 4c + 8d + 16e + 32f + 64g + 128h) / Index
Now we want P to be integer, so do modulo (let's say Index is 5 for example)
P = (1a + 2b + 4c + 3d + 1e + 2f + 4g + 3h) / 5
P = (1(a+e) + 2(b+f) + 4(c+g) + 3(d+h)) / 5

所以现在我们可以说，每个位掩码，其设置位的总和乘以模 5 以上的系数为 0，它是一个有效的 P * 索引，然后我们可以通过简单的除法找到 P。希望你能理解我。

但问题是我不知道如何将其扩展到多个索引结果对，而且我真的不知道现在该怎么办。

Answer 1

您可以使用 z3 等 SMT 求解器来实现此目的。您可以为您想要计算的所有内容创建变量，然后对其设置约束。在这里，我假设您可以选择的值是 p 和索引，您的问题仍然不清楚。完全未经测试的示例：

void solve(const std::vector<uint64_t>& subs, uint64_t mask) {
    using namespace z3;
    context c;
    solver s(c);
    expr p = c.bv_const("p", 64);
    std::vector<expr> indices;
    for (int i = 0; i < subs.size(); ++i)
        indices.push_back(c.bv_const(("indices_" + std::to_string(i)).c_str(), 9));

    for (int i = 0; i < subs.size(); ++i)
        s.add((p * zext(indices[i], 64 - 9) & mask) == subs[i]);

    if (s.check() == sat) {
        model m = s.get_model();
        uint64_t p_result = m.eval(p).get_numeral_uint64();
        std::vector<uint16_t> indices_result;
        for (int i = 0; i < subs.size(); ++i)
           indices_result.push_back(m.eval(indices[i]).get_numeral_uint64());
        // do something with the result
    } else {
        // no solution
    }
}