基于模式與熵的隨機序列研究

崔圓圓 北京郵電大學電子信息工程專業 100876

基于模式與熵的隨機序列研究

崔圓圓 北京郵電大學電子信息工程專業 100876

本文從雙色球開獎結果出發，探討真隨機序列中暗含的“模式”：真隨機序列有時表現得并不那么“隨機”。這是因為人們認為，隨機應是無序的。事實證明，并非如此。另一方面，人為產生的偽隨機序列，大多經過了消除重復的步驟以使序列本身較為“隨機”——看起來是無序的。本文使用Mersenne Twis算ter 法產生偽隨機序列，測試這種人為因素對隨機序列統計特性的影響。為了進一步研究“無序”序列與隨機序列的差異，本文基于熵，提出了一種簡便的偽隨機數發生器。通過對有序序列進行次數可控的交換來逐步實現無序化。對無序化后的序列進行均勻性和圖像加密測試。通過無序的方法產生的序列，其隨機性在一定范圍內是可以信賴的。

真偽隨機序列;模式;熵 ;Mersenne Twister算法;圖像加密

1.形形色色的隨機數

在自然界和人類社會中存在著兩類現象，確定性現象和非確定性現象。前者在一定條件下必然發生；對于后者，其結果的樣本空間非但并不唯一，大多數時候甚至難以計量。非確定性現象，或者說隨機現象，經過大量的重復試驗或觀察，總能表現出一定的統計規律性。隨機數根據其產生機理，可分為兩種：真隨機數與偽隨機數。前者由物理采樣方法得到，后者來自于數學計算。

2.隨機序列與模式

2.1 真隨機數及其特征

真隨機數源有很多，包括人為隨機源、設備隨機源、電路中的熱噪聲和散粒噪聲，等等。電腦的操作系統就能夠實現對如鍵盤隨機性、鼠標隨機性、中斷隨機性等的統一控制，以產生符合要求的隨機數。即使是真隨機數發生器的設計者，也不可能知道實際生成的隨機序列的內容，生成的隨機數是真正無法預測的。

2.2 真隨機與假模式

2.2.1 預測的模式

隨機現象的本質是不確定性。研究表明，“我們在不確定局面下進行評估和選擇時，常常會依賴于直覺”。面對隨機序列，我們所要做出的判斷并不會威脅自身的安全，僅僅是個小小的判斷。這時候，模式的思維就占了上風。

2.2.2 雙色球中的幸運

在中國，目前雙色球是一種較流行的博彩方式：投注區分為紅球號碼區和藍球號碼區，紅球號碼范圍為01～33，藍球號碼范圍為01～16。雙色球每期從33個紅球中開出6個號碼，從16個藍球中開出1個號碼作為中獎號碼，雙色球玩法即是競猜開獎號碼的6個紅球號碼和1個藍球號碼，順序不限。考慮到16是2的四次冪，便于后文的二進制計算，本文取每一期的藍球號碼作為真隨機序列。

毫無疑問，每一次的藍球數字都是隨機產生的。現在，讓我們再來看看前一節所提到的ABCDE五個數字序列。印象中最為隨機不可預測的序列，竟然表現出了驚人的“模式”。不得不相信，這些模式，僅僅是湊巧的結果。一方面，概率學的知識告訴我們，產生任何一種排列，都是有可能的，而這些模式，只是無數可能排列中的一種而已；另一方面，真隨機序列，原來有時候看起來并不那么“隨機”。

2.2.3 統計性驗證

用于描述隨機序列的兩個主要指標就是期望和方差。數學期望體現了隨機變量的真正平均，而方差則代表隨機變量的取值與其方差的偏離程度。

對于理想的從1～16等可能取值的隨機序列，其數學期望和方差分別為：

取最近200期的藍球開獎結果，計算其平均值與方差：

可見，即使沒有數量龐大的樣本（只取了200個），真隨機序列在統計特性上的表現，仍是十分優越的。真隨機序列中暗含的“模式”，讓它看起來不那么隨機了。

2.3 偽隨機序列

與真隨機序列相對的，就是假隨機序列。一般計算機中使用的偽隨機序列，都是通過遞推公式計算得來。這種生成裝置，稱為偽隨機數發生：由一個初始狀態（種子）開始，通過一個確定的算法來生成隨機數。

另一種廣泛使用的PRNG，是Mersenne Twister算法（馬特賽特旋轉演算法）。

