大随机数生成器算法

2常见随机数生成方法简析
2.1 迭代取中法
这里在迭代取中法中介绍平方取中法 , 其迭代式如下 :
Xn+1=(Xn^2/10^s)(mod 10^2s)
Rn+1=Xn+1/10^2s
其中， Xn+1 是迭代算子，而 Rn+1 则是每次需要产生的随机数。
第一个式子表示的是将 Xn 平方后右移 s 位，并截右端的 2s 位。
而第二个式子则是将截尾后的数字再压缩 2s 倍，显然 :0=<Rn+1<=1.
迭代取中法有一个不良的性就是它比较容易退化成 0。
2.2 乘同余法
乘同余法的迭代式如下 :
Xn+1=Lamda*Xn(mod M) (Lamda 即参数λ )
Rn+1=Xn/M
各参数意义及各步的作用可参 2.1。
当然，这里的参数的选取至关重要。
经过前人检验的两组性能较好的素数取模乘同余法迭代式的系数为 :
1 ） lamda=5^5,M=2^35-31
2 ） lamda=7^5,M=2^31-1
2.3 混同于法
混合同余法是加同余法和乘同余法的混合形式 , 其迭代式如下 : 【买计算机毕业论文就到计算机毕业论文网】 内容来自think58 [版权所有：http://think58.com]

Xn+1=( Lamda*Xn+C )%M
Rn+1=Xn/M

本文来自think58

[资料来源：www.THINK58.com]

经前人研究表明，在 M=2^q 的条件下，参数 lamda,miu,X0 按如下选取，周期较大，概率统计特性好 :
Lamda=2^b+1,b 取 q/2 附近的数
C=(1/2+sqrt(3))/M
X0 为任意非负整数
它的一个致命的弱点，那就是随机数的生成在某一周期内成线性增长的趋势，显然，在大多数场合，这种极富“规律”型的随机数是不应当使用的。 copyright think58 [来源：http://think58.com]

实现 :
1 double _random( void )
2 {
3 int a;
4 double r;
5
6 a = rand() % 32767 ;
7 r = (a + 0.00 ) / 32767.00 ;
8
9 return r;
10
11 }
2.4 反变换法
它首先需要使用均匀分布获得一个 (0,1) 间随机数 , 这个随机数相当于原概率分布的 Y 值 , 因为我们现在是反过来求 X. 哎 , 听糊涂了也没关系 , 只要知道算法怎么执行的就行 .
采用概率积分变换原理 , 对于随机变量 X 的分布函数 F(X) 可以求其反函数，得 : 原来我们一般面对的是概率公式 Y=f(X). 现在反过来 , 由已知的概率分布或通过其参数信息来反求 X.
Xi=G(Ri)
其中 ,Ri 为一个 0-1 区间内的均匀分布的随机变量 .
F(X) 较简单时，求解较易，当 F(X) 较复杂时，需要用到较为复杂的变换技巧。 copyright think58

2.4.1 平均分布 :
已知随机变量密度函数为 :

2.4.2 指数分布 :
指数分布的分布函数为 :
x<0 时 ,F(x)=0 ; x>=0,F(x)=1-exp(-lamda*x)
利用反函数法，可以求得 : x=-lnR/lamda( 怎么来的别问 )

2.4.3 正态分布随机变量的生成 :
正态分布在概率统计的理论及应用中占有重要地位，因此，能产生符合正态分布的随机变量就在模拟一类的工作中占有相当重要的地位。
下面介绍两种方法。
经过一定的计算变行，符合二维的正态分布的随机变量的生成可按下面的方法进行：
1) 产生位于 0-1 区间上的两个随机数 r1 和 r2.
2) 计算 u=2*r1-1,v=2*r2-1 及 w=u^2+v^2
3) 若 w>1 ，则返回 1)
4) x=u[(-lnw)/w]^(1/2) ( 怎么来的别问 )
y=v[(-lnw)/w]^(1/2)
如果为 (miu,sigma^2) 正态分布 , 则按上述方法产生 x 后， x’=miu+sigma*x
由于采用基于乘同余法生成的 0-1 上的随机数的正态分布随机数始终无法能过正态分布总体均值的假设检验。而采用 C 语言的库函数中的随机数生成函数 rand() 来产生 0-1 上的随机数，效果较为理想。
2.5 离散型随机变量
基本的思想是这样的：
1 ）在泊松分布中，求出 X 取何值时， p(X=k) 取最大值时，设为 Pxmax.
其时，这样当于求解 f(x)=lamda^k/k! 在 k 取何值时有最大值，虽然，这道题有一定的难度，但在程序中可以能过一个循环来得到取得 f(x) 取最大值时的整数自变量 Xmax 。 think58好，好think58

[资料来源：http://www.THINK58.com]

2) 通过迭代，不断生成 0-1 区间上的随机数，当随机数 <Pxmax 时，则终止迭代，否则重复 (2)
3) 记录迭代过程的次数，即为所需要得到的符何泊松分布的随机量。
显然，这种方法较为粗糙，在试验的过程中发现：生成的的随机量只能算是近似的服从泊松分布，所以，更为有效的算法还有待尝试。
实现 : 采用 double 至少可以支持 lamda=700 ，即 exp(-700)!=0

