可逆伪随机序列发生器

Question

我想要某种方法来创建一个相当长的随机数序列()，可以来回遍历，。就像一台有“下一步”和“先前”按钮的机器，它会给出随机数。

大约10位分辨率(即从0到1023范围内的正整数)就足够了，而且序列的数目也是>100 k。这是一个简单的游戏类型的应用程序，，我不需要加密-强度随机性或任何东西，但我希望它感觉相当随意。不过，我有一个有限的内存可用，所以我不能只生成一块随机数据并遍历它。我需要在“互动时间”中得到数字--我可以轻松地花几分钟思考下一个数字，但不会比这更舒服。最终，它将在某种微控制器上运行，可能只是一个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中被选择为相对素数，所以我们可以用扩展的欧几里德算法来求逆。

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

使用非常简单的对称加密算法是最简单的方法之一。每个随机数都是通过使用一些固定密钥加密前一个随机数而形成的，然后向后退，您只需解密。

您可以查看RC4 -代码在http://en.wikipedia.org/wiki/RC4.您可以使用一个小得多的关键时间表，以使它适合在一个arduino。

Answer 3

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

AES几乎可以在最近的每一个系统上使用，而且速度很快。