1997 年，松本和西村開發了這一基于有限二進制字段上矩陣線性再生的偽隨機數算法。它的算法隨機性好，易實現，占用內存少，產生隨機數的速度快、周期長，且具有623維均勻分布的性質。 在MATLAB v7.7 及以上版本中，通過調用RandStream類，就能產生基于MT的偽隨機數。

2.4 兩種隨機數的比較

將Matlab自帶的隨機序列生成器設為“mt19937ar”，便可以得到基于MT算法的偽隨機序列。為了與雙色球的真隨機數作比較，產生多組200個同區間均勻分布的偽隨機數。計算數學期望與方差，可得：

可以看到，Matlab產生的偽隨機數偏離理想均值8.5的程度比雙色球大，其波動卻相對較小。

使用隨機數生成算法連續生成的2 0 0個隨機數，耦合成199個像素坐標值。Dn表示第n個像素點，以此衡量數據的均勻性。作圖后可見，兩者的均勻性相似。如果取值空間更大，而不是1至16，應當會出現一定的差異。

3.基于熵的偽隨機序列發生器

3.1 物理熵

1850 年，德國物理學家魯道夫·克勞修斯首次提出熵的概念，用來表示任何一種能量在空間中分布的均勻程度。一個體系的能量完全均勻分布時，這個系統的熵就達到最大值。系統的熵，只能逐漸增大或保持不變，而不可能逐漸減小。在物理學中，熵代表著系統的無序性。越是均勻無序的系統，其熵值越大。

3.2 信息熵

信息論的創始人香農，率先將熵的概念進行了泛化，引入信息熵。對于有限離散隨機變量集合，當集合中的等概率發生時，熵達到最大值。對于隨機序列，當取值均勻分布時，熵達到最大值。熵標志著系統的無序性，當序列變得無序，熵也不斷增大，逼近均勻分布。

3.3 基于熵的發生器

構建一個序列，由四個從0到255的連續升序排列（0,1,2,...255）組成。顯然，這一序列是非常有序的。根據前一小節的分析，如果不斷打亂其排序，序列的熵就會不斷增加，逼近最大值。這時，就有可能得到了一個偽隨機序列。

在原序列基礎上，每次隨機選取兩個序號，交換其值，進行實驗。根據期望和方差的定義，由于打亂后的序列，其各個數字的數量維持在4不變，因此均值和方差與理想序列相同。

3.3.1 均勻性測試

按照第二部分中介紹過的均勻性衡量方法，取序列的前256個值作圖。記k為交換的次數，分別做出k=0,100,200,300, 400,500時的均勻性分布圖。

未做交換時，原圖是一條直線。隨著k的值不斷增大，點越來越分散。k=500時，仍能看出原圖的痕跡。對于使用這種擾亂的方法構造的1024個數字組成的序列，在交換500次時，隨機性仍不理想。

當交換次數達到600時，點的分布已找不到原始的規律；隨著交換不斷增加，均勻性狀況不再改變。對于一個長度為2n的序列，交換n次時，可基本無序。

3.3.2 無序程度測試

在未進行交換時，1024個點，每個都在自己的初始位置。現每交換100次后，測試仍在初始位置的點的個數，它表現出了明顯的下降趨勢，并且在3200次之后開始波動，不再單一遞減。可以推測，對于長為n的序列，當交換3n次時，無序狀況基本穩定。

3.3.3 圖像加密測試

以大小為256×256的256級灰度的Lena圖像為例，明文為是一個256×256的8bit的2進制矩陣，通過reshape整合運算，將算法生成的隨機數轉換成為一個256×256的密鑰矩陣，然后再將明文矩陣與密鑰矩陣按位異或。當交換次數改變時，加密效果有所不同。交換400次后，仍能看出原圖的痕跡；交換800次后，逐漸變得模糊；交換1200次后，已經完全看不出Lena的樣子了。對于一個長度為n的序列，進行n次交換后，已達到較好的圖像加密效果。

[1]胡細寶,孫洪祥,王麗霞.概率論·隨機過程·數理統計.北京郵電大學出版社.2004年2月,第一版

[2]列納德·蒙洛迪諾[英]著；郭斯羽譯.醉漢的腳步——隨機性如何主宰我們的生活.湖南科學技術出版社.2010年6月,第一版

10.3969/j.issn.1001-8972.2011.11.012

崔圓圓，北京郵電大學電子信息工程專業本科生，在讀。