可逆伪随机序列发生器

Question

我想要某种方法来创建一个相当长的随机数序列,我可以向前和向后翻转.就像具有"下一个"和"上一个"按钮的机器一样,它会为您提供随机数字.

像10位分辨率(即0到1023范围内的正整数)就足够了,并且序列> 100k.这是一个简单的游戏类型的应用程序,我不需要加密强度随机性或任何东西,但我希望它感觉相当随机.我有可用的内存有限,所以我不能只生成一大块随机数据并通过它.我需要在"交互时间"中获取数字 - 我可以轻松地花几个小时思考下一个数字,但不是比这更舒服.最终它将在某种微控制器上运行,可能只是一个Arduino.

我可以用简单的线性同余生成器(LCG)来做到这一点.前进很简单,向后退我必须缓存最近的数字并间隔存储一些点,这样我就可以从那里重新创建序列.

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

或者也许我可以使用某种哈希函数来填充索引号？我要先尝试一下.

还有其他想法吗？

Answer 1

我在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中的相对素数,我们可以通过使用扩展的euclid算法找到逆.

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和a,则算法的周期为2 ^ 64

履行

如果有人感兴趣的话,我做了这个算法的头文件实现.

Answer 2

使用非常简单的对称加密算法是最简单的方法之一.每个随机数都是通过用一些固定密钥加密前一个随机数来形成的,然后向后解密.

您可以在http://en.wikipedia.org/wiki/RC4查看RC4代码.您可以使用更小的密钥计划来使其完全适合arduino.

Answer 3

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

AES是可用的几乎每一个新的系统上在那里,而且是闪电快.