随机数定义
根据密码学原理，随机数的随机性检验可以分为三个标准：
1.统计学伪随机性。
统计学伪随机性指的是在给定的随机比特流样本中，1的数量大致等于0的数量，同理，“10”“01”“00”“11”四者数量大致相等。
类似的标准被称为统计学随机性。满足这类要求的数字在人类“一眼看上去”是随机的。
2.密码学安全伪随机性。
其定义为，给定随机样本的一部分和随机算法，不能有效的演算出随机样本的剩余部分。
3.真随机性。
其定义为随机样本不可重现。实际上只要给定边界条件，真随机数并不存在。
可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉（比如计算机当地的本底辐射波动值），可以认为用这个方法演算出来了真随机数。
相应的，随机数也分为三类：
- 伪随机数：满足第一个条件的随机数。
- 密码学安全的伪随机数：同时满足前两个条件的随机数。可以通过密码学安全伪随机数生成器计算得出。
- 真随机数：同时满足三个条件的随机数。
生成伪随机数算法
伪随机数生成算法，也叫伪随机数生成器(Pseudo Random Number Generator，简称 PRNG)1
伪随机数序列，其实是确定的，只是看上去随机。比如在线性同余法中，当第一数确定后， 后续的值也就确定了。
生成n个随机数 \( x_1, x_2, …, x_n \)
可以使用一个 4 元组\( (Q, \sigma, \Sigma, f)\) 定义一个伪随机数生成算法， 其中:
- \( Q 是有限状态集合， \)
- \(\sigma\) 为状态转移函数，
- \(\Sigma\) 是有限输出集合，
- \(f 是从 Q 到 \Sigma 的单射。\)
当需要一个伪随机数序列时，设定初始状态 \( q_0 \in Q \) ，每一次输出都由如下两个过程组成
- \( q_{n} = \sigma(q_{n-1}) \)
- \( output_n = f(q_n), output_n \in \Sigma \)
Linear congruential generator(线性同余法)
- a是乘数，b为增量，m为模数,\(x_0\)是种子数
- 一般而言，m是2的高次冪(\(2^{32}或2^{64}\)), \(0<a<m,0<=b<m,0<x_0<m\)
- 一般选取：\( a=4p+1, b=2q+1,其中p,q是正整数 \) 2
- m越大，序列的周期越长, a和b越大产生的伪随机数越均匀
- a和m互质，产生的随机数效果比不互质好
- LCG不能用于随机数要求高的场合，不能用于加密应用。
- 有些场合LCG有很好的应用，例如内存很紧张的嵌入式中，电子游戏控制台用的小整数，使用高位可以胜任。
rand = 1
def Lcg():
a = 69069
b = 1
m = 1<<22
global rand
rand = (a * rand + b) %m
return rand
平法取中法
1964年由冯.诺依曼提出。基本思路：将数列中\(x_i\)(假设有m位)平方，取得到2m位数(不足2m位，在最高位前面补0) 取正中间m位数字，作为\(x_{i+1}\),由此产生一个伪随即数列。
rand = 1
def middle_square():
global rand
m = 16
rand = rand ** 2
rand = (rand // 10**8) % 10**8
return rand