[發明專利]乘同余隨機數生成器的譜測試方法

在審

• 申請號: 201410598989.0
• 申請日: 2014-10-30
• 公開（公告）號: CN104714775A
• 公開（公告）日: 2015-06-17
• 發明（設計）人: 中澤宏;中澤直也
• 申請（專利權）人: 中澤宏
• 主分類號: G06F7/58
• 分類號: G06F7/58
• 代理公司: 北京潤平知識產權代理有限公司 11283
• 代理人: 陳瀟瀟;肖冰濱

技術領域

本發明涉及新的譜測試方法。目的是創新性地改進這些方法為在計算機上的均勻且獨立隨機數選擇并產生良好的乘同余生成器。更具體地，本發明提出了自由度為L的新的譜測試，其中L≥3，并給出了具有更可靠估值，幫助(salvage)目前被忽視的優秀的生成器，以及提供消除不適當的生成器的更敏銳的標準。我們在本文中用(d,z,n)表示乘同余隨機數生成器，包括自然數d＞0表示模數，整數z表示乘數并與d互質，以及整數n定義初始隨機數，也與d互質。生成器(d,z,n)或簡化成(d,z)產生整數序列{n_k≡nz^k-1?mod(d)|0<n_k<d,k＝1,2,···}，作為遞歸等價關系的解

n₁:≡n?mod(d),n_k+1:≡zn_k?mod(d),0<n_k<d,k＝1,2,···。

在計算機上，(d,z,n)生成器的輸出是實數v_k:＝n_k/d，其是連續放出的，其中0<v_k<1，k＝1,2,···，作為均勻且獨立隨機數序列。

背景技術

我們首先需要的是對已有譜測試的結構的思考。對(d,z)生成器的第L度譜測試旨在尤其評估放出的L個連續隨機數的獨立性程度。方法采用來自生成器(d,z)的L個連續整數輸出{Q_k:＝(n_k,n_k+1,···,n_k+L-1)|k＝1,2,···}，并將其認為是L維歐幾里得空間E_L中的點。基本事實是這些點{Q₁,Q₂,···}在由d和z確定的點陣G_L(d,z)中。更清楚地說，L個連續隨機數的點序列位于由d和z確定并表示為G_L(d,z)的點陣的點陣點中。方法很少關注而非不關注(d,z)輸出的位置選擇過程。關注點在對E_L中點陣G_L(d,z)預備的位置分布的評估，這種結構是否足夠作為用于均勻且獨立隨機數的位置。這句話的意思通過可見示例可以清楚理解，該示例是連續2元組的(d,z)隨機數給出的歐幾里得平面E₂中的點陣G₂(d,z)。參見圖1，示出了由(d,z)生成器放出的一個周期內的點{Q_k:＝(n_k,n_k+1)|k＝1,2,···}的圖，其中d是奇質數，z是其原根。(d,z)的值被選得小，由此圖看被肉眼辨認。點位于從原點O開始邊長為d的正方形C_d中；示出的外框顯示為稍大的正方形。開始的圖示出了接近由正三角形形成的所謂的三角形點陣的放出的點的整齊陣列。如果隨機數的連續2元組希望以某種隨機觀察的方式位于這些整齊分布的位置，我們沒有理由否定統計學假設：隨機數的連續2元組獨立且均勻出現。相反，看圖1的最后，點陣點的這種分布看起來聚集在彼此間有明顯大間隔的一些不同的線上。如果2元組的點出現在這種類型的位置，我們找到其分布的強方向相關性，暗示我們連續隨機數或其對似乎與不確定的獨立性相關。譜檢測給出數ρ₂(d,z)>1作為對(d,z)生成器的這些印象的定量評估；參見圖1，針對G₂(d,z)點陣表示的ρ＝ρ₂(d,z)，可以理解ρ從上越接近1越好。

發明內容

我們描述本發明的新思想。我們回到L元(d,z)隨機數中出現的點陣結構的數學表達，從最簡單的L＝2的情況開始。連續2元組Q_k可以便于認為是位置行向量，Q_k:＝(nz^k-1,nz^k)＝nz^k-1e₁,e₁:＝(1,z)。Q_k的整數坐標在不用等值以d為模的情況下被獲得。歐幾里得平面E₂中任意點(其第二坐標等于Q_k以d為模的值)的位置向量可以通過加入向量e₂:＝(0,d)的整數倍來得到。類似地，其第一坐標等于Q_k的坐標以d為模的點可以通過加入向量e₁'的整數倍來得到：