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、f（A、x））となる逆関数x = g（A、y）をどのように見つけますか？

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

タカ科、グレン、ジェフ・モーザーはそれらの間に答えを持っていますが、mod 4294967295の下ですべての数が逆数になるわけではない理由をもう少し説明する価値があります。理由は、4294967295が素数ではないためです。これは、3 x 5 x 17 x 257 x 65537の5つの因子の積です。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)ますが、モジュラスが与えられた場合、常に逆数になるとは限りません。WolframAlphaでこれを参照してください。

ご了承ください

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 に答える