•  23-08-2019
  •  | 
  •  

質問

与えられ関数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'?

さな可逆ためのすべての値に'x'、最も近接する逆?

（Fは廃止PRNGないと思うのについて研究していつの反転などの機能)。

  • 更新
    場合には相対的に盛り(2^N)-1g(A,Y)はf(A-1,y).
    がん相対的に盛り、その範囲が大きい場合には、制限...はg()が存在する場合に限られる範囲?
役に立ちましたか？

解決

必要なものを計算するための逆の A mod ((2^N) - 1), がない場合がございます常に逆に考えるヤング率.見 このウォルフラムアルファ.

ご注意

A=12343は逆(A^-1=876879007mod4294967295)

が12345は逆.

このように、場合には 比較的好 (2^n)-1、それが簡単に作成する逆関数用の 拡張ユークリッドアルゴリズム 場所

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

その他いてのデモインのホテルを表示.

更新:お客様に更新、まだ得することはできない独自の逆に制限されます。ご利用の場合でもCookieOfFortuneの力、解決まりにくいなどの問題

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294.

他のヒント

あなたは拡張ユークリッドの互除法を必要とします。これは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).

は[OK]を、ここで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によって上記の式を分割し、式モジュロ（2 ^ N-1）/ Gを得ることができG.で割り切れます。従って解の集合である

  x = R*y/G + k*(2^N-1)/G, where k is an arbitrary integer.

の解を与え こちらの (http://en.wikipedia.org/wiki/Linear_congruence_theorem、を含むように拡張ユークリッドアルゴリズムを見つけるために使われますのソリューション。

モジュラスの機能一般的な逆 機能, ができるものを見つセットのxのは、指定された。

タカ科、グレン、そしてジェフ・モーザーは、それらの間の答えを持っていますが、必ずしもすべての数はMOD 4294967295の下で逆を持っている理由、それはもう少し説明する価値がある理由は4294967295が素数ではないということです。 3×5×17×257 X 65537.番号 X：それは 5因子をの生成物でありますはMODの下mutiplicative逆を持っているの M の場合に限り X との M のある互いに素ので、これらの要因の倍数である任意の数は、あなたの関数に逆を持っていないことができます。

このようのPRNGのために選ばれた弾性率が通常の素数である理由

このです。

え...ここに動作します一つです。

unsigned long G(unsigned long A, unsigned long y)
{
    for(unsigned int i = 0; i < 4294967295; i++)
    {
        if(y == F(A, i)) return i);
    }
}
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top