给定一个函数 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( ) 是否仍然存在？
最佳答案
您需要 Extended Euclidean algorithm .这给你 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 = Gcd(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.
关于c++ - A*X MOD (2^N)-1 的倒数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/894652/