algorithm - 疑似乱数の有限シーケンスに基づいてシードの近似値を取得することは可能ですか?

Question

たとえば、652,328,1,254 などのシリーズを形成するいくつかの数字があり、たとえば、次の場合にシードを取得したいとします。

srand(my_seed);

すべての数値が同じ順序で表示される場合、元の数列に対する有界誤差である種の近似値が得られます。

Answer 1

疑似乱数生成に使用されるアルゴリズムに依存します。アルゴリズムが単純な線形合同ジェネレーターである場合、シードを取得することは、線形モジュラー方程式を解くだけの問題です (解は一意ではない可能性がありますが、そのようなジェネレーターはメモリレスであるため、一意ではないことに注意してください)。案件）。

アルゴリズムがより複雑な場合、これは不可能な場合があります。

C 標準ライブラリで使用されるアルゴリズムは標準によって制限されていないため、プラットフォームによって実装が異なる場合があることに注意してください。

Answer 2

この質問をチェックしてください。

rand()ジャスティンが言うように、生成された数値のシーケンスがある場合、線形合同ジェネレーター (多くの場合実装されています)をバックトラックすることが可能です。問題は、前の値のどれが元のシードであるかを知ることだと思います...

Answer 3

暗号化 PRNG の定義は、この正確なプロパティが計算上実行不可能なものです。ただし、前述のように、これが可能なはるかに弱い (そしてはるかに高速な) PRNG があります。したがって、それはアルゴリズムに依存します。

Answer 4

一般に、エラーをバインドすることはできません。アルゴリズムが機能するか機能しないかのどちらかです。この理由は、妥当な誤差範囲が明らかに RAND_MAX よりもはるかに小さいためです。これは、下位ビットが上位ビットほどランダムではないことを意味します。しかし、優れた PRNG は、すべてのビットが均等にランダムであることを確認します。

RNG アルゴリズムの遅いが数学的に正しい例を考えてみましょう。

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

出力シーケンスと前の の間に有意な相関関係が見つかった場合state、AES アルゴリズムは壊れていると見なす必要があります。