8

コードは Objective C で書かれていますが、Objective C を知らなくても見れば理解できるはずです。基本的には RNG オブジェクトです。新しいインスタンスをインスタンス化し、必要に応じてシードを設定し、乱数の取得を開始します。

では、与えられた一連の数値をバックトラックして、その数値を生成するために使用されるシードを決定することは可能でしょうか? 私は、特定のアルゴリズムがランダムな数字のセットを生成できないと推測していますか、それともできますか?

私が次のことをするとします：

rng.seed = 1024;
for (int i=1; i<11; i++)
    DLog(@"%lu", [rng randomBetween:0 and:10]);

これにより、シーケンスが得られます10, 10, 8, 10, 2, 10, 9, 9, 7, 4。シーケンスを考慮して、1024 という数字を取得するために使用できる方法またはアルゴリズムはありますか? これが 1024 の有効なシーケンスであることはわかっていますが、シーケンスを構成しているだけです... 10, 1, 9, 6, 3, 9, 10, 3, 5, 2. それがこのアルゴリズムの有効なシーケンスであるかどうかを知る方法はありますか?もしそうなら、シードは何ですか?

RNG.h:

@interface RNG : NSObject
@property (assign) unsigned long seed;
- (unsigned long)random;
- (long)randomBetween: (long)min and: (long)max;
@end

RNG.m:

#define A 16807         /* a relatively prime number -- also M div Q */
#define M 2147483647L   /* 0xFFFFFFFF / 2 */
#define Q 127773L       /* M div A */
#define R 2836          /* M mod A */

@implementation RNG
@synthesize seed = _seed;

- (id)init {
    self = [super init];
    if (self) {
        self.seed = 0;
    }
    return self;
}


- (unsigned long)random {
    self.seed = A * (self.seed % Q) - R * (self.seed / Q);
    if (self.seed > M)
        return (self.seed -= M);
    else if (self.seed)
        return (self.seed);
    else
        return (self.seed = 1L);
}


- (long)randomBetween: (long)min and: (long)max {
    return ([self random] % (max - min + 1) + min);
}


- (void)seed: (unsigned long)new_seed {
    if (new_seed == 0)
        new_seed = 1;
    while (new_seed > M)
        new_seed -= M;

    self.seed = new_seed;
}
@end
4

3 に答える 3

3

あなたが投稿するコードは基本的にopenbsdsrandomと同じです-それは丸めを避けるために実装された線形合同ジェネレーターです（それが含まれている理由Qです）。

これは、そのようなジェネレーターをクラックする方法に関する論文ですが、完全な出力（「間」の値ではない）が利用可能であることを期待しています。

範囲を法として算術演算を使用して、「間」で作業するように論文のアプローチを拡張できるはずです（おそらくより多くのサンプルが必要になるでしょう）。

于 2012-08-16T13:19:23.770 に答える
3

これは「線形合同ジェネレーター」のように見えます。http://en.wikipedia.org/wiki/Linear_congruential_generatorを参照してください。

これらは優れた暗号化セキュリティを提供しないため、シーケンスを生成するシードを計算できるはずです。

于 2012-08-16T08:57:39.603 に答える
0

おそらく最善の策は、シードごとに選択したアルゴリズムによって返される最初の値を持つ配列 (またはディスク ファイル) を作成することです。次に、最初の値に一致するものを検索して、より長い一致を探します。実際、データベース テーブルは素晴らしいものです。gdbm、bsddb、または sqlite が思い浮かびます。

これは、「計算可能ですが...」の問題の 1 つに思えます。IOW、それはできますが、特にきれいではありません。

于 2012-08-16T19:38:21.450 に答える