一種產(chǎn)生隨機數(shù)的數(shù)學(xué)方法

陳華賢

關(guān)鍵詞：隨機數(shù)；函數(shù)；進制轉(zhuǎn)換；無理數(shù)；超大整數(shù)

1引言

如今，各行業(yè)尤其是計算機領(lǐng)域?qū)﹄S機數(shù)的需求量很大，因此，迫切需要一種高效和低成本產(chǎn)生隨機數(shù)的方法。但是，在傳統(tǒng)的科學(xué)觀點中，在計算機上是不可能產(chǎn)生真正的隨機數(shù)的。美國著名計算機學(xué)家馮·諾依曼曾經(jīng)說過：“任何人考慮用數(shù)學(xué)的方法產(chǎn)生隨機數(shù)肯定是不合情理的”。能否找到一種產(chǎn)生隨機數(shù)序列的數(shù)學(xué)方法，本文認為是可以的。事實上，隨機數(shù)并不難獲得。

2產(chǎn)生隨機數(shù)的數(shù)學(xué)方法

2.1靈感來源

本數(shù)學(xué)方法的靈感來源于無理數(shù)。比如，針對無理數(shù)π，數(shù)學(xué)家對它進行了深入研究，即π是無限不循環(huán)小數(shù)，利用泰勒級數(shù)或者其他計算方法可以將其無限地計算下去。據(jù)悉，現(xiàn)在科學(xué)家已將π計算到小數(shù)點后萬億位。而π數(shù)位上的數(shù)字擁有的特點是：（1）無限性，即可以無限計算下去；（2）無周期性，沒有周期不會出現(xiàn)循環(huán)；（3）隨機性和不可預(yù)測性，數(shù)位上的數(shù)字沒有特別的規(guī)律，而且相互獨立，無法通過已知數(shù)位上的數(shù)字推測未知數(shù)位上的數(shù)字；（4）均勻性，每個數(shù)位上的數(shù)字（0～9）出現(xiàn)的概率均等，即每個數(shù)字出現(xiàn)的概率都接近10％；（5）可復(fù)現(xiàn)性，即π數(shù)位上的數(shù)字通過重復(fù)計算較易重現(xiàn)，對于加密算法而言，該特性使它不用占據(jù)大量的存儲空間，在加密或者解密環(huán)節(jié)把數(shù)字重新計算出來即可，可以不提前儲存。

從上文對無理數(shù)π的分析可見，π數(shù)位上的數(shù)字符合真隨機數(shù)的特點，因此，可以把它們看成是隨機數(shù)。同時，可以大膽推斷：存在一類無理數(shù)，其數(shù)位上的數(shù)字也具有類似仃的特征，即無限性、無周期性、隨機性、均勻性和可復(fù)現(xiàn)性。當(dāng)然，基于此可以再引申：存在一類有理數(shù)，其周期很長，有成百上千位，在它們的某個周期內(nèi)，數(shù)位上的數(shù)字會隨機出現(xiàn)，即可以將它們看成是隨機數(shù)。

2.2產(chǎn)生隨機數(shù)具體的數(shù)學(xué)方法

既然無理數(shù)和有理數(shù)都可以作為隨機數(shù)的來源，那么可以從求解無理數(shù)π的方法中得到啟示。求解π的方法很多，最直接的方式就是用泰勒級數(shù)進行求值計算。而通過觀察泰勒級數(shù)的形式，暫且不論它的數(shù)學(xué)本質(zhì)，單就運算形式而言，可以發(fā)現(xiàn)它其實就是初等函數(shù)之間的加減乘除運算。這些基本數(shù)學(xué)運算和初等函數(shù)的計算方法在現(xiàn)代計算機上已經(jīng)能夠?qū)崿F(xiàn)。另外，從獲取隨機數(shù)的角度來看，并不需要小數(shù)點，因此，π的小數(shù)點可以去掉。而π去掉小數(shù)點后，會變成一個無限長的超大整數(shù)。在此，把位數(shù)超過一百位的十進制數(shù)字稱為超大整數(shù)，簡稱超大數(shù)。對于某個通過函數(shù)隨機運算確定的超大數(shù)而言，和仃類似，它的數(shù)位上的數(shù)字出現(xiàn)是沒有規(guī)律的，也無法預(yù)測，即無法通過已知數(shù)位上的數(shù)字推測未知數(shù)位上的數(shù)字。受此啟發(fā)，可以利用現(xiàn)成的大數(shù)運算庫，用隨機設(shè)計的函數(shù)去計算超大數(shù)，進而得到隨機數(shù)數(shù)字序列。

