可逆的伪随机序列发生器

我想要一些方法来创build一个相当长的随机数字序列 ,我可以翻转来回 。 就像一台带有“下一个”和“上一个”button的机器,它会给你随机的数字。

像10位分辨率(即在从0到1023的范围内的正整数)就足够了,并且一个> 100k数字的序列就足够了。 这是一个简单的游戏types的应用程序, 我不需要encryption强度随机性或任何东西,但我希望它感觉相当随机。 虽然我有一个有限的内存 ,所以我不能只生成一大块随机数据,并通过它。 我需要在“互动时间”中得到这些数字 – 我可以轻松地花几个小时来思考下一个数字,但是不能轻松得多。 最终它会运行在某种微控制器上,可能只是一个Arduino。

我可以用一个简单的线性同余发生器(LCG)来完成。 向前走是简单的,为了倒退,我不得不caching最近的数字,并间隔存储一些点,所以我可以从那里重新创build序列。

但也许有一些伪随机发生器,让你去前锋和前锋? 应该可以连接两个线性反馈移位寄存器(LFSR)以便在不同的方向上滚动,否?

或者,也许我可以通过使用某种哈希函数篡改索引号? 我要先尝试一下。

任何其他的想法?

我在tigsource论坛上问了一个非常类似的问题 。

哈希

至less在游戏中,哈希函数可能可以做你想要的。 你可以这样做

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 

我们可以重新sorting:

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

由于a和m在lcg中被select为相对的,所以我们可以通过使用扩展的euclidalgorithm来find逆。

 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 

如果仔细selectm和a,algorithm可以有2 ^ 64的周期

履行

如果有人感兴趣,我只做了这个algorithm的头部实现 。

使用一个非常简单的对称encryptionalgorithm是最简单的方法之一。 每个随机数是由一个固定的密钥对前一个密钥进行encryption,然后向后解密。

你可以看看http://en.wikipedia.org/wiki/RC4上的RC4 – Code。 你可以使用一个更小的关键时间表,以适应所有的arduino。

用任何密码和任何密钥encryption序列1, 2, 3, ...

几乎每一个最近的系统都可以使用AES ,而且闪电般快。

只要在递增的整数序列中颠倒位的顺序即可。 例如(8位分辨率):

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

在序列中前后移动非常容易,而且比调用encryption或散列函数要快得多。 它也有产生最长可能序列的好处。

这绝对不是密码安全的。 这里是生成值的散点图(同样是8位分辨率):

散点图“随机”生成的值

你可以很容易地看到模式,虽然它可能是“随机”足够你。

如果线性同余发生器足够好使用它。 他们很容易扭转。 关键是反向发电机也是一个LCG。 LCG也可以非常快地向任何方向(向前和向后)跳跃。

细节可以在“计算机编程艺术 – 第二卷”中find

特别是第3.2.1节和TAOCP第6-8节的练习5给出了预期的结果。 如果你不能解决这个问题,你可以很容易地find答案,例如这里

虽然我同意@BlueRaja,你应该在“计数器模式”中使用AES,并且随机或基于时间的序列启动,但AES可能无法在您的embedded式环境中使用或不可行。

我find了这个有趣的论文 ,讨论如何build立一个可逆的PRNG; 它只有10页,并有大量的代码示例。 试一试,如果AES不适用于你。

你也可以用LCG后退,它只是另一个LCG,使用乘法器模数的倒数和一个合适的增量。

对于你的小数字,你可以使用蛮力来search逆,一般来说,它可以用一个扩展的GCDalgorithm来计算。

除非你的游戏只是为了好玩,不涉及任何types的赌注,否则我会select密码保密的东西,比如其他人build议的AES方法。 LCG和其他线性随机数发生器不能承受智能对手。