現(xiàn)實(shí)世界隨機(jī)事件隨時(shí)都在發(fā)生印蔬，而計(jì)算機(jī)世界的隨機(jī)又是怎樣的呢浩姥？

在不同領(lǐng)域?qū)﹄S機(jī)數(shù)有不同的定義。這里就從計(jì)算機(jī)的角度去理解分歇，可以分為兩種——偽隨機(jī)數(shù)傀蓉、真隨機(jī)數(shù)。

真隨機(jī)數(shù)

真隨機(jī)數(shù)是非常難通過計(jì)算機(jī)得到的卿樱，而是使用物理現(xiàn)象才能得到僚害。比如擲錢幣、骰子繁调、轉(zhuǎn)輪萨蚕、使用電子元件的噪音、核裂變等等蹄胰。這樣的隨機(jī)數(shù)生成器叫做物理性隨機(jī)數(shù)生成器岳遥，它們的缺點(diǎn)是技術(shù)要求比較高。

其次也可以使用專門的設(shè)備裕寨，比如熱噪訊號(hào)浩蓉、量子力學(xué)的效應(yīng)、放射性元素的衰退輻射宾袜，或使用無(wú)法預(yù)測(cè)的現(xiàn)象捻艳，譬如用戶按鍵盤的位置與速度、用戶運(yùn)動(dòng)鼠標(biāo)的路徑坐標(biāo)等來產(chǎn)生庆猫。

也就是真隨機(jī)只有在現(xiàn)實(shí)的物理世界才能得到认轨，平時(shí)在計(jì)算機(jī)中使用的大都數(shù)都是偽隨機(jī)。

偽隨機(jī)數(shù)

顧名思義偽隨機(jī)數(shù)其實(shí)嚴(yán)格來講不是真真的隨機(jī)月培，一般情況下在計(jì)算機(jī)中通過一定算法得到的嘁字，并且在大量的隨機(jī)樣本情況下是可以推算出來的；

偽隨機(jī)數(shù)有一個(gè)重要的特征那就是在計(jì)算偽隨機(jī)數(shù)時(shí)假如使用的開始值（也稱種子）不變的話杉畜，那么偽隨機(jī)數(shù)的數(shù)序也不變纪蜒。

偽隨機(jī)數(shù)的優(yōu)點(diǎn)是它的計(jì)算比較簡(jiǎn)單，而且只使用少數(shù)數(shù)值很難推算出計(jì)算它的算法此叠。一般人們使用一個(gè)假的隨機(jī)數(shù)纯续，比如電腦上的時(shí)間作為計(jì)算偽隨機(jī)數(shù)的開始值。

C語(yǔ)言偽隨機(jī)算法

用來計(jì)算偽隨機(jī)數(shù)的函數(shù)被稱為隨機(jī)函數(shù)，使用隨機(jī)函數(shù)產(chǎn)生隨機(jī)數(shù)的算法稱為隨機(jī)數(shù)生成器杆烁。具體的算法如下牙丽。這里的種子意思就是隨機(jī)數(shù)的開始數(shù)值简卧。對(duì)應(yīng)到下面的代碼就是next變量兔魂。

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

int rand(void)                        // 生成偽隨機(jī)數(shù)
{
    next = next * 1103515245 + 12345;
    return (unsigned int) (next / 65536) % 32768;
}

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

一般情況下會(huì)用1970年元旦午夜0點(diǎn)到現(xiàn)在的秒數(shù)作為隨機(jī)序列運(yùn)算的初始化種子，
事實(shí)上這種產(chǎn)生隨機(jī)種子的方法有一定的缺陷性举娩。假設(shè)在一臺(tái)計(jì)算機(jī)上運(yùn)行批量執(zhí)行程序析校，程序執(zhí)行的時(shí)間是幾個(gè)ms，那么幾個(gè)相鄰程序的seed是一樣的铜涉，每次調(diào)用隨機(jī)數(shù)生成函數(shù)的結(jié)果也是一樣的智玻。

因?yàn)橄到y(tǒng)時(shí)間time是按照秒級(jí)來計(jì)算的，而程序執(zhí)行的時(shí)間是毫秒級(jí)芙代，倘若在一秒內(nèi)執(zhí)行多次程序吊奢，必然導(dǎo)致產(chǎn)生的隨機(jī)種子相同。

這里有一個(gè)用系統(tǒng)時(shí)間作為隨機(jī)種子的可被破解的例子：利用系統(tǒng)時(shí)間可預(yù)測(cè)破解java隨機(jī)數(shù)纹烹，有興趣的可以看一看

【 一些注意事項(xiàng)】：由于偽隨機(jī)數(shù)不是真的隨機(jī)數(shù)页滚，在有些方面它們不能被使用，例如在密碼學(xué)中使用偽隨機(jī)數(shù)要小心铺呵，因?yàn)槠淇捎?jì)算性是一個(gè)可以攻擊的地方裹驰。偽隨機(jī)數(shù)的一個(gè)特別大的優(yōu)點(diǎn)是它們的計(jì)算不需要外部的特殊硬件的支持，因此在計(jì)算機(jī)科學(xué)中偽隨機(jī)數(shù)依然被使用片挂。

隨機(jī)數(shù)生成算法介紹

