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

Question

这里有一个函数，用C语言表达为：

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

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

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

- Max Gresham

---

你需要考虑溢出算术来解决方程 x = x * 0x156 ^ 0xfca802c7。 - aioobe

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - TheGreatContini

我认为这个问题会很难。乘法和异或是代数上“不兼容”的操作，而且很难理解这种逻辑。事实上，有些密码和哈希函数依赖于混合加法、乘法和异或（例如TEA、MurmurHash），正是因为它们很难分析。 - Nayuki

我猜你需要将问题分解成位级别。例如，先解决 x[0] = (x[0] & a[0]) ^ b[0]，然后解决 x[1] = (x[0] & a[1]) ^ (x[1] & a[0]) ^ b[1]，以此类推。"等等"部分会很难。 - MooseBoys

我认为你可以通过归纳找到一个可行的算法。我们已经在模2下解决了它。从那里将其提升到模4算法：解决方案模2为1，这意味着只有1和3是模4的可能解。那就是2种可能性。尝试它们，我猜只有一个有效。接下来，通过将（假定的）模4解的一个解提升到模8的两个可能性来进行模8操作，以此类推。这应该有效。现在不在火车上的人可以完成这个算法并将其写得漂亮一些。我认为运行时间将是线性的。 - TheGreatContini

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和/或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：该代码找到了所有的解。在这种情况下，只有一个解，但对于更一般的参数，可能会有多个解。

注意2：运行时间是O(max[解的数量，模数大小的位数]), 假设我没有出错。因此，除非存在许多许多的不动点，否则它很快。在这种情况下，似乎只有一个。

- TheGreatContini

Answer 2

让我们使用Z3求解器：

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

结果是 '#x08f2cab1' = 150129329.

- Shinjikun

---

请问您能否简单解释一下那段神奇代码的工作原理？ - Sayakiss

@Sayakiss，这段代码只包含问题定义。魔法发生在“check-sat”中，它调用了SAT求解器。SAT求解器是一个复杂的程序，你不能用简单的答案描述所有使用的策略。很可能发布者也不理解细节，就像我们大多数人不知道我们选择的语言编译器的详细实现一样。 - CodesInChaos

这篇博客介绍了一个原始的SAT求解器：通过在Python中实现简单的SAT求解器理解SAT。在这个答案中使用的Z3求解器可能支持更多高级策略，以便能够更有效地解决更多问题。 - CodesInChaos

虽然这个问题是一个SAT问题，但Z3几乎肯定会以比调整布尔列表更快的方式工作。事实上，这就是SAT / SMT求解器和逻辑编程语言的美妙之处：您描述问题并使用一个非常精心编写和优化的通用解析器来找到解决方案。 - Shinjikun

严格来说，Z3不是一个SAT求解器。它可以在更多的情况下使用，官方分类是“SMT”求解器。但在这种特定情况下，你确实可以将其作为SAT求解器使用。位向量（例如整数）是布尔值列表。XOR和MUL都可以通过对这些布尔值进行逻辑运算来定义。然后，该方程将其转化为SAT问题，涉及到的布尔值（位数）数量是NPC级别的。 - Shinjikun

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

- sam hocevar