1

I'm trying to build a PRNG of bytes where I can take a set of bytes (say, 10 or 15 bytes) and return a list of seeds that would yield that list of bytes. I'm not concerned about cryptography, but it must be roughly uniformly distributed, it must hit all possible 2^8 combinations and it must occasionally be able to repeat a number without getting stuck.

The problem is, most algorithms I've read about either use ciphers, which probably means it won't allow repeats, or they use modulus or non-circular shifts that induce loss and make reversing the function impractical at best. Also, if the algorithm used counting, it would be hard to work backwards as the byte list input would not know what the internal PRNG's counter was at the generation time.

I realize what I'm looking for is a have-your-cake-and-eat-it-too situation, but I wanted to make sure there wasn't another solution I was missing.

While searching I came across this post which has similar requirements. I was writing in C# but really, syntax is not important.

Every algorithm I've tried to write myself has been a cipher and thus failed to repeat and/or not uniform in distribution. I used inversion, circular shifting and seed masking.

4

2 回答 2

1

这行得通吗？

#include <stdio.h>

int seed = 1;

int next() {
    seed = 1664525*seed + 1013904223;
    return (seed & 0xff) ^ (seed>>8 & 0xff) ^ (seed>>16 & 0xff) ^ (seed>>24 & 0xff);
}   

int main() {
    int i;
    for(i = 0; i < 1000; i++) {
        printf("%d\n", next());
    }   
}

由于它基于具有完整周期的线性同余生成器（LCG），因此每个字节最终将由每个种子生成。好像有重复。它继承了底层 LCG 的一致性。

于 2012-01-13T09:38:44.433 回答
0

我的顾问已将 PRNG（基于 L'Ecuyer 的 clcg4）修改为可逆的，以支持我们小组的 HPC 模拟工作。您可以在此处阅读这些内容。

基本上，它“撤消”已经完成的操作，并且正如您可能已经猜到的那样，这可能需要“撤消”随机数生成，然后沿着不同的计算路径再次重新生成这些相同的值。您可以在此处和此处查看此代码。这是 BSD 许可的代码。

于 2013-01-21T23:04:02.737 回答