真随机数

真随机数是非常难通过计算机得到的，而是使用物理现象才能得到。比如掷钱币、骰子、转轮、使用电子元件的噪音、核裂变等等。这样的随机数生成器叫做物理性随机数生成器，它们的缺点是技术要求比较高。

其次也可以使用专门的设备，比如热噪讯号、量子力学的效应、放射性元素的衰退辐射，或使用无法预测的现象，譬如用户按键盘的位置与速度、用户运动鼠标的路径坐标等来产生。

也就是真随机只有在现实的物理世界才能得到，平时在计算机中使用的大都数都是伪随机。

伪随机数

顾名思义伪随机数其实严格来讲不是真真的随机，一般情况下在计算机中通过一定算法得到的，并且在大量的随机样本情况下是可以推算出来的；

伪随机数有一个重要的特征那就是在计算伪随机数时假如使用的开始值（也称种子）不变的话，那么伪随机数的数序也不变。

伪随机数的优点是它的计算比较简单，而且只使用少数数值很难推算出计算它的算法。一般人们使用一个假的随机数，比如电脑上的时间作为计算伪随机数的开始值。

C语言伪随机算法

用来计算伪随机数的函数被称为随机函数，使用随机函数产生随机数的算法称为随机数生成器。具体的算法如下。这里的种子意思就是随机数的开始数值。对应到下面的代码就是next变量。

/* 使用 ANSI C 可移植算法 */
static unsigned long int next = 1;    // 种子

int rand(void)                        // 生成伪随机数
{
    next = next * 1103515245 + 12345;
    return (unsigned int) (next / 65536) % 32768;
}

void srand(unsigned int seed)         // 修改种子
{
    next = seed;
}

一般情况下会用1970年元旦午夜0点到现在的秒数作为随机序列运算的初始化种子，
事实上这种产生随机种子的方法有一定的缺陷性。假设在一台计算机上运行批量执行程序，程序执行的时间是几个ms，那么几个相邻程序的seed是一样的，每次调用随机数生成函数的结果也是一样的。

因为系统时间time是按照秒级来计算的，而程序执行的时间是毫秒级，倘若在一秒内执行多次程序，必然导致产生的随机种子相同。

这里有一个用系统时间作为随机种子的可被破解的例子：利用系统时间可预测破解java随机数，有兴趣的可以看一看

【一些注意事项】：由于伪随机数不是真的随机数，在有些方面它们不能被使用，例如在密码学中使用伪随机数要小心，因为其可计算性是一个可以攻击的地方。伪随机数的一个特别大的优点是它们的计算不需要外部的特殊硬件的支持，因此在计算机科学中伪随机数依然被使用。

随机数生成算法介绍

线性同余方法

线性同余方法（LCG）它是根据递归公式：

产生随机数的方法。线性同余中的线性，是指“线性”表示方程中 A 的次数是一次，mod 取余运算符则体现了“同余”这一数学概念。

其中A、B、M是产生器设定的常数。LCG周期最大为M，但大部分时候都会小于M。A、B、M分别称做乘数、增量和模数。使用线性同余生成随机数的方法速度快，但对乘数、增量和模数的选取有一定的要求：

要令LCG达到最大周期，应符合以下条件：

B,M互质；
M的所有质因子的积能整除A-1；
若M是4的倍数，A-1也是；
A,B,N_0都比M小；
A,B是正整数。

出了上面的条件以外还有以下：

多次使用线性同余公式产生的序列应该看起来是随机的，不循环的；
乘数/增量与模数互质；
这个函数能够产生一个完整周期内的所有随机数，由模数控制；

可以看到上面介绍C语言随机数生成算法就是线性同余方法。

从网上搜集了一些式子：

seed = (seed * 9301 + 49297) % 233280
seed = (seed * 31 + 13) % ((1 << 15) - 1);

【注】：因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知，所以此种伪随机数生成器属于统计学伪随机数生成器。设计密码学的应用必须至少使用密码学安全伪随机数生成器，故需要避免由线性同余方法获得的随机数在密码学中的应用。

线性同余实现

unsigned int seed;

// 默认使用系统时间为种子
// time(NULL) 返回从1970年元旦午夜0点到现在的秒数
void srand(unsigned int s = (unsigned int)time(NULL)) 
{
    seed = s;
}

// 使用了一种线性同余法，得到的随机数最大为(2^15-1),29为质数中的一个
unsigned int rand()
{
    seed = (seed * 31 + 13) % ((1 << 15) - 1);   
    return seed;
}

高级的随机数生成器

unsigned int x = 123456789,
                   y = 362436000,
                   z = 521288629,
                   c = 7654321; /* Seed variables */ 
 
unsigned int KISS()
{  
    unsigned long long t, A = 698769069ULL;  

    x = 69069*x+12345;  
    y ^= (y<<13); 
    y ^= (y>>17); 
    y ^= (y<<5);  
    
    t = (A*z + c);
    c = (t >> 32);
    z = t;
     
    return x+y+z;  
}

上面这个生成器只是把“线性同余”，“移位轮转”和“带记忆乘法”这3种基本的随机数发生法一起用，便获得很好的效果。其中移位轮转在很多加密算法中经常用到。

乘同余法

乘同余法和线性同余法非常相似。对比一下二者的公式

线性同余：

乘同余法：

Xn+1=Lamda*Xn(mod M)
Rn+1=Xn/M

数选取是有一定理论基础的，否则所产生的随机数的周期将较小，相关性会较大。经过前人检验的两组性能较好的素数取模乘同余法迭代式的系数为:

Lamda=5^5,M=2^35-31
Lamda=7^5,M=2^31-1

代码这里就不贴了

平方取中法

算法：
[图片上传失败...(image-170cbf-1526008450174)]

换一种方式十进制的表达：

对比上面可以写成另外一种形式。

#define S 2  
Xn+1=(Xn^2/10^s)(mod 10^2s) 
Rn+1=Xn+1/10^2s
这里的s代表的就是位数

其中，Xn+1是迭代算子，而 Rn+1 则是每次需要产生的随机数。 
第一个式子表示的是将 Xn 平方后右移 s 位，并截右端的 2s 位。 
而第二个式子则是将截尾后的数字再压缩 2s 倍，显然 :0=<Rn+1<=1。
迭代取中法有一个显著的不良特性就是它比较容易退化成 0。

将上面的公式转为代码表示：x=(int)(x*x/pow(10.0,(m/2)))%(int)pow(10.0,m);

平法取中法的简单实现

void randomTest() {
    int x,i = 0;
    double m;
    char str[25];
    printf("please input a int number");
    scanf("%d", &x);
    if (x < 0) {
        printf("error! enter again:");
        scanf("%d", &x);
    }
    itoa(x, str, 10);//作用是将数字转为字符串，并且制定转换之后的进制
    m = strlen(str);
    
    while (i <= 99) {
        x=(int)(x*x/pow(10.0,(m/2)))%(int)pow(10.0,m);
        printf("x%d=%d\n", ++i, x)
    }
}