線性同余方法

線性同余方法（LCG）它是根據(jù)遞歸公式：

其中A、B闷愤、M是產(chǎn)生器設(shè)定的常數(shù)整葡。LCG周期最大為M，但大部分時(shí)候都會(huì)小于M肝谭。A掘宪、B、M分別稱做乘數(shù)攘烛、增量和模數(shù)魏滚。使用線性同余生成隨機(jī)數(shù)的方法速度快，但對(duì)乘數(shù)坟漱、增量和模數(shù)的選取有一定的要求：

要令LCG達(dá)到最大周期鼠次，應(yīng)符合以下條件：

1. B,M互質(zhì)；
2. M的所有質(zhì)因子的積能整除A-1；
3. 若M是4的倍數(shù)腥寇，A-1也是成翩；
4. A,B,N_0都比M小赦役；
5. A,B是正整數(shù)麻敌。

出了上面的條件以外還有以下：

1. 多次使用線性同余公式產(chǎn)生的序列應(yīng)該看起來是隨機(jī)的，不循環(huán)的掂摔；
2. 乘數(shù)/增量與模數(shù)互質(zhì)术羔；
3. 這個(gè)函數(shù)能夠產(chǎn)生一個(gè)完整周期內(nèi)的所有隨機(jī)數(shù)，由模數(shù)控制乙漓；

可以看到上面介紹C語(yǔ)言隨機(jī)數(shù)生成算法就是線性同余方法级历。

從網(wǎng)上搜集了一些式子：

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

【注】：因?yàn)橥ㄟ^線性同余方法構(gòu)建的偽隨機(jī)數(shù)生成器的內(nèi)部狀態(tài)可以輕易地由其輸出演算得知，所以此種偽隨機(jī)數(shù)生成器屬于統(tǒng)計(jì)學(xué)偽隨機(jī)數(shù)生成器叭披。設(shè)計(jì)密碼學(xué)的應(yīng)用必須至少使用密碼學(xué)安全偽隨機(jī)數(shù)生成器寥殖，故需要避免由線性同余方法獲得的隨機(jī)數(shù)在密碼學(xué)中的應(yīng)用。

線性同余實(shí)現(xiàn)

unsigned int seed;

// 默認(rèn)使用系統(tǒng)時(shí)間為種子
// time(NULL) 返回從1970年元旦午夜0點(diǎn)到現(xiàn)在的秒數(shù)
void srand(unsigned int s = (unsigned int)time(NULL)) 
{
    seed = s;
}

// 使用了一種線性同余法涩蜘，得到的隨機(jī)數(shù)最大為(2^15-1),29為質(zhì)數(shù)中的一個(gè)
unsigned int rand()
{
    seed = (seed * 31 + 13) % ((1 << 15) - 1);   
    return seed;
}

高級(jí)的隨機(jī)數(shù)生成器

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;  
}

上面這個(gè)生成器只是把“線性同余”嚼贡，“移位輪轉(zhuǎn)”和“帶記憶乘法”這3種基本的隨機(jī)數(shù)發(fā)生法一起用，便獲得很好的效果皱坛。其中移位輪轉(zhuǎn)在很多加密算法中經(jīng)常用到编曼。

乘同余法

乘同余法和線性同余法非常相似。對(duì)比一下二者的公式

線性同余：

乘同余法：

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

數(shù)選取是有一定理論基礎(chǔ)的剩辟，否則所產(chǎn)生的隨機(jī)數(shù)的周期將較小掐场，相關(guān)性會(huì)較大。經(jīng)過前人檢驗(yàn)的兩組性能較好的素?cái)?shù)取模乘同余法迭代式的系數(shù)為:

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

代碼這里就不貼了

平方取中法

算法：
[圖片上傳失敗...(image-170cbf-1526008450174)]

換一種方式十進(jìn)制的表達(dá)：

對(duì)比上面可以寫成另外一種形式贩猎。

#define S 2  
Xn+1=(Xn^2/10^s)(mod 10^2s) 
Rn+1=Xn+1/10^2s
這里的s代表的就是位數(shù)

其中熊户，Xn+1是迭代算子，而 Rn+1 則是每次需要產(chǎn)生的隨機(jī)數(shù)吭服。 
第一個(gè)式子表示的是將 Xn 平方后右移 s 位嚷堡，并截右端的 2s 位。 
而第二個(gè)式子則是將截尾后的數(shù)字再壓縮 2s 倍艇棕，顯然 :0=<Rn+1<=1蝌戒。
迭代取中法有一個(gè)顯著的不良特性就是它比較容易退化成 0。

將上面的公式轉(zhuǎn)為代碼表示：x=(int)(x*x/pow(10.0,(m/2)))%(int)pow(10.0,m);

平法取中法的簡(jiǎn)單實(shí)現(xiàn)

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);//作用是將數(shù)字轉(zhuǎn)為字符串沼琉，并且制定轉(zhuǎn)換之后的進(jìn)制
    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)
    }
}

擴(kuò)展閱讀

線性同余方法
隨機(jī)數(shù)產(chǎn)生原理及應(yīng)用
使用線性同余法生成偽隨機(jī)數(shù)/序列（C++實(shí)現(xiàn)）
SecureRandom