本數(shù)學(xué)方法的核心就是通過設(shè)計函數(shù)去計算超大整數(shù)，然后把超大整數(shù)數(shù)位上的數(shù)字看成隨機數(shù)，從而達到本文的目的。同時，可以對計算出來的超大數(shù)進行進制轉(zhuǎn)換，然后得到指定范圍內(nèi)的隨機數(shù)。關(guān)于設(shè)計函數(shù)和進制轉(zhuǎn)換的細節(jié)，下文將進一步討論。

2.2.1設(shè)計初等函數(shù)求解超大數(shù)

顯然初等函數(shù)有無限種形式且具有隨機性，而自變量的值也不盡相同，存在差異。因此，有理由相信通過隨機設(shè)計的函數(shù)計算出來的數(shù)值也具有隨機性。這就是本文方法能夠獲取隨機數(shù)的本質(zhì)。在具體的上機實驗中，采用微軟．net的大數(shù)運算庫。利用該運算庫，結(jié)合本文設(shè)計的函數(shù)（包括多元函數(shù)），可以計算出位數(shù)高達百萬位的超大整數(shù)。從實驗結(jié)果來看，以此計算出來的超大數(shù)，其數(shù)位上的數(shù)字具有無限性、無周期性、隨機性、均勻性和可復(fù)現(xiàn)性等特征。這些特征符合上文分析無理數(shù)π時所總結(jié)的性質(zhì)。同時，在上機實驗中獲得的隨機數(shù)樣本能夠通過相關(guān)統(tǒng)計學(xué)軟件的測試。

可以看出，以上函數(shù)都是常見的初等函數(shù)的復(fù)合函數(shù)，它們是隨機設(shè)計的。而通過隨機設(shè)計的函數(shù)來計算超大數(shù)，并把超大數(shù)數(shù)位上的數(shù)字當(dāng)成隨機數(shù)來源的方法，簡單便利，實現(xiàn)門檻低，這是本數(shù)學(xué)方法的創(chuàng)新之處。值得注意的是，在需要多個密鑰的密碼學(xué)應(yīng)用場景下，函數(shù)可以設(shè)計成多元的，每個自變量對應(yīng)一個密鑰。多元函數(shù)體現(xiàn)了本文方法的靈活性。

2.2.2利用函數(shù)矩陣來計算超大數(shù)

如圖1所示，由函數(shù)構(gòu)成的矩陣簡稱函數(shù)矩陣，顯然它與2.2.1節(jié)討論的初等函數(shù)一樣，具有無限種形式。它的橫向為初等函數(shù)的加減乘除；縱向是對橫向計算結(jié)果1至結(jié)果n的字符串連接，即對橫向計算出來的超大數(shù)字直接進行首尾相連。在此，用符號“&”表示字符串連接運算。之所以用字符串連接，是為了提高求值效率，同時加強隨機性。另外，如果把該方法應(yīng)用到密碼學(xué)領(lǐng)域，即對數(shù)據(jù)進行加密，字符串連接運算也可以增強密碼安全性，使加密算法更難被破解[2]。

函數(shù)矩陣的形式本身具有隨機性，也可以采用多個自變量（即多元函數(shù)矩陣）來快速計算超大整數(shù)。建議利用隨機化的系數(shù)初始化函數(shù)矩陣，然后將數(shù)字代入函數(shù)矩陣求值即可。如何設(shè)計函數(shù)矩陣，并使性能最優(yōu)化還需要進一步討論。

下文舉例說明用函數(shù)矩陣計算超大數(shù)，進而獲取隨機數(shù)的方法。假如是一元函數(shù)矩陣，那么可以設(shè)計函數(shù)矩陣如下：

2.2.3進制轉(zhuǎn)換

在以上兩個例子中，所得隨機數(shù)集合都是0～9范圍內(nèi)的整數(shù)，如何才能得到指定范圍內(nèi)的隨機數(shù)集合？比如，要得到O～p的隨機數(shù)集合，設(shè)p為大于等于1的正整數(shù)。其實處理方式也很簡單，對計算出來的超大數(shù)進行進制轉(zhuǎn)換即可。把超大數(shù)轉(zhuǎn)換為二進制，因為二進制數(shù)字中數(shù)位上只能是0～1的數(shù)字，所以可得0和1的隨機數(shù)集合：把超大數(shù)轉(zhuǎn)換為十六進制，而十六進制數(shù)字數(shù)位上的數(shù)字范圍是0～15，因此，可以得到0～15的隨機數(shù)集合?？傊?，把超大數(shù)轉(zhuǎn)換為p+l進制后，可以得到0～p的隨機數(shù)集合。

需要注意的是，p需要遠小于超大數(shù)才能使進制轉(zhuǎn)換后的隨機數(shù)集合更加均勻，這是基本的邏輯推理，下文將繼續(xù)討論均勻性。同一個超大數(shù)可以轉(zhuǎn)換為不同進制，得到不同的隨機數(shù)集合。

