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 = g(A,y) 使得 x = g(A, f(A,x)) 对于所有“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 = 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.

Answer 2

解决方案在此处给出（http://en.wikipedia.org/wiki/Linear_congruence_theorem），并演示了如何使用扩展欧几里得算法来找到解决方案。

模函数通常没有反函数，但有时您可以找到一组映射到给定 y 的 x。

Answer 3

Accipitridae、Glenn 和 Jeff Moser 在他们之间找到了答案，但值得多解释一下为什么不是每个数字在 mod 4294967295 下都有逆元。原因是 4294967295 不是素数；它不是质数。 它是五个因素的乘积：3 x 5 x 17 x 257 x 65537。一个数字x 在 mod m 当且仅当 x 和 m 是 互质，因此任何作为这些因子的倍数的数字都不能在您的函数中存在逆函数。

这就是为什么为此类 PRNG 选择的模数通常是素数的原因。

Answer 4

您需要计算 A mod ((2^N) - 1) 的倒数，但在给定模数的情况下，您可能并不总是有倒数。 请参阅有关 Wolfram Alpha 的内容。

请注意，

A = 12343 有逆元 (A^-1 = 876879007 mod 4294967295)，

但 12345 没有逆元。

因此，如果 A 与 (2^n)-1 互质，那么您可以轻松地使用扩展欧几里得算法创建反函数，其中

g(A,y) = F(A^-1, y)，

否则你就不走运了。

更新：针对您更新的问题，您仍然无法在限制范围内获得唯一的逆。 即使您使用 CookieOfFortune 的强力解决方案，您也会遇到类似

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294 的问题。

Answer 5

呃...这是一个可行的方法：

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}