揭秘随机数生成器：从原理到随机性检测（C/C++代码实现）
在现代科技的各个角落，随机数生成器都扮演着不可或缺的角色。从保障信息安全的密码学，到模拟复杂系统行为的仿真技术，再到为玩家带来惊喜与挑战的游戏开发，随机数生成器的身影无处不在。
在密码学领域，随机数用于生成加密密钥、初始化向量等关键元素。以常见的 AES 加密算法为例，密钥的随机性直接决定了加密的强度。如果密钥可预测，攻击者就有可能通过分析密钥规律来破解加密信息，导致数据泄露。而一个高质量的随机数生成器能够生成不可预测的密钥，大大增加了破解的难度，为信息安全保驾护航。
模拟仿真也是随机数生成器的重要应用场景。在交通流量模拟中，为了真实反映车辆的行驶行为，需要借助随机数来模拟车辆的到达时间、行驶速度、换道概率等因素。比如，通过生成符合一定概率分布的随机数来决定某一时刻路段上车辆的数量，以及车辆之间的间距，这样可以更准确地预测交通拥堵情况，为交通规划和管理提供有力支持。
游戏开发更是离不开随机数。以角色扮演游戏为例，玩家打怪掉落装备的过程就依赖于随机数来实现概率控制。不同品质装备的掉落概率可以通过随机数生成器来设定，让玩家在游戏中充满期待和惊喜。此外，游戏中的随机事件，如野外遭遇隐藏 BOSS、触发特殊任务等，也是通过随机数来实现的，这大大增加了游戏的趣味性和重玩性。
正因为随机数生成器在如此多的关键领域发挥着重要作用，确保其生成的随机数具有良好的随机性就显得尤为重要。如果随机数不够随机，在密码学中可能导致加密被破解，在模拟仿真中可能得出错误的结论，在游戏中可能破坏游戏的公平性和趣味性。所以，对随机数生成器的随机性进行检测，是保障这些应用领域正常运行和发展的关键步骤。
随机数生成器的类型与工作原理
（一）真随机数生成器（TRNG）
真随机数生成器（TRNG）是一种利用自然物理现象来生成随机数的设备或系统。它的核心原理是基于自然界中那些真正不可预测的过程，比如热噪声、量子效应、放射性衰变等。这些物理现象天生就具有不确定性，不受任何确定性算法或规则的控制，这使得 TRNG 能够产生真正意义上的随机数。
以热噪声为例，在电子元件中，由于电子的热运动，会产生一种随机的电信号波动，这就是热噪声。这种噪声的幅度和相位都是完全随机的，没有任何规律可循。TRNG 通过专门的电路来采集和放大这种热噪声信号，然后经过一系列的处理，将其转换为数字形式的随机数输出。
量子效应也是 TRNG 常用的物理现象之一。量子力学中的一些特性，如量子纠缠、量子隧穿等，都表现出了内在的随机性。例如，在量子纠缠实验中，一对纠缠的量子粒子，无论它们相隔多远，当对其中一个粒子进行测量时，另一个粒子的状态会瞬间发生变化，而且这种变化是完全随机的，无法提前预测。利用这种特性，科学家们开发出了量子随机数生成器，能够生成高质量的随机数。
TRNG 生成的随机数具有极高的随机性和不可预测性，这是它最大的优势。在对安全性要求极高的密码学领域，TRNG 生成的随机数可以用于生成加密密钥，确保加密的安全性。因为这些随机数的不可预测性，使得攻击者几乎无法通过分析密钥来破解加密信息。
不过，TRNG 也存在一些局限性。它的生成速度相对较慢，这是由于物理过程本身的限制，无法像伪随机数生成器那样快速地生成大量的随机数。而且，TRNG 对环境条件比较敏感，比如温度、湿度、电磁干扰等环境因素的变化，都可能影响到物理现象的随机性，进而影响随机数的质量。此外，TRNG 通常需要专门的硬件设备来实现，这增加了成本和复杂性。
（二）伪随机数生成器（PRNG）
伪随机数生成器（PRNG）则是基于确定性算法来生成看似随机的数字序列。虽然它生成的随机数在统计学上表现出一定的随机性，但本质上它们是由确定性的数学公式或算法产生的。只要初始条件（通常是一个称为 “种子” 的值）相同，PRNG 就会生成完全相同的随机数序列。
常见的 PRNG 算法有线性同余生成器（LCG）、梅森旋转算法（MT）和 XOR 移位生成器等。线性同余生成器是最古老、最简单的 PRNG 之一，它的算法公式为：Xn+1=(aXn+c)mod mX_{n+1}=(aX_n + c)\mod mXn+1=(aXn+c)modm 。在这个公式里，XnX_nXn代表当前的随机值，aaa是乘数，ccc是增量，mmm是模数 。通过不断迭代这个公式，就可以生成一系列的随机数。LCG 的优点是实现非常简单，计算速度也很快，在一些对随机数质量要求不高的场景，比如简单的游戏开发中模拟一些随机事件，它可以快速生成大量随机数来满足需求。但它的统计性质较差，周期相对较短，如果参数选择不当，生成的随机数序列可能会出现明显的规律性，因此不太适合对随机性要求严格的密码学应用。
梅森旋转算法（MT）以其超长的周期而闻名，它的周期大约为219937−12^{19937}-1219937−1 。MT 算法基于矩阵线性递归的构造方法，通过巧妙的数学设计，使得生成的随机数在高维空间中也能保持良好的均匀分布特性。在科学计算、模拟仿真等对随机数质量要求较高的领域，MT 算法被广泛应用。比如在金融风险评估的蒙特卡洛模拟中，需要大量高质量的随机数来模拟各种市场情况，MT 算法就能够很好地满足这一需求，为模拟提供可靠的随机数序列，帮助分析师更准确地评估风险。
XOR 移位生成器利用异或（XOR）和位移等位运算来产生随机数序列。它的算法通常是通过对几个内部状态变量进行位运算来更新状态，并生成新的随机数。例如，常见的 XOR 移位算法会对状态变量进行左移、右移操作，然后再进行异或运算，以此来生成看似随机的结果。XOR 移位生成器的优点是计算简洁高效，速度远超许多其他 PRNG，在一些对计算效率要求较高，对随机数统计性质要求相对较低的场景中，如一般的游戏特效实现、简单的数据采样等，它能够快速生成足够的随机数来满足应用需求。不过，它的统计性质略逊于 MT 算法，在对随机性要求极高的场合，可能不太适用 。
随机性的概念与衡量标准
（一）随机性的定义
在数学和计算机领域，随机性是指一系列事件或结果中不存在可预测的模式或顺序。想象一下，你在抛硬币，每次抛出的结果是正面还是反面，完全没有规律可循，这就是一种简单的随机现象。在计算机中，随机数生成器的目标就是生成这样看似毫无规律的数字序列。真正的随机性在现实世界中很难完全实现，尤其是在计算机这种遵循特定指令运行的确定性系统里。不过，我们可以通过一些巧妙的算法和物理现象，尽可能地逼近随机性，以满足不同应用场景的需求。
（二）熵的概念
熵是一个在信息论中用来衡量系统随机性程度的重要概念，简单来说，熵值越高，就意味着系统的随机性越强。我们可以把熵理解为对不确定性的一种量化。比如说，在一个只有两种可能结果（且这两种结果出现概率相等）的系统中，它的熵就比较高，因为我们很难预测到底会出现哪种结果；而如果一个系统总是出现相同的结果，那它的熵就很低，因为结果完全确定，没有什么不确定性。
在信息论里，香农熵是一种常用的度量随机变量可能取值的平均不可预测性的方法，其计算公式为H(X)=−sumi=1np(xi)log2p(xi)H(X) = -\\sum_{i=1}^{n} p(x_i) \\log_2 p(x_i)H(X)=−sumi=1np(xi)log2p(xi) ，这里的p(xi)p(x_i)p(xi) 表示每个可能结果xix_ixi 的概率。从这个公式可以看出，当所有可能结果出现的概率都相等时，熵会达到最大值，这时候系统的随机性最强。例如，抛一枚均匀的硬币，正面和反面出现的概率都是 0.5，通过计算可以得出这个抛硬币事件的熵相对较高；而如果是一枚两面都是正面的特殊硬币，每次抛都必然是正面，那么它的熵就是 0，因为结果完全确定，没有任何随机性。
（三）随机数的质量标准
-
均匀分布：理想的随机数在一定范围内应该是均匀分布的，也就是说，每个数字出现的概率大致相等。就好比从 1 到 100 这 100 个数字中生成随机数，如果是均匀分布的随机数生成器，那么每个数字被生成的概率都应该接近 1%。为了判断随机数是否符合均匀分布，我们可以采用统计检验的方法，其中卡方检验是一种常用的手段。通过将随机数的取值范围划分成若干个区间，统计每个区间内随机数出现的实际频数，再与理论上均匀分布时的期望频数进行比较，计算出卡方统计量。如果卡方统计量小于某个临界值，就可以认为这些随机数在一定程度上符合均匀分布；反之，如果卡方统计量过大，那就说明随机数的分布可能存在偏差，不均匀。例如，在检验某个随机数生成器生成的 1 到 10 之间的随机数是否均匀分布时，我们可以将 1 到 10 这 10 个数字分成 10 个区间，每个区间对应一个数字，然后生成大量的随机数，统计每个数字出现的次数，再用卡方检验来判断这些次数与理论上每个数字应出现次数（假设生成了 1000 个随机数，那么理论上每个数字应出现 100 次）之间的差异是否在可接受范围内。
-
独立性：随机数序列中的每个数都应该相互独立，即任何一个数的出现都不依赖于其他数，也不会对其他数的出现产生影响。比如在抽奖活动中，每次抽奖的结果都应该是独立的，上一次抽奖的中奖号码不会影响下一次抽奖的结果。为了检验随机数的独立性，我们可以使用一些专门的独立性检验方法，像卡方独立性检验等。这些方法主要是通过分析随机数序列中不同位置的数之间是否存在某种关联或依赖关系来判断独立性。例如，对于一个随机数序列，我们可以将其分成若干对相邻的数，然后统计这些数对中两个数之间的相关性，如果相关性很低，接近随机情况下的预期，就说明这些随机数具有较好的独立性；反之，如果相关性较高，那就说明随机数之间可能存在某种隐藏的依赖关系，独立性较差。独立性对于随机数的质量非常重要，因为如果随机数不独立，那么在一些需要随机性的应用中，就可能导致结果出现偏差，无法真实地模拟随机现象。
-
不可预测性：随机数最重要的特性之一就是不可被提前预测，这在很多应用场景中，尤其是对安全性要求极高的加密领域，是至关重要的。以加密通信为例，如果加密密钥是可预测的，那么攻击者就有可能通过分析密钥生成的规律，破解加密信息，导致数据泄露。真正高质量的随机数生成器，应该能够生成完全不可预测的随机数序列，让攻击者无论使用何种方法，都无法提前知晓下一个随机数是什么。在实际应用中，为了确保随机数的不可预测性，我们通常会采用一些特殊的技术和算法，比如利用物理过程中的真正随机现象（如热噪声、量子效应等）来生成随机数，或者使用经过严格密码学验证的伪随机数生成算法，这些算法通过复杂的数学运算和足够的熵源，保证生成的随机数在统计上是不可预测的。
随机数生成器随机性检测系统设计思路
（一）系统功能概述
随机数生成器随机性检测系统的设计目标是全面、准确地评估随机数生成器的随机性质量，为不同应用场景提供可靠的随机数生成器选择依据。该系统主要具备以下功能：
-
支持多种随机数生成器：涵盖线性同余生成器（LCG）、梅森旋转算法（Mersenne Twister）、XOR 移位生成器和系统默认生成器等常见类型。每种生成器都有其独特的算法和特性，例如 LCG 实现简单、计算速度快，但统计性质较差；梅森旋转算法则以超长周期和良好的统计特性著称。系统支持多种生成器，能够满足不同用户对随机数生成效率和质量的多样化需求。在简单的游戏开发场景中，对随机数质量要求相对较低，LCG 的快速生成特性就可以满足需求；而在金融风险评估的蒙特卡洛模拟中，就需要像梅森旋转算法这样高质量的随机数生成器来确保模拟结果的准确性。
-
实现多种随机性检测算法：集成了频数检测、序列检测、扑克检测、游程检测、最长游程检测、累计和检测、自相关检测等多种检测算法。这些算法从不同角度对随机数序列进行分析，例如频数检测关注 0 和 1 的比例是否接近 1:1，以判断随机数的基本分布情况；序列检测则通过分析连续位的频率是否符合随机分布，来检测更复杂的随机性特征。多种检测算法的综合运用，能够更全面、深入地评估随机数生成器的随机性，避免单一算法可能存在的局限性。
-
可配置参数：用户可以根据实际需求灵活配置序列长度、随机数生成器类型和种子值等参数。配置序列长度可以适应不同规模的测试需求，对于一些对随机性要求极高的加密应用，可能需要生成和检测较长的随机数序列；而在一些简单的测试场景中，较短的序列就可以满足初步评估的需求。选择不同的随机数生成器类型，可以对比不同算法生成的随机数的随机性差异；设置种子值则可以实现随机数序列的可重现性，方便在调试和验证过程中进行对比和分析。
-
清晰的测试结果输出：系统会清晰地输出每个测试的 P 值和是否通过测试的判断，同时还会提供详细的备注信息。P 值是判断测试结果的重要依据，它反映了在原假设（即随机数序列是随机的）成立的情况下，观察到当前结果或更极端结果的概率。通过明确的 P 值和通过与否的判断，用户可以直观地了解随机数生成器在各项测试中的表现；详细的备注信息则进一步解释了测试结果的相关细节，例如在频数检测中，备注信息可能会包含 0 和 1 的实际计数、计算得到的统计量等，帮助用户更好地理解测试结果背后的原因。
（二）检测算法原理
-
频数检测：频数检测是一种基础的随机性检测方法，其核心思想是基于随机数序列中 0 和 1 的分布应该符合均匀分布的原理。在一个真正随机的二进制序列中，0 和 1 出现的概率理论上应该相等，都为 0.5 。所以，通过计算随机数序列中 0 和 1 的实际比例，并与理论值 1:1 进行比较，就可以判断该序列是否具有良好的随机性。在一个长度为 1000 的随机数序列中，如果 0 出现了 480 次，1 出现了 520 次，那么 0 和 1 的比例为 48:52 ，与理论的 1:1 存在一定偏差。通过进一步计算统计量，比如使用卡方检验等方法，来评估这种偏差是否在合理范围内。如果统计量显示偏差不显著，那么可以认为该随机数序列在频数方面具有较好的随机性；反之，如果偏差显著，就说明该序列可能存在问题，随机性较差。
-
序列检测：序列检测主要用于分析随机数序列中连续位的频率是否符合随机分布。在随机情况下，不同长度的连续位组合（如 00、01、10、11 等）出现的概率应该与它们的理论概率相符。对于长度为 2 的二进制序列组合，00、01、10、11 出现的理论概率都应为 0.25 。通过统计随机数序列中各种连续位组合的实际出现频率，并与理论概率进行对比，就可以判断该序列在这方面的随机性。如果在一个序列中，00 出现的频率远高于其他组合，达到了 0.4，而其他组合的频率都远低于 0.25 ，那么就说明该序列中连续位的分布不符合随机分布，随机性存在问题。这种检测方法能够发现随机数序列中可能存在的局部模式或规律，对于评估随机数生成器的质量具有重要意义。
-
扑克检测：扑克检测是通过检测固定长度子序列的频率与预期频率的差异，来评估随机数序列的随机性。这里的 “扑克” 可以理解为将随机数序列按照固定长度进行分组，每一组就相当于一张 “扑克牌”。在一个随机数序列中，将其按照长度为 4 进行分组，那么可能出现的不同分组（如 0000、0001、0010 等）共有 16 种。在理想的随机情况下，每种分组出现的概率都应该相等，为 1/16 。通过统计实际生成的随机数序列中各种分组的出现频率，并与理论概率进行比较，计算出卡方统计量等指标。如果卡方统计量较小，说明实际频率与理论频率的差异不显著，随机数序列在扑克检测方面表现良好，具有较好的随机性；反之，如果卡方统计量较大，就表明随机数序列中存在某些分组出现的频率异常，随机性较差。
-
游程检测：游程检测的原理是根据随机数序列中连续相同位的长度分布是否符合随机期望，来判断序列的随机性。在一个随机的二进制序列中，连续出现相同位（如连续的 0 或连续的 1）的长度应该是随机分布的，不会出现过长或过短的游程过于集中的情况。如果一个序列中出现了大量长度为 10 的连续 1 游程，而其他长度的游程很少，那么这就不符合随机期望，说明该序列可能存在非随机的结构或模式。通过统计不同长度游程的数量和分布情况，并与理论上的随机分布进行对比，就可以评估随机数序列的随机性。通常会使用一些统计方法，如计算游程的期望数量和方差，来判断实际游程数量是否在合理范围内。如果实际游程数量与理论期望相差较大，那么就可以认为该随机数序列在游程检测中不通过，随机性存在问题。
-
最长游程检测：最长游程检测主要是通过判断随机数序列中最长连续相同位的长度是否在合理范围内，来评估序列的随机性。在一个真正随机的序列中，最长游程的长度不会过长，否则就表明序列可能存在某种规律性。对于一个长度为 1000 的随机数序列，如果最长游程的长度达到了 50，这就明显超出了合理范围，说明该序列可能不是随机的。确定最长游程长度的合理范围通常需要考虑序列的长度等因素。一般来说，随着序列长度的增加，最长游程的合理长度也会相应增加，但增长速度是有限的。可以通过一些经验公式或统计方法来确定不同长度序列的最长游程的合理上限。如果最长游程长度超过了这个上限，就说明随机数序列的随机性可能存在问题，需要进一步分析和验证。
-
累计和检测：累计和检测是通过计算随机数序列的累积和的分布是否符合随机期望，来检测序列的随机性。在二进制随机数序列中，将 0 转换为 -1，1 保持不变，然后计算序列的累积和。在随机情况下，累积和的分布应该是相对均匀的，不会出现某一方向上的累积和过大或过小的情况。如果在一个序列中，累积和始终为正，且数值不断增大，这就说明该序列的累积和分布不符合随机期望，随机性存在问题。通过分析累积和的最大值、最小值以及分布情况，并与理论上的随机分布进行比较，可以判断随机数序列的随机性。对于较长的序列，可以使用一些统计方法，如计算累积和的标准差等，来评估累积和的波动情况是否符合随机数的特征。如果累积和的波动异常，就表明随机数序列可能不是随机生成的。
-
自相关检测：自相关检测的原理是检测随机数序列与其移位序列之间的相关性，以此来判断序列的随机性。如果一个随机数序列是真正随机的，那么它与自身经过一定位移后的序列之间应该没有明显的相关性。在一个随机数序列中，将其向右移动一位得到一个新的序列，然后计算这两个序列对应位置元素的相关性。如果相关性较高，说明原序列与其移位序列之间存在某种关联，不符合随机数的独立性要求，随机性较差；反之，如果相关性较低，接近随机情况下的预期，就可以认为该随机数序列在自相关检测方面表现良好，具有较好的随机性。通常会使用相关系数等指标来衡量两个序列之间的相关性，通过设定一个阈值，当相关系数超过该阈值时，就判定随机数序列在自相关检测中不通过，随机性存在问题。
系统实现中的关键技术与细节
...
// 检测结果结构体
struct TestResult {
std::string test_name; // 测试名称
double p_value; // P值
bool passed; // 是否通过测试
std::string comments; // 备注信息
};
// 随机数生成器类型
enum RNGType {
LINEAR_CONGRUENTIAL, // 线性同余生成器
MERSENNE_TWISTER, // 梅森旋转算法
XOR_SHIFT, // XOR移位生成器
SYSTEM_RAND // 系统默认生成器
};
// 随机性检测类
class RandomTester {
private:
std::vector<bool> bit_sequence; // 比特序列
std::vector<uint32_t> num_sequence; // 数值序列
size_t sequence_length; // 序列长度
// 辅助函数：将数值序列转换为比特序列
void convertToBitSequence();
public:
// 构造函数
RandomTester(size_t length = 10000);
// 生成随机序列
void generateSequence(RNGType type, unsigned int seed = 0);
// 获取当前序列长度
size_t getSequenceLength() const { return sequence_length; }
// 频数检测：检测0和1的比例是否接近1:1
TestResult frequencyTest();
// 序列检测：检测连续位的频率是否符合随机分布
TestResult serialTest(int m = 2);
// 扑克检测：检测固定长度的子序列频率是否符合预期
TestResult pokerTest(int m = 4);
// 游程检测：检测连续相同位的长度分布是否符合随机期望
TestResult runsTest();
// 最长游程检测：检测最长连续相同位的长度是否在合理范围内
TestResult longestRunTest();
// 累计和检测：检测累积和的分布是否符合随机期望
TestResult cumulativeSumsTest(bool forward = true);
// 自相关检测：检测序列与其移位序列的相关性
TestResult autocorrelationTest(int d = 1);
// 所有测试
std::vector<TestResult> runAllTests();
};
// 线性同余生成器
class LinearCongruentialGenerator {
private:
uint32_t a; // 乘数
uint32_t c; // 增量
uint32_t m; // 模数
uint32_t seed; // 当前种子
public:
LinearCongruentialGenerator(uint32_t a = 1664525, uint32_t c = 1013904223,
uint32_t m = 0xFFFFFFFF, uint32_t seed = 1);
void setSeed(uint32_t s);
uint32_t next();
};
// XOR移位生成器
class XORShiftGenerator {
private:
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
public:
XORShiftGenerator(uint32_t seed = 1);
void setSeed(uint32_t s);
uint32_t next();
};
...
// 正态分布的累积分布函数
double normalCDF(double x) {
return 0.5 * (1.0 + erf(x / sqrt(2.0)));
}
// 卡方分布的累积分布函数近似
double chiSquaredCDF(double x, int df) {
...
// 不完全伽马函数近似
double sum = 0.0;
double term = exp(-lambda) * pow(lambda, k) / tgamma(k + 1);
sum = term;
for (int i = 1; i <= 100; ++i) {
term *= lambda / (k + i);
sum += term;
if (term < 1e-15) break;
}
return sum;
}
// 随机数检测器构造函数
RandomTester::RandomTester(size_t length) : sequence_length(length) {
bit_sequence.reserve(length * 32); // 预留空间
num_sequence.reserve(length);
}
// 转换数值序列为比特序列
void RandomTester::convertToBitSequence() {
bit_sequence.clear();
for (uint32_t num : num_sequence) {
for (int i = 31; i >= 0; --i) {
bit_sequence.push_back((num >> i) & 1);
}
}
}
// 生成随机序列
void RandomTester::generateSequence(RNGType type, unsigned int seed) {
num_sequence.clear();
num_sequence.reserve(sequence_length);
switch (type) {
case LINEAR_CONGRUENTIAL: {
LinearCongruentialGenerator lcg(1664525, 1013904223, 0xFFFFFFFF, seed);
for (size_t i = 0; i < sequence_length; ++i) {
num_sequence.push_back(lcg.next());
}
break;
}
case MERSENNE_TWISTER: {
std::mt19937 mt(seed);
for (size_t i = 0; i < sequence_length; ++i) {
num_sequence.push_back(mt());
}
break;
}
case XOR_SHIFT: {
XORShiftGenerator xorShift(seed);
for (size_t i = 0; i < sequence_length; ++i) {
num_sequence.push_back(xorShift.next());
}
break;
}
case SYSTEM_RAND: {
srand(seed);
for (size_t i = 0; i < sequence_length; ++i) {
num_sequence.push_back(rand());
}
break;
}
}
convertToBitSequence();
}
// 频数检测
TestResult RandomTester::frequencyTest() {
...
// 计算统计量
double s_obs = fabs(count_ones - n / 2.0) / sqrt(n / 4.0);
double p_value = 2.0 * (1.0 - normalCDF(s_obs));
result.p_value = p_value;
result.passed = (p_value >= 0.01); // 显著性水平α=0.01
std::stringstream ss;
ss << "Ones count: " << count_ones << ", Z-score: " << std::fixed << std::setprecision(4) << s_obs;
result.comments = ss.str();
return result;
}
// 序列检测
TestResult RandomTester::serialTest(int m) {
...
// 计算m位和m-1位模式的频率
std::map<std::vector<bool>, int> freq_m;
std::map<std::vector<bool>, int> freq_m_minus_1;
for (int i = 0; i <= n - m; ++i) {
std::vector<bool> pattern(bit_sequence.begin() + i, bit_sequence.begin() + i + m);
freq_m[pattern]++;
}
if (m > 1) {
for (int i = 0; i <= n - (m - 1); ++i) {
std::vector<bool> pattern(bit_sequence.begin() + i, bit_sequence.begin() + i + (m - 1));
freq_m_minus_1[pattern]++;
}
}
// 计算卡方统计量
double chi_squared = 0.0;
for (const auto& pair : freq_m) {
double expected = (m > 1) ?
(freq_m_minus_1[std::vector<bool>(pair.first.begin(), pair.first.end() - 1)] *
freq_m_minus_1[std::vector<bool>(pair.first.begin() + 1, pair.first.end())]) /
(double)(n - m + 2) : n / pow(2, m);
if (expected > 0) {
chi_squared += pow(pair.second - expected, 2) / expected;
}
}
// 自由度
int df = (int)pow(2, m) - 1 - (m > 1 ? m - 1 : 0);
// 计算p值
double p_value = 1.0 - chiSquaredCDF(chi_squared, df);
result.p_value = p_value;
result.passed = (p_value >= 0.01);
std::stringstream ss;
ss << "Chi-squared: " << std::fixed << std::setprecision(4) << chi_squared
<< ", Degrees of freedom: " << df;
result.comments = ss.str();
return result;
}
// 扑克检测
TestResult RandomTester::pokerTest(int m) {
...
if (k < pow(2, m)) {
result.passed = false;
result.comments = "Not enough subsequences for m=" + std::to_string(m);
return result;
}
// 计算每个m位模式的频率
std::map<std::vector<bool>, int> freq;
for (int i = 0; i < k; ++i) {
std::vector<bool> pattern(bit_sequence.begin() + i * m, bit_sequence.begin() + (i + 1) * m);
freq[pattern]++;
}
// 计算卡方统计量
double chi_squared = 0.0;
for (const auto& pair : freq) {
chi_squared += pow(pair.second, 2);
}
chi_squared = (chi_squared * pow(2, m) / k) - k;
// 自由度
int df = (int)pow(2, m) - 1;
// 计算p值
double p_value = 1.0 - chiSquaredCDF(chi_squared, df);
result.p_value = p_value;
result.passed = (p_value >= 0.01);
std::stringstream ss;
ss << "Chi-squared: " << std::fixed << std::setprecision(4) << chi_squared
<< ", Degrees of freedom: " << df;
result.comments = ss.str();
return result;
}
// 游程检测
TestResult RandomTester::runsTest() {
...
// 如果0或1的比例太极端，不适合做游程检测
if (p < 0.1 || p > 0.9) {
result.passed = false;
result.comments = "Proportion of ones too extreme: " + std::to_string(p);
return result;
}
// 计算游程数
int runs = 1;
for (int i = 1; i < n; ++i) {
if (bit_sequence[i] != bit_sequence[i - 1]) {
runs++;
}
}
// 计算期望游程数和方差
double expected_runs = 2 * n * p * (1 - p) + 1;
double variance = (expected_runs - 1) * (expected_runs - 2) / (n - 1.0);
// 计算Z统计量
double z = (runs - expected_runs) / sqrt(variance);
double p_value = 2.0 * (1.0 - normalCDF(fabs(z)));
result.p_value = p_value;
result.passed = (p_value >= 0.01);
std::stringstream ss;
ss << "Runs count: " << runs << ", Z-score: " << std::fixed << std::setprecision(4) << z;
result.comments = ss.str();
return result;
}
// 最长游程检测
TestResult RandomTester::longestRunTest() {
...
for (bool bit : bit_sequence) {
if (bit) {
current_run_ones++;
current_run_zeros = 0;
max_run_ones = std::max(max_run_ones, current_run_ones);
} else {
current_run_zeros++;
current_run_ones = 0;
max_run_zeros = std::max(max_run_zeros, current_run_zeros);
}
}
int max_run = std::max(max_run_ones, max_run_zeros);
// 根据序列长度确定临界值（简化版）
int critical_value;
if (n < 100) {
critical_value = 6;
} else if (n < 1000) {
critical_value = 9;
} else if (n < 10000) {
critical_value = 12;
} else {
critical_value = 15;
}
// 对于较长序列，使用更精确的临界值计算
if (n >= 100000) {
critical_value = static_cast<int>(log2(n)) + 2;
}
bool passed = (max_run <= critical_value);
result.p_value = passed ? 0.5 : 0.0; // 简化的p值表示
result.passed = passed;
std::stringstream ss;
ss << "Longest run: " << max_run << ", Critical value: " << critical_value;
result.comments = ss.str();
return result;
}
// 累计和检测
TestResult RandomTester::cumulativeSumsTest(bool forward) {
...
// 计算累计和，将0转换为-1以便计算
auto it = forward ? bit_sequence.begin() : bit_sequence.end() - 1;
const auto end = forward ? bit_sequence.end() : bit_sequence.begin() - 1;
const int step = forward ? 1 : -1;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + (static_cast<int>(*it) * 2 - 1); // 1变为1，0变为-1
it += step;
}
// 找到最大绝对偏差
int max_abs = 0;
for (int val : s) {
max_abs = std::max(max_abs, abs(val));
}
// 计算p值（简化版）
double p_value;
if (n <= 100) {
// 对于小样本，使用已知临界值表
const std::map<int, std::map<int, double>> critical_values = {
{10, {{1, 0.01}, {2, 0.001}}},
{20, {{2, 0.01}, {3, 0.001}}},
{50, {{3, 0.01}, {5, 0.001}}},
{100, {{5, 0.01}, {6, 0.001}}}
};
auto it_n = critical_values.find(n);
if (it_n != critical_values.end()) {
bool passed = true;
for (const auto& pair : it_n->second) {
if (max_abs >= pair.first) {
p_value = pair.second;
passed = false;
break;
}
}
if (passed) p_value = 0.5;
} else {
p_value = 0.5;
}
} else {
// 对于大样本，使用近似公式
double z = (max_abs / sqrt(n) - 0.5) / 0.5;
p_value = 2.0 * (1.0 - normalCDF(fabs(z)));
}
result.p_value = p_value;
result.passed = (p_value >= 0.01);
std::stringstream ss;
ss << "Max absolute sum: " << max_abs;
result.comments = ss.str();
return result;
}
// 自相关检测
TestResult RandomTester::autocorrelationTest(int d) {
...
int n = bit_sequence.size();
if (n <= d) {
result.passed = false;
result.comments = "Sequence too short for d=" + std::to_string(d);
return result;
}
// 计算1的比例
int count_ones = std::count(bit_sequence.begin(), bit_sequence.end(), true);
double p = count_ones / (double)n;
// 计算自相关系数
int c = 0;
for (int i = 0; i < n - d; ++i) {
if (bit_sequence[i] == bit_sequence[i + d]) {
c++;
}
}
double numerator = c - (n - d) * (2 * p * p - 2 * p + 1);
double denominator = (n - d) * 2 * p * (1 - p);
double r = numerator / sqrt(denominator);
// 计算p值
double p_value = 2.0 * (1.0 - normalCDF(fabs(r)));
result.p_value = p_value;
result.passed = (p_value >= 0.01);
std::stringstream ss;
ss << "Correlation coefficient: " << std::fixed << std::setprecision(4) << r;
result.comments = ss.str();
return result;
}
// 运行所有测试
std::vector<TestResult> RandomTester::runAllTests() {
std::vector<TestResult> results;
results.push_back(frequencyTest());
results.push_back(serialTest(2));
results.push_back(serialTest(3));
results.push_back(pokerTest(4));
results.push_back(pokerTest(8));
results.push_back(runsTest());
results.push_back(longestRunTest());
results.push_back(cumulativeSumsTest(true));
results.push_back(cumulativeSumsTest(false));
results.push_back(autocorrelationTest(1));
results.push_back(autocorrelationTest(5));
return results;
}
// 线性同余生成器实现
LinearCongruentialGenerator::LinearCongruentialGenerator(uint32_t a, uint32_t c, uint32_t m, uint32_t seed)
: a(a), c(c), m(m), seed(seed) {}
void LinearCongruentialGenerator::setSeed(uint32_t s) {
seed = s;
}
uint32_t LinearCongruentialGenerator::next() {
seed = (a * seed + c) % m;
return seed;
}
// XOR移位生成器实现
XORShiftGenerator::XORShiftGenerator(uint32_t seed) {
setSeed(seed);
}
void XORShiftGenerator::setSeed(uint32_t s) {
x = 123456789;
y = 362436069;
z = 521288629;
w = s;
}
uint32_t XORShiftGenerator::next() {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
If you need the complete source code, please add the WeChat number (c17865354792)
使用默认设置运行
./random_tester
使用LCG生成器，长度为100000，种子为12345
./random_tester -l 100000 -r 0 -s 12345
使用XOR移位生成器，长度为50000
./random_tester -l 50000 -r 2
这是一个用于检测随机数生成器(RNG)随机性的系统仿真程序，实现了多种常见的随机性检测算法。程序可以对不同类型的随机数生成器产生的序列进行统计分析，评估其随机性。
功能特点
- 支持多种随机数生成器：线性同余生成器(LCG)、梅森旋转算法(Mersenne Twister)、XOR移位生成器和系统默认生成器
- 实现多种随机性检测算法：
- 频数检测(Frequency Test)
- 序列检测(Serial Test)
- 扑克检测(Poker Test)
- 游程检测(Runs Test)
- 最长游程检测(Longest Run Test)
- 累计和检测(Cumulative Sums Test)
- 自相关检测(Autocorrelation Test)
- 可配置序列长度、随机数生成器类型和种子值
- 清晰的测试结果输出，包括P值和是否通过测试的判断
总结
随机数生成器随机性检测系统对于保障众多依赖随机数的应用领域的可靠性和安全性，有着至关重要的作用。从设计原理上看，该系统融合了多种随机数生成器类型和丰富的随机性检测算法，以全面评估随机数序列的随机性质量。通过深入理解随机数生成器的工作原理，以及各种检测算法背后的数学依据和统计方法，我们能够更准确地判断随机数的质量是否符合要求。
在实现过程中，无论是随机数生成器的代码实现，还是检测算法的具体编程，都需要关注细节，确保每一个环节都能准确无误地运行。结果输出与分析部分，通过清晰的表格形式展示测试结果，并依据 P 值和通过与否的判断，帮助用户直观了解随机数生成器的性能。
随着科技的飞速发展，随机数生成与检测技术也在不断演进。在量子计算领域，量子随机数生成器正逐渐崭露头角。量子力学的不确定性原理为量子随机数生成提供了坚实的理论基础，使得生成的随机数具有更高的随机性和不可预测性。美国 Quantinuum 团队利用拥有 56 个量子比特的 Quantinuum System Model H2 离子阱量子计算机，成功实现了经过认证的随机数生成，这一成果标志着量子随机数生成技术迈出了重要一步，未来有望在对随机性要求极高的密码学等领域得到广泛应用。
机器学习技术的发展也为随机数检测带来了新的思路。机器学习算法能够处理和分析大量复杂的数据，通过对随机数序列特征的学习和挖掘，有望发现传统检测方法难以察觉的模式和规律，从而提高随机性检测的准确性和效率。在大数据时代，利用机器学习算法对海量随机数数据进行分析，或许能揭示出更深层次的随机性特征，为随机数生成器的优化和改进提供有力支持。
未来，随机数生成与检测技术将不断发展，以适应更多新兴领域和复杂场景的需求。在区块链技术中，需要高质量的随机数来保证交易的公平性和安全性，随机数生成与检测技术的进步将为区块链的发展提供更可靠的保障；在物联网设备的安全通信中，随机数用于加密和身份验证，随着物联网规模的不断扩大，对随机数生成与检测技术的需求也将日益增长。
Welcome to follow WeChat official account【程序猿编码】
参考
- 国家标准GB/T 32915-2016，《信息安全技术 随机数生成器的统计检测规范》
- National Institute of Standards and Technology. NIST SP 800-22 Rev. 1a, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.
- Knuth D E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley, 1997.
- Marsaglia G. Xorshift RNGs. Journal of Statistical Software, 2003, 8(14):1-6.
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
10
0- 0
已为社区贡献15条内容
所有评论(0)