TOP > 国内特許検索 > 乱数発生装置、乱数発生方法及びコンピュータプログラム > 明細書

明細書 :乱数発生装置、乱数発生方法及びコンピュータプログラム

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成30年12月27日(2018.12.27)
発明の名称または考案の名称 乱数発生装置、乱数発生方法及びコンピュータプログラム
国際特許分類 G06F   7/58        (2006.01)
G09C   1/00        (2006.01)
FI G06F 7/58 620
G09C 1/00 650B
国際予備審査の請求 未請求
全頁数 19
出願番号 特願2018-503400 (P2018-503400)
国際出願番号 PCT/JP2017/008294
国際公開番号 WO2017/150672
国際出願日 平成29年3月2日(2017.3.2)
国際公開日 平成29年9月8日(2017.9.8)
優先権出願番号 2016041564
優先日 平成28年3月3日(2016.3.3)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , ST , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DJ , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JP , KE , KG , KH , KN , KP , KR , KW , KZ , LA , LC , LK , LR , LS , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT , TZ
発明者または考案者 【氏名】岩▲崎▼ 淳
【氏名】梅野 健
出願人 【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
個別代理人の代理人 【識別番号】110000280、【氏名又は名称】特許業務法人サンクレスト国際特許事務所
審査請求 未請求
テーマコード 5J104
Fターム 5J104FA04
要約 乱数発生装置100は、複数の変数を記憶する記憶部120と、複数の変数それぞれを更新する複数の更新式の演算を実行し、複数の変数の更新値を記憶部120へ出力する演算部130と、複数の変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器110と、を備える。更新式は、更新式によって更新される対象変数の置換多項式と、複数の変数に含まれる対象変数以外の他の変数と、を含み、更新式によって対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。
特許請求の範囲 【請求項1】
複数の変数を記憶する記憶部と、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部と、
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器と、
を備え、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
乱数発生装置。
【請求項2】
前記更新式は、前記対象変数の前記置換多項式と、前記他の変数と、の和を含む
請求項1記載の乱数発生装置。
【請求項3】
前記対象変数の前記置換多項式は、前記対象変数に乗じられる係数部分であって、多項式で表される前記係数部分を含み、前記他の変数は、前記係数部分に含まれる
請求項1又は2に記載の乱数発生装置。
【請求項4】
前記置換多項式は、一筆書き多項式である
請求項1~3のいずれか1項に記載の乱数発生装置。
【請求項5】
演算部が、記憶部に記憶された複数の変数それぞれを更新する複数の更新式の演算を実行すること、
前記演算部が、複数の前記変数の更新値を記憶部へ出力すること、
生成器が、複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成すること、
を含み、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
乱数発生方法。
【請求項6】
コンピュータを、
複数の変数を記憶する記憶部、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部、及び
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器
として機能させるためのコンピュータプログラムであって、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
コンピュータプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、乱数発生装置等に関するものである。
【背景技術】
【0002】
特許文献1は、置換多項式を用いた乱数発生装置を開示している。
【先行技術文献】
【0003】

【特許文献1】特許第3806762号公報
【発明の概要】
【0004】
一般に、乱数には、高い乱数性が望まれる。置換多項式の値を用いて生成される乱数の乱数性を高くするための一つのアプローチは、置換多項式の次数を大きくすることである。しかし、置換多項式の次数が大きくなると、演算器による演算時間の増大を招き易い。
【0005】
このため、次数を大きくするのとは別のアプローチで、高い乱数性を容易に得ることが望まれる。
【0006】
一の観点からみた本発明は、乱数発生装置である。乱数発生装置は、複数の変数それぞれを更新する複数の更新式の演算を実行する。更新式は、更新式によって更新される対象変数の置換多項式と、複数の変数に含まれる対象変数以外の他の変数と、を含む。更新式は、更対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。本発明によれば、一筆書き多項式と同様の長周期が得られ、高い乱数性が容易に得られる。
【0007】
他の観点からみた本発明は、乱数を生成する方法である。他の観点からみた本発明は、コンピュータを乱数発生装置として機能させるためのコンピュータプログラムである。コンピュータプログラムは、コンピュータ読み取り可能な記録媒体に記憶される。
【図面の簡単な説明】
【0008】
【図1】置換多項式の軌道を示す図である。
【図2】一筆書き多項式の軌道を示す図である。
【図3】乱数発生装置のブロック図である。
【発明を実施するための形態】
【0009】
[1.用語]

