如何优雅地找到一个简单的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和/或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(最大值[解决方案数量,模数大小(以位为单位)],假设我没有出错.所以除非有很多很多固定点,否则它很快.在这种情况下,似乎只有一个.

Answer 2

让我们使用Z3求解器:

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

结果是 '#x08f2cab1' = 150129329.