1 const int MAX_VAL = 10000 ;
2 double U_Rand( double a, double b ) // 均匀分布
3 {
4 double x = random( MAX_VAL );
5 return a + (b - a) * x / (MAX_VAL - 1 );
6 }
7 double P_Rand( double Lamda ) // 泊松分布
8 {
9 double x = 0 ,b = 1 ,c = exp( - Lamda ),u;
10 do {
11 u = U_Rand( 0 , 1 );
12 b *= u;
13 if ( b >= c )
14 x ++ ;
15 } while ( b >= c );
16 return x;
17 }
为防止lamda过大而溢出,故应该自己来写一个浮点类
3 随机数的检验
随机数的统计检验，就是根据（0，1）上均匀总体简单子样式的性质来研究所产生的随机数序列的相应性质，进行比较鉴别，视其差异显著与否，决定取舍。如果所产生的伪随机数经过各类检验，其差异均不显著，我们即接受其为均匀总体随机数的子样。

本文来自think58 [资料来源：http://www.THINK58.com]

需要指出的是，若所产生的伪随机数序列通过某种随机性检验，只是说它与随机数的性质和规律不矛盾，我们不能扛绝它，并不是说它们已经具有随机数的性质与规律。因此检验所产生的伪随机数序列时，所通过的检验越多，随机数序列就越靠得住。随机数的检验方法有：
参数检验，检验其分布参数的观察值与理论值的差异显著性。
均匀性检验，又称频率检验，意在检验伪随机数的经验频率与理论频率的差异是否显著。
独立性检验，即检验所产生的伪随机数的独立性和统计相关是否异常，包括相关关系检验和联列表检验等。
组合规律检测，按随机数出现的先后次序，根据一定的规律组合，检验其组合的观察值与理值是不否有显著差异，包括距离检验和配套检验等。
游程检验，把随机数序列按一定的规则进行分类，分为正负游程检验和升降游程检验等。
4 大随机数产生的机理
4.1 流程图

图1 1024位随机数产生原理图
伪随机数产生器的产生过程:
输入： 输入为两个64比特的伪随机数DTi和Vi，其中DTi表示当前的日期和时间,每产生一个数Ri后，DTi都更新一次；Vi是产生第i个随机数时的种子，其初值可任意设定，以后每次自动更新。
密钥： 产生器用了3次三重DES加密，3次加密使用相同的两个56比特的密钥K1和K2，这两个密钥必须保密且不能用作他用。

think58好，好think58

输出： 输出为一个64比特的伪随机数Ri和一个64比特的新种子Vi+1
Step_1: 使用两个56比特的密钥K1和K2,对伪随机数DTi进行一次三重DES加密(EDE),得到Result_1;
step_2: 任意设置一个值为Vi的初值,将Vi和Result_1进行异或,得到Result_2;
step_3: 使用密钥K1和K2对Result_2进行一次三重DES加密(EDE),得到一个64bit的Ri和Result_3;
（公式1）
(说明: EDE表示两个密钥的三重DES)
step_4: 异或Result_1和Result_3,得到Result_4;
step_5: 使用密钥K1和K2对Result_4进行一次三重DES加密(EDE),得到Result_5,即得到一个64bit的新种子V(i+1).
（公式2）
(说明: EDE表示两个密钥的三重DES)
step_6: V(i+1)将作为下一轮的输入Vi,再次循环完成step_1到step_5的过程,直到完成16轮迭代加密.
本方案具有非常高的密码强度，这是因为采用了112比特长的密钥和9个DES加密，同时还由于算法由两个伪随机数输入驱动，一个是当前的日期和时间，另一个是算法上次产生的新种子。而且即使某次产生的随机数Ri泄露了，但由于Ri又经一次EDE加密才产生新种子Vi+1，所以别人即使得到Ri也得不到Vi+1，从而得不到新随机数Ri+1。
随机数产生为1024位，即16组64位2进制数，且有最高为（第1024位2进制数）为1，所以该随机数高位在（16进制）10000000与FFFFFFFF之间。 think58.com

[来源：http://www.think58.com]

4.2 DES算法简介
自DES算法1977年公诸于世以来，人们一直对DES的安全性持怀疑态度，对密钥的长度、迭代次数及S盒的设计众说纷纭。从技术上说，对DES的批评主要集中在以下3个方面：作为区组密码，DES的加密单位仅有64位二进制，对于数据传输来说太小；密钥仅有56位二进制未免太短，各次迭代中使用的密钥K(i)是递推产生的，这种相关性降低了密码体制的安全性；实现替代函数Si所用的S盒的设计原理尚未公开，其中可能留有隐患。
针对以上DES的缺陷，人们提出了几种增强DES安全性的方法，主要有以下3种：
1） 三重DES算法
用3个不同密钥的三重加密，即为：
C=Ek3(Dk2(Ek1P))
P=Dk1(Ek2(Dk3C))
该方法为密码专家默克尔（Merkle）及赫尔曼（Hellman）推荐。据称，目前尚无人找到针对此方案的攻击方法。
2）具有独立子密钥的DES算法
每一轮迭代都使用一个不同的子密钥，而不是由一个56位二进制的密钥产生。由于16轮迭代的每轮使用一个48位二进制的密钥，所以这一方法可以增强DES的加密强度。
3）带有交换S盒的DES算法
比哈姆和沙米尔证明通过优化S盒的设计，甚至S盒本身的顺序，可以抵抗差分密码分析，以达到进一步增强DES算法的加密强度的目的。 think58好，好think58 [资料来源：THINK58.com]
5 算法实现
函数名: get_SystemStatus_W32
函数功能: 得到系统状态
输入: 无
输出: 系统状态字符串,ni:得到的字符串长度
流程图： 本文来自think58 [来源：http://think58.com]

[资料来源：www.THINK58.com]

think58好，好think58 [资料来源：http://www.THINK58.com]

copyright think58

[资料来源：http://THINK58.com]

图2 得到系统状态的方法示意图

[来源：http://think58.com]