逆-1関数y = F（A、X）が与えられる

Question

：

Iは、逆関数は、x = G（A、y）を見つけるだろうどの

unsigned long F(unsigned long A, unsigned long x) { 
    return ((unsigned long long)A*X)%4294967295; 
} 

'x'のすべての値に対してx = g（A、f（A、x））？

f（）が 'x'のすべての値に対して可逆でない場合、逆に最も近いものは何ですか？

（Fは古くなったPRNGですが、私はそのような関数をどのように反転させるかを理解しようとしています）。
更新Aは、（2^N）-1と互いに素である場合、G（A、Y）が丁度（-1、Y）は、Fである。

• 
  Aが比較的素数でない場合、yの範囲は制約されます... g（）はその範囲に制限されていてもまだ存在しますか？

Answer 1

あなたはA mod ((2^N) - 1)の逆数を計算する必要がありますが、あなたは常にあなたの弾性率が与えられた逆を持っていない可能性があります。 this on Wolfram Alphaを参照してください。

注

A = 12343は、逆（A^-1 = 876879007 MOD 4294967295）

しかし12345は、逆を持っていない持っていること。

Aは（2^n）は-1とrelatively primeであればこのように、あなたは簡単にExtended Euclidean Algorithmどこ

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

を使用して逆関数を作成することができそうでない場合、あなたは運の出ています。

更新日：更新された質問に答えると、依然として制限された範囲で一意の逆数を得ることができません。 CookieOfFortuneの強力なソリューションを使用しても、

G(12345, F(12345, 4294967294)) == 286331152 != 4294967294のような問題が発生します。

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

Answer 3

Extended Euclidean algorithmが必要です。これはR与え、最大公約数が1である

gcd(A,2^N-1) = R * A + S * (2^N-1). 

場合、RはAの逆数であることをSなどそして、逆関数は、ここでは、

g(A,y) = R*y mod (2^N-1). 

OKですため更新ですyは、次にYはしたがって、我々は分割できG.で割り切れる関数fによって計算した場合はG = GCD（A、2^N-1）は、その場合

R*y mod (2^N-1) = R*A*x mod (2^N-1) = G*x mod (2^N-1). 

1にない場合方程式Gで上の方程式を計算し、（2^N-1）/ Gを法とする方程式を得る。従って解のセットが

Answer 4

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

ある溶液をhere（http://en.wikipedia.org/wiki/Linear_congruence_theorem）与えられ、拡張ユークリッドアルゴリズムが解を見つけるために使用される方法のデモンストレーションを含んでいます。

モジュラス関数は一般に逆関数を持っていませんが、指定されたyにマップされるxのセットを見つけることができます。

Answer 5

Accipitridae、Glenn、Jeff Moserが答えを出していますが、すべての数値がmod 4294967295の逆数になっていない理由を少し説明する価値があります。理由は4294967295が素数ではないことです。それはfive factorsの生成物である：3×5×17×257 X 65537.番号XはMOD Mif and only ifXとM下mutiplicative逆を有しているの倍数であるcoprimeので、任意の数のこれらの要素は、あなたの関数の逆数を持つことはできません。

これは、このようなPRNGに対して選択されたモジュラスが通常プライムである理由です。