没有隐藏状态,是否有"好"的PRNG生成值？

Question

我需要一些好的伪随机数生成器,它可以像以前的输出中的纯函数一样计算,而不会隐藏任何状态.在"好"下我的意思是:

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.选择独特方式所需的参数化.

我想要太多了吗？

Answer 1

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

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