如何优雅地找到一个简单的mod函数的不动点？

Question

这里有一个函数，用C语言表示是：

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

然后遇到一个难题：如何找到它所有的不动点？

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

Answer 1

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 and/or x+2^i（如果我们想要更精确，当我们说 "solution").

时，我们只查看 0, ..., modulus size - 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：此代码找到所有解决方案。在这种情况下，只有一个，但对于更通用的参数，可能会有多个。

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

Answer 2

让我们使用 Z3 solver:

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

结果是'#x08f2cab1' = 150129329.

Answer 3

因为位置 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

如何优雅地找到一个简单的mod函数的不动点？

How to find the fixed points of a simple mod function elegantly?

c++

algorithm

math

fixed-point-iteration