表3是采用上文設(shè)計的函數(shù)矩陣（x）循環(huán)計算超大數(shù)，并依次對各超大數(shù)進行進制轉(zhuǎn)換后，獲得隨機數(shù)集合中各數(shù)字出現(xiàn)的次數(shù)統(tǒng)計表。其中，設(shè)進制數(shù)p+1=2，即p為1。

設(shè)進制數(shù)p+1=16，即p為15時，數(shù)字出現(xiàn)次數(shù)統(tǒng)計如表4所列。

從上機實驗結(jié)果來看，若采用的數(shù)學(xué)函數(shù)和進制數(shù)相同，則生成的隨機數(shù)數(shù)量越多，隨機數(shù)分布的概率將更加均勻。這其實就是均勻性，也是本數(shù)學(xué)方法生成的隨機數(shù)的特性之一。

以上結(jié)論有實驗數(shù)據(jù)支持，下文采用的仍然是函數(shù)矩陣（x），當(dāng)進制數(shù)為2時，各數(shù)量級的隨機數(shù)樣本的數(shù)字出現(xiàn)情況統(tǒng)計如表5、表6、表7所列，可見實驗得到的隨機數(shù)確實是很均勻的。

在實驗中，可以觀察到變異系數(shù)c（變異系數(shù)c=（標(biāo)準(zhǔn)偏差SD/平均值Mean）×100%）的值隨著隨機數(shù)數(shù)量級的增加而減少，如下表8所列。

從理論上說，進制轉(zhuǎn)換并沒有限制進制數(shù)的上限，滿足進制數(shù)遠小于當(dāng)前的超大數(shù)即可，而超大數(shù)本身也沒有大小限制。因此，利用本文方法生成的隨機數(shù)并無大小限制。這種特性也是傳統(tǒng)隨機數(shù)算法所沒有的，屬于本文方法的創(chuàng)新點之一?？傊M制轉(zhuǎn)換解決了如何均勻地獲取指定范圍內(nèi)隨機數(shù)的問題。

2.3所得隨機數(shù)樣本的統(tǒng)計檢驗

采用IBM公司的SPSS軟件對隨機數(shù)樣本進行統(tǒng)計檢驗，如圖2、圖3所示。SPSS為IBM公司推出的一系列用于統(tǒng)計學(xué)分析運算、數(shù)據(jù)挖掘、預(yù)測分析和決策支持任務(wù)的軟件產(chǎn)品及相關(guān)服務(wù)的總稱，有Windows和Mac OS X等版本。實驗所用版本是28.0.1.1（15），對本數(shù)學(xué)方法生成的某個隨機數(shù)樣本進行檢測，結(jié)果符合隨機性假設(shè)，這也是本數(shù)學(xué)方法的技術(shù)佐證。在一般場合，也可以通過隨機數(shù)校驗算法對獲得的隨機數(shù)進行檢驗，驗證其隨機性。

3對本數(shù)學(xué)方法的計算機算法描述

因為本數(shù)學(xué)方法的靈感來源于無理數(shù)，所以把實現(xiàn)它的計算機算法命名為無理數(shù)隨機數(shù)生成算法。本算法很靈活．可以采用不同的函數(shù)來計算超大數(shù)（圖4），因此，擁有無限多個實例。要注意的是，下文算法實例中用到了大數(shù)運算庫Biglnteger，其中BigInteger.Pow方法表示對大數(shù)進行冪函數(shù)運算。以下是某個實例的具體算法描述：省略流程圖。但是要注意，可以計算超大數(shù)的函數(shù)很多，getBigNumFun只是其中一種，而這樣的函數(shù)也不難設(shè)計。從數(shù)學(xué)形式上看，沒必要用到微積分，但微積分學(xué)中的泰勒級數(shù)理論給了我們很重要的啟示。過程myChangeFormat（圖5）表示對計算出來的超大數(shù)進行進制轉(zhuǎn)換，并把進制轉(zhuǎn)換后的該超大數(shù)各數(shù)位上的數(shù)字存儲到數(shù)據(jù)列表dList中，從而得到一定范圍內(nèi)的隨機數(shù)集合。它們的偽代碼如下：

4本數(shù)學(xué)方法的優(yōu)缺點分析

