这里有一个函数,用C语言表达为:
uint32_t f(uint32_t x) {
return (x * 0x156) ^ 0xfca802c7;
}
然后我遇到了一个挑战:如何找到它的所有不动点?
我知道我们可以测试每个uint32_t
值来解决这个问题,但我仍然想知道是否有另一种更优雅的方法 - 尤其是当uint32_t
变成uint64_t
并且(0x156, 0xfca802c7)
是任意一对值时。
这里有一个函数,用C语言表达为:
uint32_t f(uint32_t x) {
return (x * 0x156) ^ 0xfca802c7;
}
然后我遇到了一个挑战:如何找到它的所有不动点?
我知道我们可以测试每个uint32_t
值来解决这个问题,但我仍然想知道是否有另一种更优雅的方法 - 尤其是当uint32_t
变成uint64_t
并且(0x156, 0xfca802c7)
是任意一对值时。
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[解的数量,模数大小的位数]), 假设我没有出错。因此,除非存在许多许多的不动点,否则它很快。在这种情况下,似乎只有一个。
让我们使用Z3求解器:
(declare-const x (_ BitVec 32))
(assert (= x (bvxor (bvmul x #x00000156) #xfca802c7)))
(check-sat)
(get-model)
'#x08f2cab1' = 150129329.
由于位于位置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
x = x * 0x156 ^ 0xfca802c7
。 - aioobex[0] = (x[0] & a[0]) ^ b[0]
,然后解决x[1] = (x[0] & a[1]) ^ (x[1] & a[0]) ^ b[1]
,以此类推。"等等"部分会很难。 - MooseBoys