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

您需要计算的倒数 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 2

你需要 扩展欧几里得算法. 。这给你 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 3

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

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

Answer 4

Accipitridae、Glenn 和 Jeff Moser 已经找到了答案，但值得多解释一下为什么不是每个数字在 mod 4294967295 下都有逆元。原因是4294967295不是素数；它是的产品 五个因素:3×5×17×257×65537。一个号码 X mod 下有乘法逆元 米 当且仅当 X 和 米 是 共质, ，因此任何作为这些因子的倍数的数字都不能在您的函数中存在反函数。

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

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);
    }
}