随机数及其生成器

伪随机数和伪随机数生成器

计算机是确定性机器，因此它不能直接生成真正的随机数。 混沌系统的随机数生成速度比较慢，很多情况下不适合作为快速（伪）随机数库函数算法。 最著名的快速伪随机数生成算法是数-（线性同余法），其为：

Xn+1=（a Xn+ b）% c// %是C/C++中的MOD（同余）运算符

该方法可以从一个种子X0=seed开始，连续生成任意长的伪随机数序列Xn。 其运算过程极其简单，如果c=2m，其中m为Xn的字长，甚至直接省略MOD运算——当Xn+1≥2m时，高位自动溢出并被截断。 这种方法生成的伪随机数序 *** 实满足在给定范围和精度内均匀分布的要求，但它并不是连续分布的，因为计算机数据存储的精度不是无限的！ 正是由于最小数据间隙的存在，序列才会以相当长的周期循环。

更重要的是，以上述方法为代表的伪随机数生成器生成的数列不具有不可辨别的模式。 相反，它们的定律非常容易从少量数据中推导出来。 这里有两种具体情况。 一是数据加密中使用了伪随机数，所以这种“容易推导出规则”的伪随机数生成器是很不合适的； 二是科学计算中使用伪随机数。 此时不需要随机数掩盖其内部规律，但还有其他要求：伪随机数的内部规律不能与所研究问题的自然规律相似，需要高精度的方法必要时使用减小“最小数据间隙”。

之所以被称为“线性同余法”，是因为 Xn+1=(a" 生成的伪随机数的核心就是这个同余运算。但是，如果一对连续的数字 (x=X2i, y=X2i +1)作为一对二维坐标来确定平面上的一点，那么在伪随机数序列上的一小段中显然会连续出现几对数字，它们各自确定的点沿着一条排列平面上的直线，这就是我在文章开头提到的现象，直线的方程——

设小截面为 Xp, Xp+1, Xp+2,...Xp+ m

那么对应的点对就是(Xp, Xp+1), (Xp+2, Xp+3),…

线 y = Ax + B = (aX + b) MOD c = (aX MOD c) + b

并且 (aX MOD c) = aX - Floor[ aX /c ]·c,

∵根据算法要求，与aX相比，c是一个更大的常数。

∴在一小部分中总是存在Floor [ aX /c ] ≠Floor [ aXp/c ]。

用常数P记录Floor[aXp/c]，直线方程可写为：

y = Ax + B = aX + b - cP，

当且仅当 cP≤aXp＜aXp+ m＜cP+c 时，该方程成立。

二维平面上的这种规律性严重影响了我的模拟计算，因此我不得不重复调用 () 函数来初始化伪随机数生成器——即使使用两个独立的伪随机数生成器也无法避免类似的规律性。 然而()函数使用系统时钟作为种子来实现初始化，这导致“连续初始化”方法存在严重问题：

首先，读取系统时钟的函数需要访问CPU-RAM总线之外的慢速设备，因此执行时间相当慢，这会严重影响高性能计算的速度。 当然，可以使用现代操作系统的虚拟时钟设备在CPU内部模拟外设时钟，这部分缓解了这个问题。

其次，系统时钟的计时精度不高，但当今计算机“CPU-cache”子系统的运行速度如此之高，以至于CPU可以在系统时钟计时精度的最小间隙（微秒级）内完成计时。 数千次操作。 如果运行速度很快，并且初始化时读取系统时钟非常频繁，可能会导致连续多次读取以获得完全相同的时钟值。 换句话说，同一种子连续多次用于初始化。 那么显然你会得到完全相同的伪随机数值。

第三，以线性同余法为代表的简单伪随机数生成算法，生成的前几个数受初始化种子的影响较大，随机性不好。 一般情况下，伪随机数序列的前几个数需要被丢弃。 值 - 这种不均匀性问题在上述高速下尤其严重！ 因为当初始化非常频繁地进行时，每次使用的种子即使不完全相同，也是紧密相邻的。 如果丢弃序列中的前几个数字，就会增加计算量，降低效率。

总之，频繁使用系统时间进行初始化的方法在高速运行中是相当无效的。

但好的一面是，只要研究人员对他正在处理的科学计算问题有清晰的思路和清晰的认识，一般来说，总有办法避免伪随机数序列相似的内在规律所研究问题的自然规律； 同时，只要稍微应用一些编程技巧，就可以有效地用存储空间换取运行时间，避免重复调用系统时间进行初始化。 例如，对于上面的例子，可以打开一个二维数组T[2][max](max≠2n)，然后：

();

整数我；

对于 (i=0 ; 我

T[1][i] = ();

/*这里的函数根据具体情况返回需要的数据类型*/

();

对于 (i=0 ; 我

T[2][i] = ();

根据该算法，存储一组伪随机二维坐标数据对，然后在调用时按列读取数据对（T[1][i]，T[2][i]）。 当“max”不大时（例如双精度浮点数组为5000），整个数组（78.125KB）可以完全缓存在CPU的L2缓存中，从而可以快速生成一系列坐标数据对并阅读。 同时，由于T[1][i]和T[2][i]并没有依次生成一对随机数，由于两次非密集的()调用，它们之间的联系几乎完全不相关。 如果需要的数据对太大，超过了更大对，可以根据情况重新生成这么多对数据然后使用，但更好不要随意增加数组的更大尺寸。

以上是特殊用途的解决方案的特例。 各种其他情况也可以用类似的具体问题来处理。 例如，一维随机游走问题可以直接使用连续的“线性同余”伪随机数序列。 最多，伪随机数生成器需要在相当长的一段时间后重新初始化。 事实上，如果独立使用科学计算所需的大量随机数，大多数都可以直接连续应用线性同余法生成的序列而不必太担心，偶尔会插入一个“初始化”操作。 然而，线性同余方法只能保证在“各自独立使用”的一维情况下，随机数序列的每个小区间不存在明显的局部相关模式。 二维及以上的高维需要具体分析——所谓“二维或高维”是指前面提到的需要连续生成随机向量的情况。

为什么一段时间后需要插入初始化操作呢？

除非添加一些额外的程序数据——例如系统时间，否则任何伪随机数生成器都必须是循环的，但循环周期的长度不同。 因为伪随机数生成器是固定的运算程序，前一次的输出是下一次运算的输入，但计算机的数值存储状态是有限的，所以在某一点上必然会产生与之前相同的结果在循环中。 从这里开始重复之前的循环。 要延长周期，最简单的方法是经过一些周期后重新初始化系统时间； 当然，你也可以组合两个或多个伪随机数生成器一起工作。 组合有很多种，例如：使用之一个生成器生成h个随机数，使用第二个随机数生成器将它们的顺序随机打乱后再输出； 或者之一个随机数生成器可以用来生成一个种子和一个整数h，第二个生成器使用seed为种子连续生成h个随机数...

混沌动态系统生成的随机数

对于一般的科学研究来说，只要保证伪随机数的内在规律与所研究的自然规律不相似，在所要求的数据精度下呈现出“准连续均匀分布”就足够了。 “推演生成定律”等逆向工程的难度是没有限制的。 有时甚至需要一个简单明了的生成规律来确认这个规律是否与所研究的自然规律相似。

然而，当数据被加密时，我们往往对这种逆向工程极为担心，因此需要设计一种难以逆推的生成法则。 大质数相乘来创建巨大的合数对于逆向工程来说相当困难，但它需要特殊的、巨大的数据结构来存储数据和执行操作，因此不适合扩展到快速生成伪随机数。 算法。

然而，在混沌动态系统的演化过程中生成伪随机数的方法是相当合适的。 要选择一组好的非线性方程组，只要保密程序中使用的非线性方程组的几个常数的初始值，并根据程序本身输出的伪随机数，系统时间为每隔几个周期就调用悄悄地改变这些常量，那么即使整个算法向全世界开放，也几乎不可能进行逆向工程并找出其中的规则（即找出那些常量值的变化规则）。 只要这些伪随机数序列运行一段时间后向外界发布，即使是暴力穷举法也无法破译其内在规律。 算法如下：

++++++++++++++++++++++++++++++++++++++++++++++++++++++ +

该算法尚未经过密码安全测试，用户须自行承担可能存在的安全风险。

++++++++++++++++++++++++++++++++++++++++++++++++++++++ +

( [ n ] ) ;//生成几个常量的初始值，需要硬件随机数

/* [ ]数组存储除之一个常量之外的各个常量的值，这些值都是整数，并且

( [ n ] ) ≥ 安全所需的加密强度，如*/

做{([n],,([n]));

/*读取系统时间并生成几个伪随机数，

然后用这些数据混合计算出一个新的[n]值*/

for (count=[0] ; count>0 ; count - - )

( [ n ] ) ;//连续输出伪随机数

问（）;

}直到(==是);

这是一种利用混沌动力系统的初值敏感性来进行“反逆向工程”的伪随机数生成算法。 初始值的微小差异会导致短时间内产生非常巨大的差异，因此“通过运行一段时间”来反向估计伪随机数初始值的方法几乎不可能实现稍后发布的序列”；至于如何应对暴力穷举法的前向破解——只要数组[n]的总长度足够长，并且受到严密保护，如果不存在任何初始值被盗后，穷举枚举所需时间的数学期望也非常长。

困难在于如何对这些瞬时伪随机数进行归一化和校正，使得任何短的伪随机数序列都能呈现均匀分布。 另外，混沌动力系统产生的伪随机数的内在规律虽然不容易与一般应用中的规律混淆（即使我们也在研究混沌动力系统，只要模型稍有不同，就会有没问题），但是一旦出现混乱，就很难找到问题的根源。 这里我提供一个权宜之计：收集伪随机数子程序的输出，收集到足够的值后对其进行FFT。 你可以尝试一维、二维……任何你认为必要的傅立叶变换； 如果发现转换后的结果有明显的规律性，则立即再次采集一批不同的输出数据，重复刚才的测试过程几次。 如果总是存在类似的模式，则说明该伪随机数子程序具有明显的规律性，不宜使用； 另一方面，如果你没有发现任何明显的模式，并不意味着这个子例程是优秀的——这只是你还没有发现缺陷。

如何让伪随机数的内在规律更加隐蔽？ 如何让它看起来（和表现）更像是一个真正的随机数，而不是一个可预测的结果？ 这些问题不仅在科学计算领域经常被提出，而且在电子商务、保密通信等涉及高度机密信息传输的领域也显得更为迫切。 这是因为当今大多数流行的加密算法都是基于从随机数派生的密钥。 如果使用伪随机数，一旦其内在规律被别有用心的人发现，就有可能算出密钥，进而破译相应的密文！ 上述混沌动态系统可以生成基本满足要求的伪随机数序列，但更能满足需要的随机数应该是来自硬件设备的真随机数……

硬件随机数发生器

伪随机数并不是“坏随机数”，但在某些情况下出于安全原因我们不得不使用“真随机数”。 产生真随机数的方法必须依赖硬件，其原理无非就是量子力学和混沌动力学。 系统。 量子力学的随机现象迄今为止还没有更深层次的规律性。 因此，利用放射源衰变等过程得到的随机数序列必须是真正随机的。 经过归一化和校正后，可以作为优秀的随机数序列发布。 然而，混沌动态系统难道不是一个“伪随机”的确定性系统吗？ 它如何生成“真随机数”？

我们说纯基于软件的混沌动态系统的伪随机数生成器生成伪随机数。 这是因为现有的软件运行在完全确定性的计算机上，计算机可以存储的值是离散的但准确的。 - 例如，由于离散有限位二进制存储方式，无法准确存储实数X=3.00000...，但可以准确存储X=2等完全确定的近似值。 E+00。 那么，在各种条件和变化过程完全确定的计算机中，产生的随机数当然是可以预测的“伪随机数”。

现实世界中的硬件设备是不同的。 例如，某些硬件利用电子元件温度的随机波动通过电子设备放大来生成随机数。 理论上，它应该满足“热传导-流体力学”组的复合非线性动力学方程组，但实际上不可能用这样一组方程组来预测随机数的生成：

首先，我们无法准确确定模型的初始条件，很多物理量最多只能测量到4到6位有效数字。 一方面，这是因为测量工具本身精度的限制； 另一方面是因为客观世界的微观波动导致这些初始值发生快速而微小的变化； 即使在足够小的微观尺度上，也会遇到量子“不确定性”。 性原则”。 种种原因导致很难同时测量客观世界中一系列初始值的精确值。 相比之下，我们可以在计算机中的模型上指定任意数量的足够准确的（最多 8 到 15 位有效数字）值。 初始值并强制其为“同时”的值。

其次，在计算机模拟过程中很容易限制环境条件（精确度为8到15位有效数字）以保持稳定，但这在现实世界中是不可能的！ 以PCI卡形式的随机数发生器为例，机箱内空气的湿度、温度和速度矢量分布的微小波动可能会显着影响其散热。 如果都将它们视为扩展模型的变量，那就会大大增加模型的初始条件数量，使得“同时测量一系列初始值的精确值”变得更加不可能”。

可见，利用现实世界中初值不确定的混沌动力系统，由于其初值敏感性，我们也可以获得几乎完全不可预测的随机数序列。 对于基于量子力学的硬件生成的无限随机数序列，预测它是不可能的事件； 而基于混沌动态系统预测硬件生成的无限随机数序列是零概率事件，也就是说，在可预见的未来任何应用都可以放心地视为“不可能事件”！ 简而言之，我们将依赖于量子力学或混沌动态系统的硬件随机数生成器统称为“真正的”随机数生成器。

长半衰期的放射源（如T1/2=30年的Cs-137）加上盖革计数器，辅以有效的防护设备和计算机数据接口卡，加上参数调整良好的标准化器修正程序，就可以组成一个良好的硬件随机数发生器，它是一个基于量子力学的完全不可预测的随机数发生装置。 但随着放射源的演变和仪器设备的逐渐老化，这种归一化校正程序需要每隔一段时间就对参数进行校正。 这不是什么大问题； 真正的大问题是生成随机数的效率。 太低！ 为了保证足够的测量精度，探测器的增益不能太大。 这样，装置的随机数输出带宽就受到放射源的辐射强度的限制。 可能每秒只有几位，甚至几十秒一位！

电子热运动的噪声（在电阻器或二极管中）是一种量子效应。 根据这个原理生成随机数的硬件设备可以更快地输出随机数。 例如，该公司的一些设备可以以20 kb/s的带宽输出出色的质量。 真正的随机数。 Intel RNG 的带宽为 75kb/s，几乎不需要额外成本，因为该设备所需的硬件是 Intel 82802 Hub（也称为 BIOS 设备）中的标准配置。 自2003年起，VIA就在其CPU中嵌入了RNG模块。 由于采用CPU核心级设计和生产工艺，其访问速度非常快c++ 随机数生成器，据称能够以800~1600 kb/s的速率生成数据。 真正的随机数——转换成单精度浮点数，只有25~50 kHz。 VIA RNG的技术原理是联合使用一组四个 *** 管振荡器，其随机性的来源来自于噪声。

正是由于硬件随机数生成器生成的数字是完全随机的，即使是设计和使用它的人也无法找到这些真实随机数的生成规则，因此使用软件来准确地校正其分布变得相当困难，并且必须利用大量的统计数据得到经验校正函数，不能保持很好的校正精度。 这对于加密应用来说并不是什么大问题，但是对于科学计算来说就会大大降低计算结果的准确性。

硬件随机数生成器的更大缺点是：它们太慢了！ 即使是VIA RNG的25~50 kHz单精度浮点数生成率也远远落后于当前主流x86系统的2~/CPU浮点计算速度：单CPU运行时几乎每10万次浮点运算对于计算密集型的科学研究来说，等待单精度随机数显然是不够的。

说到这里，就不得不提一些半硬件半软件的解决方案。 它们不需要特殊的硬件设备，可以跨平台应用于几乎任何类型的计算机。 它们比 Intel 或 VIA 的 RNG 更容易获得； 但它们并不完全是软件伪随机数生成器，但至少是近似不可预测的（半真半假）随机数源。 本质上，它们是一种用于混沌动态系统的硬件随机数生成器：

其中一些生成器捕获键盘、鼠标、硬盘驱动器和外设中断信号（DMA 等）的操作，并将它们用作随机数源； 有些收集互联网上的不确定行为作为随机数的来源。 例如，本地网络信号流量波动； 其他人将从系统硬盘上任何选定的声音、图像、动画文件中提取随机信号，或从声卡和调制解调器等 AD/DA 转换器中提取背景噪声。 。 这些不确定行为最根本的根源是个体或人类社会的活动，而人或人类社会是非线性耗散系统。 显然，上述随机数生成方法都是基于混沌动态系统的。

尽管采样的行为可能看起来是随机发生的，但这种随机性无法得到证明。 如果这些物理动作是静止的（例如服务器的鼠标和键盘可能根本没有连接）或者只是简单地重复，就有可能生成一系列低质量的随机数，导致随机数硬件的质量下降源远低于设计者在最理想条件下的预期。 然而，尽管质量较低且不稳定，但这些硬件比直接利用放射源计数或电子热运动等现象的专用硬件便宜得多且更常见，并且已经在系统层或驱动器层实现了通用随机化。 从用户的角度来看，数据池设备更接近于软件解决方案——无论是在易用性还是实施方面。

其中最著名的就是Linux内核1.3.30及以上版本在系统层提供的随机数池虚拟设备“/dev/”。 “/dev/”设备驱动程序从其他硬件：鼠标、键盘、磁盘驱动器、各种接口卡等收集动作信息，并将这些未经纠正的随机信息填充到一个公共的“（信息）熵池”中，然后提供适当的信息。需要访问“/dev/”设备时的统计函数修正和转换。 当然，它收集信息的速度也很慢，甚至比基于量子效应的专用硬件还慢！ 不过，总体来说，质量确实接近基于量子效应的硬件随机数生成器。

由于其运行缓慢，“/dev/”的“熵池”在频繁读取时会很快耗尽，因此我们不应该使用该设备作为快速获取大量高质量随机数的来源，而应该获取来自另一个相关设备。 从虚拟设备“/dev/”获取。 “/dev/”设备使用“/dev/”中的随机数作为种子，使用MD5算法生成纯软件伪随机数。 效果显然比简单的线性同余法高很多，但相应的速度会低一些。 。 调用这两个虚拟设备的方法非常简单。 文末附录中给出了相应的C99程序示例。

为了高速生成大量（伪）随机数，我们不得不使用纯软件伪随机数生成器，而任何纯软件随机数生成器本身都无法自发生成信息熵。 它必须有来自硬件的输入——即来自“熵源”的数据。 根据通常的算法描述，必须首先初始化伪随机数生成器，例如使用系统时间作为种子。 该操作将输入32位C99标准中的信息熵。 此后，每次调用系统时间时，“重新初始化”理论上都会引入信息熵。 这里有两点需要注意：

首先，在两次初始化之间，伪随机数生成器输出的序列只有总共信息熵，无论输出多少位信息！ 当然，这并不妨碍这些低熵数据在很多情况下的正常使用。

其次，如果非常频繁地调用系统时间“重新初始化”，则前后两次获取的系统时间值之间的相关性过大，信息熵就不会被重新引入。 因此，需要适当降低调用系统时间的频率，或者使用其他更快的硬件随机数生成器作为“熵源”。