【0010】
[1.1 置換多項式]
置換多項式F(X)は、有限集合上でXの置換を与える多項式である。置換多項式は、有限集合において全単射を与える。置換多項式による変数Xの値の変化を示す軌道は、必ず、周期軌道になる。すなわち、置換多項式による変数Xの値の変化は、周期性を持つ。

【0011】
[1.2 2冪剰余環]
2冪剰余環は、以下のように表される有限集合である。本明細書では、以下のように表される2冪剰余環を、「冪指数wの2冪剰余環」というものとする。wは、任意の非負整数である。
【数1】
JP2017150672A1_000003t.gif
なお、計算途中で値が集合の範囲外に出たら、”mod 2”をとる。modは、剰余演算子である。

【0012】
[1.3 2冪剰余環上置換多項式]
2冪剰余環上置換多項式は、2冪剰余環上で置換を与える置換多項式である。2冪剰余環上置換多項式は、整数係数多項式である。すなわち、2冪剰余環上置換多項式F(X)は、F(X) mod 2が、冪指数wの2冪剰余環上で全単射を与える整数係数多項式であり、以下のようにも定義される。
【数2】
JP2017150672A1_000004t.gif

【0013】
例えば、冪指数3の2冪剰余環上における、置換多項式F(X)=2X+X+1の軌道は、図1(a)に示すように、周期軌道になる。すなわち、F(0) mod 2=1であり、F(1) mod 2=4であり、F(4) mod 2=5であり、F(5) mod 2=0である。

【0014】
また、置換多項式F(X)=2X+X+1は、図1(b)に示す別の周期軌道も持つ。すなわち、F(2) mod 2=3であり、F(3) mod 2=6であり、F(6) mod 2=7であり、F(7) mod 2=2である。

【0015】
[1.4 一筆書き周期性と一筆書き多項式]
一筆書き周期性とは、多項式F(X)が成す1本の軌道(1周期の軌道)が、2冪剰余環のすべての要素をめぐることをいう。軌道が一筆書き周期性を持つ多項式を、一筆書き多項式という。一筆書き多項式は、以下のように定義される。
【数3】
JP2017150672A1_000005t.gif

【0016】
図2は、冪指数3の2冪剰余環={0,1,2,3,4,5,6,7}上における、一筆書き多項式F(X)=4X+X+1の軌道を示している。図2に示す軌道は、周期軌道であり、1周期の軌道が、{0,1,2,3,4,5,6,7}のすべての要素を1回ずつ通過している。したがって、F(X)による2冪剰余環上の軌道は、一筆書き周期性を持ち、F(X)は一筆書き多項式である。図1と図2との対比からも明らかなように、一筆書き周期性がある場合、軌道の周期は最大となり、周期長は2となる。長い周期は、乱数発生において有利である。

【0017】
置換多項式F(X)が、一筆書き多項式である必要十分条件は、
【数4】
JP2017150672A1_000006t.gif
がすべて成り立つことである。上記の必要十分条件は、
係数aと1とは法2に関して合同であり、
係数aと1とは法2に関して合同であり、
添え字が1以上であるすべての係数a,a,a,・・・の和と1とは、法4に関して合同であり、
添え字が3以上の奇数であるすべての係数a,a,a,・・・の和と2aとは、法4に関して合同であることを示す。

【0018】
一筆書き多項式は、長周期であるという観点では乱数の生成に有利であるが、時間発展(変数Xの時間的変化)が単純となり、十分な乱数性を得るのが困難な場合がある。したがって、単なる一筆書き多項式単体は、乱数の生成に不利な面も有する。

【0019】
[2.実施形態の概要]

【0020】
[第1項]
実施形態に係る乱数発生装置は、
複数の変数を記憶する記憶部と、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部と、
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器と、
を備える。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。

【0021】
第1項の乱数発生装置によれば、乱数の生成に用いられる変数を更新する更新式は、更新式によって更新される対象変数以外の他の変数も含むので、対象変数の置換多項式の次数を大きくしなくても、乱数性を高くすることができる。しかも、更新式は一筆書き周期性を持つので、長い周期を得ることができる。

【0022】
[第2項]
前記更新式は、前記対象変数の前記置換多項式と、前記他の変数と、の和を含むことができる。

【0023】
[第3項]
前記対象変数の前記置換多項式は、前記対象変数に乗じられる係数部分であって、多項式で表される前記係数部分を含み、前記他の変数は、前記係数部分に含まれていてもよい。

【0024】
[第4項]
前記置換多項式は、一筆書き多項式であるのが好ましい。

【0025】
[第5項]
実施形態に係る方法は、
演算部が、記憶部に記憶された複数の変数それぞれを更新する複数の更新式の演算を実行すること、
前記演算部が、複数の前記変数の更新値を記憶部へ出力すること、
生成器が、複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成すること、
を含む。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。

【0026】
[第6項]
実施形態に係るコンピュータプログラムは、
コンピュータを、
複数の変数を記憶する記憶部、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部、及び
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器
として機能させるためのコンピュータプログラムである。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。

【0027】
[3.実施形態の詳細]

【0028】
[3.1 乱数発生装置の構成]
図3は、実施形態に係る乱数発生装置100を示している。乱数発生装置100は、例えば、乱数を発生させるための演算を実行する演算回路を備えたハードウェアによって構成されている。乱数発生装置100は、乱数発生コンピュータプログラムがインストールされたコンピュータであってもよい。コンピュータは、乱数発生コンピュータプログラムを実行することによって、乱数発生装置100として機能する。

【0029】
乱数発生装置100は、乱数を生成する生成器110を備えている。生成器110は、変数xから乱数を生成する。実施形態に係る生成器110は、n個(nは2以上の整数)の変数x,・・・,xに基づいて、乱数を生成する。ここで、変数x,・・・,xは、それぞれ、wビットの符号なし変数である。wは、任意の非負整数であり、例えば64である。以下では、変数xの時間発展を表すxの表記を用いることもある。xは、時刻tにおける変数xの値を示す。

【0030】
乱数発生装置100は、n個の変数を記憶する記憶部120と、n個の変数を更新する演算を実行する演算部130と、を備える。記憶部120は、n個の変数を記憶するためのn個の記憶領域120-1,・・・,120-nを有する。各記憶領域120-1,・・・,120-nの大きさは、wビットである。

【0031】
演算部130は、n個の記憶領域120-1,・・・,120-nに対応する、n個の演算器130-1,・・・,130-nを有している。各演算器130-1,・・・,130-nは、対応する記憶領域120-1,・・・,120-nに記憶された変数x,・・・,xを更新するため更新式本体G,・・・,Gの演算を実行する。更新式本体G,・・・,Gは、後述する更新式から”mod 2”を除いた部分をいう。

【0032】
各演算器130-1,・・・,130-nが演算の対象とする変数xを、対象変数とよぶ。例えば、演算器130-1にとっての対象変数は、変数xであり、演算器130-nにとっての対象変数は、変数xである。

【0033】
各演算器130-1,・・・,130-nは、対象変数の更新のため、記憶部120から対象変数を取得する。例えば、演算器130-1は、記憶領域120-1から変数xを対象変数として取得し、演算器130-nは、記憶領域120-nから変数xを対象変数として取得する。

【0034】
各演算器130-1,・・・,130-nは、対象変数だけでなく、記憶部120から他の変数も取得する。他の変数は、複数の変数x,・・・,xに含まれる変数であって、対象変数以外の変数である。他の変数は、1つであってもよいし、複数であってもよい。各演算器130は、複数の変数x,・・・,xすべてを取得してもよい。例えば、演算器130-1は、記憶領域120-2から変数xなどを他の変数として取得し、演算器130-nは、記憶領域120-1から変数xなどを他の変数として取得する。

【0035】
各演算器130-1,・・・,130-nが取得した他の変数は、対象変数とともに、対象変数の更新に用いられる。すなわち、更新式は、対象変数と他の変数とを含む式である。更新式の例については後述する。

【0036】
各演算器130-1,・・・,130-nは、更新式本体G,・・・,Gの演算結果R-1,・・・,R-nを出力する。演算結果R-1,・・・,R-nのビット数は、wビットを超えることがある。各演算結果R-1,・・・,R-nの下位wビットが、変数x,・・・,xの更新値xt+1,・・・,xt+1となる。各演算結果R-1,・・・,R-nから、それらの下位wビットを取り出すことは、数学的には、各演算結果R-1,・・・,R-nに対して、”mod 2”の演算を行うことと等価である。本実施形態では、剰余演算を行う必要がないため、演算を高速化できる。

【0037】
更新値xt+1,・・・,xt+1は、演算部130から記憶部120へ出力される。更新値xt+1,・・・,xt+1は、記憶領域120-1,・・・,120-nに上書きされる。

【0038】
本実施形態では、生成器110は、時刻t+1において演算部130から出力された1又は複数の変数xt+1から、乱数発生に用いられる出力系列t+1を生成し、その出力系列t+1から時刻t+1における乱数t+1を生成する。生成器110の構成は、1又は複数の変数xから乱数を生成する所定の演算を行うものであれば、特に限定されない。生成器110が変数から乱数を生成する演算は、複数の変数x全部又は一部を如何様に組み合わせた演算であってもよいし、複数の変数xのうちの1つの変数だけを用いた演算であってもよい。なお、生成器110は、変数xの更新値が記憶部120に上書きされてから、変数xを記憶部120から読み出して乱数を生成してもよい。

【0039】
実施形態に係る生成器110は、排他的論理和演算部111を備える。排他的論理和演算部111は、n個の変数x,・・・,xの排他的論理演算を行う。排他的論理和演算部111の出力の所定上位ビット(例えば、上位16ビット)が、出力系列t+1となる。生成器110は、出力系列t+1を用いて乱数t+1を生成し、生成された乱数数t+1を出力する。なお、排他的論理和演算部111は、N個の変数x,・・・,xそれぞれの上位ビットに対する排他的論理和演算を行っても良い。また、生成器110は、出力系列を乱数として出力してもよい。

【0040】
[3.2 更新式の第1例]
n個の変数x,・・・,xそれぞれ更新するn個の更新式の第1例は、以下のとおりである。
【数5】
JP2017150672A1_000007t.gif

【0041】
各更新式の右辺は、”mod 2”の部分と、”mod 2”以外の部分である更新式本体と、を有する。例えば、変数xの更新式の更新式本体Gは、変数xの更新式のうち、”mod 2”以外の部分である”F(x(i))+c1,1(i)+c1,2(i)+c1,3(i)+・・・+c1,n(i)”の部分である。他の変数x,・・・,xについても同様である。

【0042】
更新式本体は、対応する演算器によって演算される。例えば、更新式本体Gは、演算器130-1によって演算される。更新式本体Gは、対象変数xの置換多項式としての一筆書き多項式F(x(i))、と、付加多項式c1,1(i)+c1,2(i)+c1,3(i)+・・・+c1,n(i)と、の和として表される。付加多項式は、少なくとも一つの他の変数(対象変数x以外の変数)x,・・・xを含む。付加多項式は、対象変数xを含んでも良い。第1例において、付加多項式は、付加多項式に含まれる複数の変数xに関して、ck,lを係数とした線形結合となっている。なお、本明細書において、多項式は、単項式を含む。以上の更新式本体Gについての説明は、他の変数x,・・・,xについての更新式本体G,・・・,Gにおいても同様である。

【0043】
更新式の第1例では、各一筆書き多項式に付加多項式が付加されているが、各更新式全体における一筆書き周期性が維持されている。

【0044】
更新式の第1例において、一筆書き周期性を持つための条件は、以下のとおりである。
・係数ck,l(k=1,2,・・・,n,l=1,2,・・・,n)はすべて偶数(偶数は0を含む、以下同様)である。
・任意のkに対して、ck,1,ck,2,・・・,ck,nのうち、4で割り切れないものの個数は偶数である。

【0045】
なお、付加多項式中の”+”、及び、付加多項式と置換多項式(一筆書き多項式)との和をとるための”+”は、算術和演算である必要はなく、排他的論理和演算であってもよい。また、複数の”+”に対応する演算として、算術和演算と排他的論理和演算とが混在してもよい。算術和演算と排他的論理和演算とが混在する場合には、両演算の優先順位を適宜決めればよい。

【0046】
更新式の第1例は、以下の点で有用である。まず、各更新式は一筆書き周期性を持つため、各変数の周期は、2という長周期になることが保証される。すなわち、以下が成り立つ。
【数6】
JP2017150672A1_000008t.gif
なお、長周期性は、疑似乱数発生器やストリーム暗号において重要な性質である。

【0047】
更新式の第1例の時間発展は、単なる一筆書き多項式単体の時間発展より複雑な挙動となるため有利である。更新式の第1例では、各更新式の次数は2に抑えられているが、次数を高くしなくても、時間発展の複雑な挙動が得られる。次数の増加は、演算負荷が大きい乗算の増加を招くが、更新式の第1例では、各更新式の次数を低く抑えられて有利である。

【0048】
また、更新式の第1例は、一筆多項式に付加多項式が付加されているが、一筆書き多項式と同様に、実質的に除算を行う必要がない。つまり、剰余算はデジタルコンピュータ上では無視できるという一筆書き多項式の優れた点が維持されている。

【0049】
n個の更新式を並列に演算することで、すなわち、各演算器130-1,・・・,130-nが並列に演算することで、変数の数が増加しても演算時間の増加を抑えることができる。

【0050】
係数ck,lの値として、2の冪乗のものを選択すると、更新式中では乗算として表現されているck,lk,lを、変数xk,lのビットシフト操作で実現できるため、より高速化が可能である。また、係数ck,lの値としては、上記の条件を満たす限り、様々な値を採用できる。したがって、乱数発生装置としての設計の自由度が高くなる。

【0051】
[3.3 更新式の第1例の評価]
更新式の第1例の乱数性を評価するため、以下のn個の更新式を用いた。
【数7】
JP2017150672A1_000009t.gif

【0052】
評価は、図1の乱数発生装置における演算部130が上記のn個の更新式を演算するようにコンピュータを機能させるプログラムを、コンピュータに実行させて行った。乱数発生装置として機能させたコンピュータのプロセッサは、1.3GHz Intel Core i5である。なお、評価は、n個の更新式の演算を並列化せずに行った。

【0053】
評価において、生成部110は、演算部130が出力した変数x,x,x,x,x,xの排他的論理和をとり、その結果を、48ビット右シフトさせた16ビットの値(出力系列)を評価系列として生成する。すなわち、生成部110は、以下の演算を行う。
【数8】
JP2017150672A1_000010t.gif

【0054】
乱数性の評価は、以下を1セットとして40セット行った。
1.x,x,x,x,x,x,a,a,a,a,a,a,b,b,b,b,b,bの値をランダムに決める。
2.「1.」で決めた値をセットした乱数発生装置を実行させ、生成された評価系列から10ビットの乱数を生成する。
3.得られた乱数10ビットの乱数を、10ビットの乱数1000本とする。1000本の乱数を、米国商務省標準技術局(NIST) SP 800-22で定義される乱数検定にかける。

【0055】
表1は、乱数検定結果を示している。
【表1】
JP2017150672A1_000011t.gif

【0056】
NIST SP 800-22は、188項目のテストで構成されている。188項目すべてについて合格したのは、40セット中26セットであった。理想的な乱数の場合に、188項目すべてをクリアするセット数の理論値は、標準偏差の範囲で、40セット中21セットから27セットである。また、すべての項目に合格しなかった14セットについても、理想的な乱数が十分にとり得る成績である。よって、乱数性に関し良好な結果が得られていることがわかる。

【0057】
また、評価では、3Gbps以上の実行速度が得られており、実行速度の観点からも良好な結果が得られた。

【0058】
[3.4 更新式の第2例]
N個の変数x,・・・,xそれぞれ更新するN個の更新式の第2例は、以下のとおりである。
【数9】
JP2017150672A1_000012t.gif

【0059】
なお、第2例中の”+”も、算術和演算である必要はなく、排他的論理和演算であってもよい。また、複数の”+”に対応する演算として、算術和演算と排他的論理和演算とが混在してもよい。算術和演算と排他的論理和演算とが混在する場合には、両演算の優先順位を適宜決めればよい。

【0060】
更新式の第2例は、第1例を包含する形式で定義されている。つまり、全係数ci,j,k,lのうち、添え字jが0かつ添え字lが1(他の添え字i,kは、0でもよいし0でなくてよい)である係数ci,0,k,1以外のものすべてを0にすると、
【数10】
JP2017150672A1_000013t.gif
となり、第1例に対応する。

【0061】
第2例においても、各変数x,・・・,xの更新式は、一筆書き周期性を有する。第2例においても、各更新式の右辺は、”mod 2”の部分と、”mod 2”以外の部分である更新式本体と、を有する。第2例でも、更新式本体は、対象変数の置換多項式(一筆書き多項式)と、付加多項式としての和として表されるが、第2例では、付加多項式が含まれていなくても良い。第2例では、置換多項式の係数部分(対象変数に乗じられる部分)が、対象変数以外の他の変数を含む多項式で表される。

【0062】
以下は、第2例の具体例を示している。
【数11】
JP2017150672A1_000014t.gif

【0063】
例えば、変数xの更新式は、”mod264”以外の更新式本体Gを有している。更新式本体Gにおいて、対象変数xのための一筆書き多項式に相当するのは、”2{x(t)+{4x(t)+3}x(t)+1”の部分であり、付加多項式に相当するのが、”4x(t)”の部分である。更新式本体Gの付加多項式は、他の変数としてx(t)を有する。

【0064】
更新式本体Gの一筆書き多項式においては、x(t)の係数が、定数ではなく、他の変数x(t)を含んでいる。したがって、一筆書き多項式の係数が時間的に変化し、更新式の時間発展が、第1例よりも複雑になる。他の変数x~xの更新式についても同様である。

【0065】
また、第2例は、第1例を包含しており、第1例と同様の有用性が得られる。さらに、第2例では、置換多項式(一筆書き多項式)の係数部分を他の変数によって変化させることができるため、係数部分が、時間的に値が変化しない定数を含んでいてもその値は小さくてよい。したがって、値が変化しない定数に大きなメモリを割り当てなくても良くなり、メモリ効率が向上する。

【0066】
[3.5 更新式の第2例の評価]
更新式の第2例の乱数性の評価を、上記の具体例として示したn個の更新式を用いて行った。

【0067】
評価の方法は、第1例の評価方法とほぼ同様である。第2例では、52セットについて評価した。また、第2例では、各変数が64ビットであり、各変数の上位32ビットを出力系列生成に用いた。

【0068】
第2例の場合、実行速度の最高値は、4936.824780Mpbsとなり、暗号化速度に換算すると、2.16cycle/Byteとなり、非常に高い速度が得られている。

【0069】
第2例の場合、NIST SP 800-22で定義される乱数検定の結果は、52セット中、40セットが、188項目すべてについて合格した。第2例においても良好な乱数性が確認された。

【0070】
本発明は、上記実施形態に限定されるものではなく、様々な変形が可能である。
【符号の説明】
【0071】
100 乱数発生装置
110 生成器
120 記憶部
130 演算部
図面
【図1】
0
【図2】
1
【図3】
2