尝试编写 8 位的可逆 PRNG，而不是密码

Question

我正在尝试构建一个字节 PRNG，其中我可以获取一组字节（例如 10 或 15 字节）并返回一个种子列表，该种子列表将产生该字节列表。我不关心密码学，但它必须大致均匀分布，它必须击中所有可能的 2^8 组合，并且它必须偶尔能够重复一个数字而不被卡住。

问题是，我读过的大多数算法要么使用密码，这可能意味着它不允许重复，要么使用模数或非循环移位，这会导致损失并使反转函数充其量是不切实际的。此外，如果算法使用计数，则很难向后工作，因为字节列表输入不知道生成时内部 PRNG 的计数器是什么。

我意识到我正在寻找的是一种鱼与熊掌兼得的情况，但我想确保我没有错过其他解决方案。

在搜索时，我发现 这篇文章 具有类似的要求。我是用 C# 编写的，但实际上，语法并不重要。

我尝试自己编写的每个算法都是密码，因此无法重复和/或分布不均匀。我使用了反转、循环移位和种子掩蔽。

Answer 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的一致性。

Answer 2

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

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