给定一个RNG算法和一系列数字，是否可能确定将产生该序列的种子是什么? [英] Given a RNG algorithm and a series of numbers is it possible to determine what seed would produce the series?

问题描述

该代码位于目标C中，但是即使您不知道目标C，如果仔细查看它，它也是可以理解的.基本上，它是一个RNG对象，您实例化了一个新实例，如果需要，可以设置种子并开始抓取随机数.

The code is in Objective C but it should be understandable if you look it over even if you don't know Objective C. Basically its a RNG object, you instantiate a new instance, set the seed if you want and start grabbing random numbers.

那么是否可以回溯给定的一系列数字来确定用于生成数字的种子?我猜想任何给定的算法都不能仅生成任何随机数集，或者可以吗?

So is it possible to backtrack a given series of numbers to determine the seed used to generate the numbers? I'm guessing any given algorithm can't generate just any random set of numbers though, or can it?

说我要执行以下操作:

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.是否有办法知道该算法是否有效，以及种子是什么?

Which gives me the sequence 10, 10, 8, 10, 2, 10, 9, 9, 7, 4. Is there some method or algorithm I could use, given the sequence, to get the number 1024? I know thats the valid sequence for the seen 1024, but what is I just make up a sequence... 10, 1, 9, 6, 3, 9, 10, 3, 5, 2. Is there a way to know if that is a valid sequence for this algorithm and if so what the seed is?

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

推荐答案

您发布的代码与

the code you post is basically the same as the openbsd srandom - it's a linear congruential generator that is implemented to avoid rounding (which is why it contains Q).

此处是有关如何破解此类生成器的论文，但它希望完整的输出(不是"between"值)可用.

here is a paper on how to crack such a generator, but it expects the full output (not the "between" value) to be available.

我想您应该能够使用算术运算范围的模数来扩展本文中的方法，以在介于"之间工作(大概需要更多的样本).

i guess you should be able to extend the approach in the paper to work with "between" using arithmetic modulo the range (presumably you would need more samples).

这篇关于给定一个RNG算法和一系列数字，是否可能确定将产生该序列的种子是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！