25

ある種の方法で、かなり長い乱数のシーケンスを作成して、前後に反転できるようにしたいと思います。「次へ」と「前へ」のボタンがあるマシンのように、それはあなたに乱数を与えるでしょう。

10ビットの解像度（つまり、0〜1023の範囲の正の整数）のようなもので十分であり、10万を超える数値のシーケンスです。シンプルなゲームタイプのアプリ用で、暗号化強度のランダム性などは必要ありませんが、かなりランダムに感じてもらいたいです。ただし、使用できるメモリの量には限りがあるため、ランダムデータのチャンクを生成してそれを処理することはできません。「インタラクティブな時間」で数値を取得する必要があります。次の数値について考えるのに数ミリ秒を簡単に費やすことができますが、それ以上の快適さはありません。最終的には、ある種のマイクロコントローラー、おそらくArduinoで実行されるようになります。

単純な線形合同法（LCG）でそれを行うことができました。前進するのは簡単です。後退するには、最新の数値をキャッシュし、そこからシーケンスを再作成できるように、間隔を置いていくつかのポイントを格納する必要があります。

しかし、おそらく、前進と前進の両方を可能にする疑似ランダムジェネレーターがありますか？2つの線形フィードバックシフトレジスタ（LFSR）を接続して、異なる方向に回転させることは可能であるはずです。

それとも、ある種のハッシュ関数を使用してインデックス番号を文字化けさせるだけでうまくいくでしょうか？最初に試してみます。

他のアイデアはありますか？

4

7 に答える 7

26

私はtigsourceフォーラムで非常によく似た質問をしました。

ハッシュ

少なくともゲームでは、ハッシュ関数はおそらくあなたが望むことをすることができます。あなたはこのようにそれを行うことができます

class ReversibleRNG {
    int x;
public:
    ReversibleRNG(int seed) : x(seed) {}
    int next(){return yourFavoriteHash(++x);}
    int prev(){return yourFavoriteHash(--x);}
};

可逆線形合同法（lcg）

複数の人が指摘しているように、lcgは確かにリバーシブルです。lcgでは、次の状態は次のように計算されます。

x = (a * prevx + c) mod m

これを並べ替えることができます：

x ≡ a * prevx + c (mod m)
x - c ≡ a * prevx (mod m)

aとmは、lcgで互いに素になるように選択されているため、拡張ユークリッドのアルゴリズムを使用して逆数を見つけることができます。

ainverse = extEuclid(a, m).x;
ainverse * (x - c) ≡ ainverse * a * prevx (mod m)
ainverse * (x - c) ≡ prevx (mod m)

つまり、

prevx = ainverse * (x - c) mod m

mを慎重に選択すると、アルゴリズムの周期は2^64になります。

実装

誰かが興味を持った場合に備えて、このアルゴリズムのヘッダーのみの実装を行いました。

于 2013-05-19T01:11:17.640 に答える
11

非常に単純な対称暗号化アルゴリズムを使用することは、これを行う最も簡単な方法の1つです。各乱数は、前の乱数を固定キーで暗号化するだけで形成され、逆方向に進むには復号化するだけです。

あなたはRC4-コードをhttp://en.wikipedia.org/wiki/RC4で見るかもしれません。はるかに小さい鍵スケジュールを使用して、すべてをarduinoに適合させることができます。

于 2010-05-28T13:58:50.980 に答える
6

1, 2, 3, ...任意の暗号と任意のキーを使用してシーケンスを暗号化します。

AESは、最近のほぼすべてのシステムで利用可能であり、非常に高速です。

于 2010-05-28T14:00:47.947 に答える
2

整数の昇順でビットの順序を逆にするだけです。例（8ビットの解像度）：

  • 0 <=> 0
  • 1 <=> 128
  • 2 <=> 64
  • 3 <=> 192
  • 4 <=> 32
  • 等

シーケンス内を前後に移動するのは非常に簡単で、暗号化やハッシュ関数を呼び出すよりもはるかに高速です。また、可能な限り長いシーケンスを生成するという利点もあります。

暗号的に安全ではありません。生成された値の散布図を次に示します（これも8ビットの解像度で）。

の散布図

パターンは「ランダム」である可能性がありますが、すぐに確認できます。

于 2017-01-18T19:47:27.917 に答える
2

線形合同法が十分に良い場合は、それを使用してください。それらは簡単に元に戻すことができます。ポイントは、リバースジェネレーターもLCGであるということです。LCGは、任意の方向（順方向および逆方向）に非常に高速にスキップすることもできます。

詳細については、The Art of ComputerProgramming-Volume2をご覧ください。

特に、TAOCPのセクション3.2.1 Page 10式6〜8および演習5でも、望ましい結果が得られます。演習を解決できない場合は、簡単に解決策を見つけることができます。たとえば、ここにあります。

于 2017-05-02T13:02:40.817 に答える
0

@BlueRajaは、シーケンスのランダムまたは時間ベースの開始で「カウンターモード」でAESを使用する必要があることに同意しますが、AESは、埋め込まれた状況では使用できないか、実行できない可能性があります。

可逆PRNGを構築する方法について説明しているこの興味深い論文を見つけました。たった10ページで、たくさんのコードサンプルがあります。AESが機能しない場合は、試してみてください。

于 2010-05-28T14:14:20.260 に答える
0

LCGを使用して逆方向に進むこともできます。これは、モジュラスを法とする乗数の逆数と適切な増分を使用する別のLCGです。

少数の場合は、ブルートフォースを使用して逆数を検索できます。一般に、拡張GCDアルゴリズムを使用して計算できます。

あなたのゲームが厳密に楽しみのためであり、いかなる種類の利害関係もない場合を除いて、他の人が提案したAESアプローチなど、暗号的に安全なものを選択します。LCGやその他の線形乱数ジェネレーターは、インテリジェントな敵に耐えることができません。

于 2010-05-29T12:45:13.993 に答える