A*X MOD(2 ^ N)-1的逆

Question

给定函数y = f(A,X):

unsigned long F(unsigned long A, unsigned long x) {
    return  ((unsigned long long)A*X)%4294967295;
}

对于'x'的所有值,我如何找到反函数x = g(A,y)使得x = g(A,f(A,x))？

如果f()对于'x'的所有值都不可逆,那么最接近逆的是什么？

(F是一个过时的PRNG,我试图理解一个人如何反转这样的功能).

• 更新
  如果A是(2 ^ N)-1的相对素数,那么g(A,Y)只是f(A-1,y).
  如果A不是相对素数,则y的范围受到约束......如果限制在该范围内,g()是否仍然存在？

Answer 1

您需要扩展欧几里德算法.这样就可以得到R和S.

gcd(A,2^N-1) = R * A + S * (2^N-1).

如果gcd是1则R是A的乘法逆.那么反函数是

g(A,y) = R*y mod (2^N-1).

确定,这里是一个更新的情况下G =最大公因数(A,2 ^ N-1)不为1在这种情况下

R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1).

如果y是由函数f运算则y是整除G.因此,我们可以由G除以上述公式,并得到一个方程式模(2 ^ N-1)/ G.因此,这套解决方案是

  x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.

Answer 2

这里给出了解决方案(http://en.wikipedia.org/wiki/Linear_congruence_theorem),并演示了如何使用扩展的欧几里德算法来找到解.

模数函数通常没有反函数,但有时你可以找到一组映射到给定y的x.