11

这是一个函数，用 C 表示为：

uint32_t f(uint32_t x) {
    return (x * 0x156) ^ 0xfca802c7;
}

然后我遇到了一个挑战：如何找到它的所有不动点？

我知道我们可以测试每个uint32_t值来解决这个问题，但我仍然想知道是否有另一种更优雅的方法 - 特别是当uint32_t成为uint64_t并且(0x156, 0xfca802c7)是任意一对值时。

4

3 回答 3

15

Python代码：

def f(x, n):
    return ((x*0x156)^0xfca802c7) % n


solns = [1]  # The one solution modulo 2, see text for explanation
n = 1
while n < 2**32:
    prev_n = n
    n = n * 2
    lifted_solns = []
    for soln in solns:
        if f(soln, n) == soln:
            lifted_solns.append(soln)
        if f(soln + prev_n, n) == soln + prev_n:
            lifted_solns.append(soln + prev_n)
    solns = lifted_solns

for soln in solns:
    print soln, "evaluates to ", f(soln, 2**32)

输出：150129329 计算结果为 150129329

算法背后的想法：我们试图找到x XOR 0xfca802c7 = x*0x156 modulo n，在我们的案例中n=2^32。我这样写是因为右边是一个简单的模乘法，它与左边的表现很好。

我们将要使用的主要属性是将解决方案归x XOR 0xfca802c7 = x*0x156 modulo 2^(i+1)约为 的解决方案x XOR 0xfca802c7 = x*0x156 modulo 2^i。另一种说法是，一个解决方案x XOR 0xfca802c7 = x*0x156 modulo 2^i转换为一个或两个解决方案模数2^(i+1)：这些可能性是x和/或x+2^i（如果我们想要更精确，我们只查看 0，...，模数大小之间的整数 - 1 当我们说“解决方案”时）。

我们可以很容易地解决这个问题，因为i=1:x XOR 0xfca802c7 = x*0x156 modulo 2^1与 相同x XOR 1 = x*0 mod 2，这意味着x=1是唯一的解决方案。从那里我们知道只有 1 和 3 是可能的解模2^2 = 4。所以我们只有两个可以尝试。事实证明，只有一个有效。这就是我们当前的模 4 解决方案。然后我们可以将该解决方案提升到模 8 的可能性。等等。最终我们得到了所有这样的解决方案。

备注1：此代码找到所有解决方案。在这种情况下，只有一个，但对于更一般的参数，可能不止一个。

Remark2：假设我没有出错，运行时间为 O(max[解决方案数，模数大小])。所以它很快，除非有很多很多的固定点。在这种情况下，似乎只有一个。

于 2016-05-04T07:18:27.477 回答
5

让我们使用Z3 求解器：

(declare-const x (_ BitVec 32))
(assert (= x (bvxor (bvmul x #x00000156) #xfca802c7)))
(check-sat)
(get-model)

结果是'#x08f2cab1' = 150129329.

于 2016-05-04T07:33:44.733 回答
0

由于位置处的输入位n仅影响位置处的输出位，≥ n因此您知道可以通过选择第一位，然后是第二位等来找到解决方案。

以下是如何在 C++ 中为 64 位整数解决它（当然它也适用于 32 位整数）：

#include <cstdint>
#include <cstdio>

uint64_t f(uint64_t x) {
    return (x * 0x7ef93a76ULL) ^ 0x3550e08f8a9c89c7ULL;
}

static void search(uint64_t x, uint64_t bit)
{
    if (bit == 0)
    {
        printf("Fixed point: 0x%llx\n", (long long unsigned)x);
        return;
    }

    if (f(x + bit) & bit) search(x + bit, bit << 1);
    if ((f(x) & bit) == 0) search(x, bit << 1);
}

int main()
{
    search(0x0, 1);
}

有了这个输出：

Fixed point: 0xb9642f1d99863811
于 2016-05-04T11:55:02.747 回答