與傳統(tǒng)的隨機數(shù)算法相比，本文方法具備的主要優(yōu)勢是：（1）無周期性，把生成超大數(shù)的函數(shù)設(shè)計成非周期性的即可，而這樣的函數(shù)有很多，有很大的選擇空間；（2）無限性，只要計算和存儲資源足夠，在生成超大數(shù)的函數(shù)理論上可以無限計算下去，因此，可以產(chǎn)生無限多數(shù)量的隨機數(shù)；（3）可復(fù)現(xiàn)性，本文方法靈活應(yīng)用數(shù)學(xué)函數(shù)，函數(shù)形式不唯一，而且只要確定函數(shù)形式和自變量，那么計算出來的超大數(shù)就是確定的，因此，本文方法獲取的隨機數(shù)很容易復(fù)現(xiàn)，不需要物理采集和占用存儲，簡便且效率高；（4）隨機數(shù)無大小限制，因為超大數(shù)在理論上是無大小限制的，因此，進制數(shù)也應(yīng)該沒有大小限制，所以，只要計算和存儲資源允許，我們能夠得到任意數(shù)量和任意大小的隨機數(shù)集合；（5）靈活性強、實現(xiàn)簡便、代價低，本數(shù)學(xué)方法完全可以在民用計算機上實現(xiàn)，是一種低門檻、低成本，大批量獲得隨機數(shù)的新方式，又因為任何人都可以定制生成隨機數(shù)的函數(shù)，因此，它具有很強的靈活性；（6）隨機性和均勻性都很強，函數(shù)形式和自變量的隨機性造就了超大數(shù)的隨機性，而既然是隨機的，那么各數(shù)字的出現(xiàn)概率也應(yīng)該相等，即均勻性。

本數(shù)學(xué)方法的不足之處在于理論上需要繼續(xù)完善，主要是隨機性和均勻性的嚴(yán)格數(shù)學(xué)證明。在實際應(yīng)用中，可以增加隨機性和均勻性的檢驗環(huán)節(jié)，對本數(shù)學(xué)方法產(chǎn)生的隨機數(shù)集合進行檢驗，從而在一定程度上彌補理論上的不足。

5本數(shù)學(xué)方法的應(yīng)用展望

5.1本數(shù)學(xué)方法可以改良一次一密算法

因為本文方法可以生成概率均勻的隨機數(shù)集合，所以可以改良當(dāng)前安全性高但實用性不強的一次一密算法。一次一密算法是具備完善保密性、安全性較高的對稱加密算法。一個加密方案是完善保密的，即使攻擊者擁有無限計算資源，也不可能從密文中分析出關(guān)于明文的任何信息。此前，如果采用一次一密算法對1GB的文件進行加密，則生成和管理1GB大小的密鑰，造成存儲空間的極大浪費。而如果采用本數(shù)學(xué)方法，保存生成超大數(shù)的函數(shù)和相關(guān)變量即可，在需要加密或解密時，再計算出隨機數(shù)，能節(jié)省50%左右的存儲空間。因此，本數(shù)學(xué)方法最直接的應(yīng)用在于改良一次一密算法。當(dāng)然，概率分布均勻的隨機數(shù)集合的應(yīng)用還很多，可以逐步發(fā)掘它的潛力。

5.2本數(shù)學(xué)方法可以檢驗量子計算機的計算正確性

目前，已有研究者用計算π的超精密值（通常是小數(shù)點后萬億位以上）來驗證計算機的準(zhǔn)確性。如上文所述，π去掉小數(shù)點后其實就是一個超大數(shù)，而本文方法可以通過設(shè)計某個函數(shù)（或函數(shù)矩陣）來計算超大數(shù)，因此，可以用該方式去檢驗量子計算機的正確性。因為擁有大量位數(shù)（如萬萬億位十進制形式）的超大數(shù)不容易獲得，需要通過超級計算機計算得到。而顯然只要對比量子計算機的計算結(jié)果與傳統(tǒng)超級計算機的計算結(jié)果是否一致，就能檢驗量子計算機的計算正確性。本數(shù)學(xué)方法生成的超大數(shù)沒有大小限制且具有可復(fù)現(xiàn)性，因此它為相關(guān)檢驗工作提供了便利，是一種比較新的思路。

5.3本數(shù)學(xué)方法可以抵御量子計算機的威脅

因為量子計算機的強大計算能力，傳統(tǒng)的非對稱加密算法（如RSA）已經(jīng)可以在較短時間內(nèi)被它破解，因此，迫切需要一種新的加密機制保護關(guān)鍵數(shù)據(jù)。一次一密算法是傳統(tǒng)的對稱加密算法，具有完善保密性，可以抵御量子計算機的攻擊。上文提道，本數(shù)學(xué)方法可以大大改良一次一密算法，因此，未來可能會廣泛采用改良后的一次一密算法對關(guān)鍵數(shù)據(jù)進行加密，因為它的安全性較高。

5.4對本數(shù)學(xué)方法的總結(jié)

總之，本數(shù)學(xué)方法的技術(shù)可行性較強、應(yīng)用前景廣闊，需要多加研究和討論，使其不斷完善。本文方法既有理論支撐，也有技術(shù)支持，偏重技術(shù)實現(xiàn)。本文方法可以直接應(yīng)用于密碼學(xué)，能以較低的代價換取較高的安全性方面的收益，不失為一種新的加密方案，尤其在民用和商用等非關(guān)鍵數(shù)據(jù)的加密方面完全可以勝任。