消除线性伪随机数生成器中的线性缺陷：新方法与测试

"Scrambled Linear Pseudorandom Number Generators-计算机科学" 线性伪随机数生成器（Linear Pseudorandom Number Generators, LPRNGs）在计算机科学领域广泛应用，主要得益于它们的高速运算能力、易于构建大状态空间的生成器以及可证明的理论性质。然而，这类生成器存在线性特征的问题，这会导致它们在诸如二进制秩（binary-rank）和线性复杂度测试等与线性相关的统计测试中表现不佳。 论文的作者David Blackman和Sebastiano Vigna分别来自澳大利亚和意大利的研究机构，他们对这一问题进行了深入研究。他们提出，线性生成器的线性特征可能导致在统计上观察到的偏差，这些偏差可能会影响依赖于随机性的计算的准确性和可靠性。 首先，作者介绍了两种新的精心设计的线性变换。这些变换旨在拥有良好的统计特性，同时能高效地在超标量处理器上编程，甚至可以直接集成到硬件中。这种优化旨在提高生成器的性能，减少因线性结构导致的统计缺陷。 其次，他们描述了一种新的测试方法，用于检测汉明重量（Hamming weight）的依赖性。这种方法可以发现现有生成器中，尤其是线性生成器中的微妙且之前未被识别的偏斜。汉明重量是指一个数字中“1”的个数，这个测试可以帮助识别那些可能导致错误结果的潜在模式。 最后，作者提出了若干种“扰动器”（scramblers），即应用于状态数组的非线性函数。这些非线性函数可以减少或消除线性特征，从而改善生成器的随机性。通过将线性变换与非线性扰动器相结合，可以创建出既快速又统计上更可靠的伪随机数生成器。 这篇论文关注的是如何通过改进线性生成器的设计，增强其统计质量，确保在各种计算任务中生成的伪随机数更接近真正的随机性。这对于密码学、模拟、统计建模和其他依赖随机数生成的领域具有重要意义。通过引入高效的线性变换和非线性扰动策略，研究人员可以进一步提升现有LPRNGs的性能，降低由于线性结构引起的潜在问题。