7

我需要一些好的伪随机数生成器，它可以像纯函数一样从其先前的输出中计算出来，而不会隐藏任何状态。在“好”下，我的意思是：

  1. 我必须能够以这样的方式对生成器进行参数化，即2^n使用任何参数（或它们的一些大子集）运行它以覆盖所有或几乎所有介于0和之间的值2^n - 1，其中n是输出值中的位数。

  2. 位的组合生成器输出n + p必须涵盖所有或几乎所有值0，2^(n + p) - 1如果我针对2^n其参数的每个可能组合运行它进行迭代，其中p是参数中的位数。

例如，LCG可以像纯函数一样计算，它可以满足第一个条件，但不能满足第二个条件。假设我们有 32 位 LCG，m = 2^32并且它是常数，我们的p = 64（两个 32 位参数a和c）n + p = 96，所以我们必须从输出中查看三个整数的数据以满足第二个条件。不幸的是，由于输出中奇偶整数的严格交替序列，无法满足条件。为了克服这个问题，必须引入隐藏状态，但这会使函数不纯并打破第一个条件（长隐藏期）。

编辑：严格来说，我想要按p位参数化并具有完整n位状态的函数系列，每个函数都以独特的“随机”方式生成所有可能的二进制位字符串p + n，而不仅仅是连续递增(p + n)-bit int。选择该独特方式所需的参数化。

我想要的太多了吗？

4

2 回答 2

2

您可以使用具有固定密钥的任何分组密码。要生成下一个数字，请解密当前数字，将其递增，然后重新加密。因为分组密码是 1:1，所以它们必须在重复之前遍历输出域中的每个数字。

于 2010-05-20T20:55:47.390 回答
1

试试LFSR
你所需要的只是原始多项式的列表。
以这种方式生成有限域的周期，生成大小为 2^n-1 的域。但是您可以推广此过程以生成任何带有 k^n-1 周期的内容。

我还没有看到这个实现，但你所要做的就是将数字移动小数 s>n 其中 gcd(s,2^n-1) == 1。gcd 代表最大公约数

于 2010-05-20T19:53:53.223 回答