有没有隐藏状态的“好”PRNG生成值？

 

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

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

  • 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位二进制串，而不仅仅是连续递增(p + n) -位int。 参数化需要选择这种独特的方式。

    我想要太多吗？

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

    试试LFSR
    所有你需要的是本原多项式列表。
    以这种方式生成有限域的周期，生成大小为2 ^ n-1的域。 但是你可以概括这个过程来产生任何白色的k ^ n-1。

    我没有看到这个实现，但你必须实现的是将数字移动到小数字s> n其中gcd（s，2 ^ n-1）== 1. gcd代表最大公约数

    链接地址: http://www.djcxy.com/p/963.html

    上一篇: Is there "good" PRNG generating values without hidden state?

    下一篇: CSG operations on implicit surfaces with marching cubes