2

给定一个函数 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(·) 是否仍然存在？
4

5 回答 5

8

您需要扩展欧几里得算法。这给了你 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.
于 2009-05-21T19:38:44.583 回答
6

此处给出了解决方案( http://en.wikipedia.org/wiki/Linear_congruence_theorem )，其中包括如何使用扩展欧几里得算法来找到解决方案的演示。

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

于 2009-05-21T19:56:43.593 回答
3

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

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

于 2009-05-21T19:59:14.370 回答
2

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

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
于 2009-05-21T19:32:51.850 回答
2

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

于 2009-05-21T19:34:28.523 回答