2022年随机数的生成 .pdf

《2022年随机数的生成 .pdf》由会员分享，可在线阅读，更多相关《2022年随机数的生成 .pdf（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、随机数的生成摘要： 随机数在密码学中应用广泛，随机数产生的好与坏直接影响到对数据加密、数字签名、身份认证等运用的安全性，尤其是当用某一随机数作为密钥时，这一点更为明显。直接利用计算机中的伪随机序列发生器产生的随机数并不完全随机，在有限状态机中是周期的，而任何周期性的东西都是可预测的。真正的随机数是使用物理现象产生的，通常我们使用的随机数表其实是伪随机数。关键词： 随机数；伪随机数；均匀分布；二项分布；正态分布。1. 随机数的介绍1.1 随机数的历史随机数的产生方法的研究已经有较长的历史. 至今仍有统计学者继续研究随机数的产生的方法和理论. 随机数的产生 , 最早的方法称为手工方法. 即采用抽签

2、、 掷骰子、抽牌、摇号或者从搅乱的罐子中取带数字的球等方法，许多彩票的发行仍采用这种方法。随着计算机和模拟方法的应用， 计算机来产生随机数成为新的课题。利用计算机产生随机数有两种方法，在计算机内输入随机数表和把具有随机性质的物理过程变换为随机数，如粒子的辐射性，裂变等等。在数据结构、 算法分析与设计、 科学模拟等方面都需要用到随机数。由于在数学上，整数是离散型的，实数是连续型的，而在某一具体的工程技术应用中，可能还有数据值的范围性和是否可重复性的要求。在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模

3、拟法计算的时候等等。在用计算机编制程序时，经常需要用到随机数，尤其在仿真等领域，更对随机数的产生提出了较高的要求，仅仅使用C语言类库中的随机函数已难以胜任相应的工作。由具有已知分布的总体中抽取简单子样，在蒙特卡罗方法中占有非常重要的地位。总体和子样的关系，属于一般和个别的关系，或者说属于共性和个性的关系。由具有已知分布的总体中产生简单子样，就是由简单子样中若干个性近似地反映总体的共性。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - -

4、- 随机数是实现由已知分布抽样的基本量，在由已知分布的抽样过程中，将随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简单子样。1.2 随机数的定义随机数是专门的随机试验的结果。在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。1.3 随机数在密码中的作用很多密码算法都需使用随机数，例如：相互认证。在密钥分配中需使用一次性随机数来防止重放攻击。会话密钥的产生。公钥密码算法中密钥的产生，用随机数作为公钥密码算法中的密钥，或以随机数来产生公钥密码算法中的密钥。在随机数的上

5、述应用中，都要求随机数序列满足随机性和不可预测性。（1） 随机性以下两个准则常用来保障数列的随机性： 均匀分布 : 数列中每个数出现的频率应相等或近似相等。 独立性: 数列中任意一数都不能由其他数推出。数列是否满足均匀分布可通过检测得出，而是否满足独立性则无法检测。有很多检测方法能证明数列不满足独立性，因此通常检测数列是否满足独立性的方法是在对数列进行了足够多次检测后都不能证明不满足独立性，就可比较有把握地相信该数列满足独立性。在设计密码算法时， 经常使用似乎是随机的数列， 称为伪随机数列，例如 RSA算法中素数的产生。一般来说，决定一个大数N是否为素数是很困难的。最原始的方法是用小于N 的每

6、个数去除N，如果 N 很大，比如 10150，这一方法则超出了人类的分析能力和计算能力。很多有效的算法是通过使用随机选择的整数序列作为相对简单计算的输入，可检测一个数的素性。如果随机选择的序列足够长（当然，远小于15010） ，就可比较肯定地得出这个数的素性。这种方法称为随机化，在设计密码算法时经常使用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - （2）不可预测性在诸如相互认证和会话密钥的产生等应用中，不仅要求数列具有随机性

7、而且要求对数列中以后的数是不可预测的。对于真随机数列来说，数列中每个数都独立于其他数，因此是不可预测的。对于伪随机数来说，就需要特别注意防止敌手从数列前边的数预测出后边的数。1.4 随机数产生的方法产生随机数有多种不同的方法。这些方法被称为随机数发生器。随机数最重要的特性是它在产生时后面的那个数与前面的那个数毫无关系。真正的随机数是使用物理现象产生的：比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等等。这样的随机数发生器叫做物理性随机数发生器，它们的缺点是技术要求比较高。在实际应用中往往使用伪随机数就足够了。这些数列是“似乎”随机的数，实际上它们是通过一个固定的、可以重复的计算方法产生的。

8、它们不真正地随机，因为它们实际上是可以计算出来的，但是它们具有类似于随机数的统计特征。这样的发生器叫做伪随机数发生器。在真正关键性的应用中，比如在密码学中，人们一般使用真正的随机数。1.5 随机数生成的基本原理生成服从给定分布的随机数， 需要首先生成服从均匀分布的随机数。常用的生成均匀分布随机数的方法是同余法，其递推公式为1modiixaxcm给定初值0 x ，可以迭代出均匀随机数12,nx xx ，将它们进行标准化（此时随机数界于0 和 1 之间）或极差标准化（此时随机数界于-1 和1 之间） ，可以得到均匀分布的随机数。获得均匀分布的随机数以后，可以用多种方法构造基于该随机数的随机变量，常

9、用的方法是反函数法，即利用随机变量x的分布函数 Fx的反函数1Fx 来推求随机变量。基本算法是：（1）产生均匀分布随机数ir ；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - （2）令1iixFr，然后返回。2. 伪随机数的介绍2.1 伪随机数的定义真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。而计算机中的随机函数是按照一定算法模拟产生的，其结果是确定

10、的，是可见的。我们可以这样认为这个可预见的结果其出现的概率是100% 。所以用计算机随机函数所产生的“随机数”并不随机，是伪随机数。2.2 伪随机数的生成方法一般地，伪随机数的生成方法主要有以下3 种：（1）直接法（ Direct Method） ，根据分布函数的物理意义生成。缺点是仅适用于某些具有特殊分布的随机数，如二项式分布、泊松分布。（2）逆转法（Inversion Method） ，假设U服从 0,1 区间上的均匀分布，令1XF U ，则X的累计分布函数（ CDF ）为F。该方法原理简单、编程方便、适用性广。（3）接受拒绝法（ Acceptance-Rejection Method）

11、：假设希望生成的随机数的概率密度函数（ PDF ）为f，则首先找到一个 PDF为g的随机数发生器与常数 c，使得 fxcg x ，然后根据接收拒绝算法求解。 由于算法平均运算 c次才能得到一个希望生成的随机数， 因此 c的取值必须尽可能小。显然，该算法的缺点是较难确定g与 c。因此，伪随机数生成器（PRNG ）一般采用逆转法，其基础是均匀分布，均匀分布 PRNG 的优劣决定了整个随机数体系的优劣。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - -

12、- - - - 伪随机数发生器3. 编程产生所选分布的随机数3.1 二项分布基本数学原理：设X服从参数为,n p的二项分布，概率函数为1,0,1, .n kkknpC ppkn在 Matlab 中用函数 binornd 产生参数为,n p的二项分布的随机数，其基本的调用格式如下：R=binornd(N,P) %,N P为二项分布的两个参数，返回服从参数为,N P的二项分布的一个随机数；R=binornd(N,P,m,n) %,m n分别表示随机数产生的行数和列数。例如，当X服从参数为=1000,=0.05np的二项分布时，用 Matlab 随机生成 100 个数，见下图：3.2 均匀分布基本数

13、学原理：设X在区间,a b 上服从均匀分布，密度函数为名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 1,;0,axbfxba当其他在 Matlab 中用函数 unifrnd产生均匀分布的随机数， 其基本调用格式如下：R=unifrnd(a,b) %返回参数为,a b的连续型均匀分布的随机数；R=unifrnd(a,b,m) %m指定产生 m 行 m 列个随机数；R=unifrnd(a,b,m,n) %,m n分别表示产生的随机

14、数的行数和列数。例如，当X在区间 10,20 上服从均匀分布时，用Matlab 随机生成 100个数，见下图：3.3 正态分布基本数学原理：设X服从参数为和的正态分布，密度函数为22121,02xfxe在 Matlab 中用函数 normrnd 产生参数为,的正态分布的随机数，其基本的调用格式如下：R=normrnd(MU,SIGMA) % 返回均值为MU，标准差为SIGMA的正态分布的随机数，R可以使向量或矩阵；R=normrnd(MU,SIGMA,m) % m制定随机数的行数与列数，与R同尾数，产生 m行 m列个随机数；R=normrnd(MU,SIGMA,m,n) %,m n分别表示R的

15、行数和列数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 例如，当X服从参数为=0和=1的正态分布时，用Matlab 随机生成100 个数，见下图：4. 结束语本文主要介绍了随机数与伪随机数，并解释了生成的原理与方法。通过计算机 Matlab，可以产生常用分布，如二项分布、均匀分布、正态分布等的随机数。参考文献：1 百度百科 .随机数 .词条2 百度百科 .伪随机数 .词条3 杨煜 .随机数的产生 .哈尔滨工业大学4 杨波 .现代密码学 (第 2 版).05-2 5 青岛理工大学精品课程.概率论与数理统计科学实验.实验三名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -