(57)【要約】  乱数発生装置１００は、複数の変数を記憶する記憶部１２０と、複数の変数それぞれを更新する複数の更新式の演算を実行し、複数の変数の更新値を記憶部１２０へ出力する演算部１３０と、複数の変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器１１０と、を備える。更新式は、更新式によって更新される対象変数の置換多項式と、複数の変数に含まれる対象変数以外の他の変数と、を含み、更新式によって対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。
2017150672.tif 000002
【特許請求の範囲】
【請求項１】
複数の変数を記憶する記憶部と、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部と、
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器と、
を備え、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
乱数発生装置。
【請求項２】
前記更新式は、前記対象変数の前記置換多項式と、前記他の変数と、の和を含む
請求項１記載の乱数発生装置。
【請求項３】
前記対象変数の前記置換多項式は、前記対象変数に乗じられる係数部分であって、多項式で表される前記係数部分を含み、前記他の変数は、前記係数部分に含まれる
請求項１又は２に記載の乱数発生装置。
【請求項４】
前記置換多項式は、一筆書き多項式である
請求項１〜３のいずれか１項に記載の乱数発生装置。
【請求項５】
演算部が、記憶部に記憶された複数の変数それぞれを更新する複数の更新式の演算を実行すること、
前記演算部が、複数の前記変数の更新値を記憶部へ出力すること、
生成器が、複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成すること、
を含み、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
乱数発生方法。
【請求項６】
コンピュータを、
複数の変数を記憶する記憶部、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部、及び
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器
として機能させるためのコンピュータプログラムであって、
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である
コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数発生装置等に関するものである。
【背景技術】
【０００２】
特許文献１は、置換多項式を用いた乱数発生装置を開示している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３８０６７６２号公報
【発明の概要】
【０００４】
一般に、乱数には、高い乱数性が望まれる。置換多項式の値を用いて生成される乱数の乱数性を高くするための一つのアプローチは、置換多項式の次数を大きくすることである。しかし、置換多項式の次数が大きくなると、演算器による演算時間の増大を招き易い。
【０００５】
このため、次数を大きくするのとは別のアプローチで、高い乱数性を容易に得ることが望まれる。
【０００６】
一の観点からみた本発明は、乱数発生装置である。乱数発生装置は、複数の変数それぞれを更新する複数の更新式の演算を実行する。更新式は、更新式によって更新される対象変数の置換多項式と、複数の変数に含まれる対象変数以外の他の変数と、を含む。更新式は、更対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。本発明によれば、一筆書き多項式と同様の長周期が得られ、高い乱数性が容易に得られる。
【０００７】
他の観点からみた本発明は、乱数を生成する方法である。他の観点からみた本発明は、コンピュータを乱数発生装置として機能させるためのコンピュータプログラムである。コンピュータプログラムは、コンピュータ読み取り可能な記録媒体に記憶される。
【図面の簡単な説明】
【０００８】
【図１】置換多項式の軌道を示す図である。
【図２】一筆書き多項式の軌道を示す図である。
【図３】乱数発生装置のブロック図である。
【発明を実施するための形態】
【０００９】
［１．用語］
【００１０】
［１．１  置換多項式］
置換多項式Ｆ（Ｘ）は、有限集合上でＸの置換を与える多項式である。置換多項式は、有限集合において全単射を与える。置換多項式による変数Ｘの値の変化を示す軌道は、必ず、周期軌道になる。すなわち、置換多項式による変数Ｘの値の変化は、周期性を持つ。
【００１１】
［１．２  ２冪剰余環］
２冪剰余環は、以下のように表される有限集合である。本明細書では、以下のように表される２冪剰余環を、「冪指数ｗの２冪剰余環」というものとする。ｗは、任意の非負整数である。
【数１】
2017150672.tif 000003
なお、計算途中で値が集合の範囲外に出たら、”ｍｏｄ  ２ｗ”をとる。ｍｏｄは、剰余演算子である。
【００１２】
［１．３  ２冪剰余環上置換多項式］
２冪剰余環上置換多項式は、２冪剰余環上で置換を与える置換多項式である。２冪剰余環上置換多項式は、整数係数多項式である。すなわち、２冪剰余環上置換多項式Ｆ（Ｘ）は、Ｆ（Ｘ）  ｍｏｄ  ２ｗが、冪指数ｗの２冪剰余環上で全単射を与える整数係数多項式であり、以下のようにも定義される。
【数２】
2017150672.tif 000004
【００１３】
例えば、冪指数３の２冪剰余環上における、置換多項式Ｆａ（Ｘ）＝２Ｘ２＋Ｘ＋１の軌道は、図１（ａ）に示すように、周期軌道になる。すなわち、Ｆａ（０）  ｍｏｄ  ２３＝１であり、Ｆａ（１）  ｍｏｄ  ２３＝４であり、Ｆａ（４）  ｍｏｄ  ２３＝５であり、Ｆａ（５）  ｍｏｄ  ２３＝０である。
【００１４】
また、置換多項式Ｆａ（Ｘ）＝２Ｘ２＋Ｘ＋１は、図１（ｂ）に示す別の周期軌道も持つ。すなわち、Ｆａ（２）  ｍｏｄ  ２３＝３であり、Ｆａ（３）  ｍｏｄ  ２３＝６であり、Ｆａ（６）  ｍｏｄ  ２３＝７であり、Ｆａ（７）  ｍｏｄ  ２３＝２である。
【００１５】
［１．４  一筆書き周期性と一筆書き多項式］
一筆書き周期性とは、多項式Ｆ（Ｘ）が成す１本の軌道（１周期の軌道）が、２冪剰余環のすべての要素をめぐることをいう。軌道が一筆書き周期性を持つ多項式を、一筆書き多項式という。一筆書き多項式は、以下のように定義される。
【数３】
2017150672.tif 000005
【００１６】
図２は、冪指数３の２冪剰余環＝｛０，１，２，３，４，５，６，７｝上における、一筆書き多項式Ｆｂ（Ｘ）＝４Ｘ２＋Ｘ＋１の軌道を示している。図２に示す軌道は、周期軌道であり、１周期の軌道が、｛０，１，２，３，４，５，６，７｝のすべての要素を１回ずつ通過している。したがって、Ｆｂ（Ｘ）による２冪剰余環上の軌道は、一筆書き周期性を持ち、Ｆｂ（Ｘ）は一筆書き多項式である。図１と図２との対比からも明らかなように、一筆書き周期性がある場合、軌道の周期は最大となり、周期長は２ｗとなる。長い周期は、乱数発生において有利である。
【００１７】
置換多項式Ｆ（Ｘ）が、一筆書き多項式である必要十分条件は、
【数４】
2017150672.tif 000006
がすべて成り立つことである。上記の必要十分条件は、
係数ａ０と１とは法２に関して合同であり、
係数ａ１と１とは法２に関して合同であり、
添え字が１以上であるすべての係数ａ１，ａ２，ａ３，・・・の和と１とは、法４に関して合同であり、
添え字が３以上の奇数であるすべての係数ａ３，ａ５，ａ７，・・・の和と２ａ２とは、法４に関して合同であることを示す。
【００１８】
一筆書き多項式は、長周期であるという観点では乱数の生成に有利であるが、時間発展（変数Ｘの時間的変化）が単純となり、十分な乱数性を得るのが困難な場合がある。したがって、単なる一筆書き多項式単体は、乱数の生成に不利な面も有する。
【００１９】
［２．実施形態の概要］
【００２０】
［第１項］
実施形態に係る乱数発生装置は、
複数の変数を記憶する記憶部と、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部と、
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器と、
を備える。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。
【００２１】
第１項の乱数発生装置によれば、乱数の生成に用いられる変数を更新する更新式は、更新式によって更新される対象変数以外の他の変数も含むので、対象変数の置換多項式の次数を大きくしなくても、乱数性を高くすることができる。しかも、更新式は一筆書き周期性を持つので、長い周期を得ることができる。
【００２２】
［第２項］
前記更新式は、前記対象変数の前記置換多項式と、前記他の変数と、の和を含むことができる。
【００２３】
［第３項］
前記対象変数の前記置換多項式は、前記対象変数に乗じられる係数部分であって、多項式で表される前記係数部分を含み、前記他の変数は、前記係数部分に含まれていてもよい。
【００２４】
［第４項］
前記置換多項式は、一筆書き多項式であるのが好ましい。
【００２５】
［第５項］
実施形態に係る方法は、
演算部が、記憶部に記憶された複数の変数それぞれを更新する複数の更新式の演算を実行すること、
前記演算部が、複数の前記変数の更新値を記憶部へ出力すること、
生成器が、複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成すること、
を含む。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。
【００２６】
［第６項］
実施形態に係るコンピュータプログラムは、
コンピュータを、
複数の変数を記憶する記憶部、
複数の前記変数それぞれを更新する複数の更新式の演算を実行し、複数の前記変数の更新値を前記記憶部へ出力する演算部、及び
複数の前記変数の少なくともいずれか一つの変数に基づいて、乱数を生成する生成器
として機能させるためのコンピュータプログラムである。
前記更新式は、
前記更新式によって更新される対象変数の置換多項式と、複数の前記変数に含まれる前記対象変数以外の他の変数と、を含み、
前記更新式によって前記対象変数を繰り返し更新したときの周期性が、一筆書き周期性である。
【００２７】
［３．実施形態の詳細］
【００２８】
［３．１  乱数発生装置の構成］
図３は、実施形態に係る乱数発生装置１００を示している。乱数発生装置１００は、例えば、乱数を発生させるための演算を実行する演算回路を備えたハードウェアによって構成されている。乱数発生装置１００は、乱数発生コンピュータプログラムがインストールされたコンピュータであってもよい。コンピュータは、乱数発生コンピュータプログラムを実行することによって、乱数発生装置１００として機能する。
【００２９】
乱数発生装置１００は、乱数を生成する生成器１１０を備えている。生成器１１０は、変数ｘから乱数を生成する。実施形態に係る生成器１１０は、ｎ個（ｎは２以上の整数）の変数ｘ１，・・・，ｘｎに基づいて、乱数を生成する。ここで、変数ｘ１，・・・，ｘｎは、それぞれ、ｗビットの符号なし変数である。ｗは、任意の非負整数であり、例えば６４である。以下では、変数ｘの時間発展を表すｘｔの表記を用いることもある。ｘｔは、時刻ｔにおける変数ｘの値を示す。
【００３０】
乱数発生装置１００は、ｎ個の変数を記憶する記憶部１２０と、ｎ個の変数を更新する演算を実行する演算部１３０と、を備える。記憶部１２０は、ｎ個の変数を記憶するためのｎ個の記憶領域１２０−１，・・・，１２０−ｎを有する。各記憶領域１２０−１，・・・，１２０−ｎの大きさは、ｗビットである。
【００３１】
演算部１３０は、ｎ個の記憶領域１２０−１，・・・，１２０−ｎに対応する、ｎ個の演算器１３０−１，・・・，１３０−ｎを有している。各演算器１３０−１，・・・，１３０−ｎは、対応する記憶領域１２０−１，・・・，１２０−ｎに記憶された変数ｘ１，・・・，ｘｎを更新するため更新式本体Ｇ１，・・・，Ｇｎの演算を実行する。更新式本体Ｇ１，・・・，Ｇｎは、後述する更新式から”ｍｏｄ  ２ｗ”を除いた部分をいう。
【００３２】
各演算器１３０−１，・・・，１３０−ｎが演算の対象とする変数ｘを、対象変数とよぶ。例えば、演算器１３０−１にとっての対象変数は、変数ｘ１であり、演算器１３０−ｎにとっての対象変数は、変数ｘｎである。
【００３３】
各演算器１３０−１，・・・，１３０−ｎは、対象変数の更新のため、記憶部１２０から対象変数を取得する。例えば、演算器１３０−１は、記憶領域１２０−１から変数ｘ１を対象変数として取得し、演算器１３０−ｎは、記憶領域１２０−ｎから変数ｘｎを対象変数として取得する。
【００３４】
各演算器１３０−１，・・・，１３０−ｎは、対象変数だけでなく、記憶部１２０から他の変数も取得する。他の変数は、複数の変数ｘ１，・・・，ｘｎに含まれる変数であって、対象変数以外の変数である。他の変数は、１つであってもよいし、複数であってもよい。各演算器１３０は、複数の変数ｘ１，・・・，ｘｎすべてを取得してもよい。例えば、演算器１３０−１は、記憶領域１２０−２から変数ｘ２などを他の変数として取得し、演算器１３０−ｎは、記憶領域１２０−１から変数ｘ１などを他の変数として取得する。
【００３５】
各演算器１３０−１，・・・，１３０−ｎが取得した他の変数は、対象変数とともに、対象変数の更新に用いられる。すなわち、更新式は、対象変数と他の変数とを含む式である。更新式の例については後述する。
【００３６】
各演算器１３０−１，・・・，１３０−ｎは、更新式本体Ｇ１，・・・，Ｇｎの演算結果Ｒ−１，・・・，Ｒ−ｎを出力する。演算結果Ｒ−１，・・・，Ｒ−ｎのビット数は、ｗビットを超えることがある。各演算結果Ｒ−１，・・・，Ｒ−ｎの下位ｗビットが、変数ｘ１ｔ，・・・，ｘｎｔの更新値ｘ１ｔ＋１，・・・，ｘｎｔ＋１となる。各演算結果Ｒ−１，・・・，Ｒ−ｎから、それらの下位ｗビットを取り出すことは、数学的には、各演算結果Ｒ−１，・・・，Ｒ−ｎに対して、”ｍｏｄ  ２ｗ”の演算を行うことと等価である。本実施形態では、剰余演算を行う必要がないため、演算を高速化できる。
【００３７】
更新値ｘ１ｔ＋１，・・・，ｘｎｔ＋１は、演算部１３０から記憶部１２０へ出力される。更新値ｘ１ｔ＋１，・・・，ｘｎｔ＋１は、記憶領域１２０−１，・・・，１２０−ｎに上書きされる。
【００３８】
本実施形態では、生成器１１０は、時刻ｔ＋１において演算部１３０から出力された１又は複数の変数ｘｔ＋１から、乱数発生に用いられる出力系列ｔ＋１を生成し、その出力系列ｔ＋１から時刻ｔ＋１における乱数ｔ＋１を生成する。生成器１１０の構成は、１又は複数の変数ｘから乱数を生成する所定の演算を行うものであれば、特に限定されない。生成器１１０が変数から乱数を生成する演算は、複数の変数ｘ全部又は一部を如何様に組み合わせた演算であってもよいし、複数の変数ｘのうちの１つの変数だけを用いた演算であってもよい。なお、生成器１１０は、変数ｘの更新値が記憶部１２０に上書きされてから、変数ｘを記憶部１２０から読み出して乱数を生成してもよい。
【００３９】
実施形態に係る生成器１１０は、排他的論理和演算部１１１を備える。排他的論理和演算部１１１は、ｎ個の変数ｘ１，・・・，ｘｎの排他的論理演算を行う。排他的論理和演算部１１１の出力の所定上位ビット（例えば、上位１６ビット）が、出力系列ｔ＋１となる。生成器１１０は、出力系列ｔ＋１を用いて乱数ｔ＋１を生成し、生成された乱数数ｔ＋１を出力する。なお、排他的論理和演算部１１１は、Ｎ個の変数ｘ１，・・・，ｘｎそれぞれの上位ビットに対する排他的論理和演算を行っても良い。また、生成器１１０は、出力系列を乱数として出力してもよい。
【００４０】
［３．２  更新式の第１例］
ｎ個の変数ｘ１，・・・，ｘｎそれぞれ更新するｎ個の更新式の第１例は、以下のとおりである。
【数５】
2017150672.tif 000007
【００４１】
各更新式の右辺は、”ｍｏｄ  ２ｗ”の部分と、”ｍｏｄ  ２ｗ”以外の部分である更新式本体と、を有する。例えば、変数ｘ１の更新式の更新式本体Ｇ１は、変数ｘ１の更新式のうち、”ｍｏｄ  ２ｗ”以外の部分である”Ｆ１（ｘ１（ｉ））＋ｃ１，１ｘ１（ｉ）＋ｃ１，２ｘ２（ｉ）＋ｃ１，３ｘ３（ｉ）＋・・・＋ｃ１，ｎｘｎ（ｉ）”の部分である。他の変数ｘ２，・・・，ｘｎについても同様である。
【００４２】
更新式本体は、対応する演算器によって演算される。例えば、更新式本体Ｇ１は、演算器１３０−１によって演算される。更新式本体Ｇ１は、対象変数ｘ１の置換多項式としての一筆書き多項式Ｆ１（ｘ１（ｉ））、と、付加多項式ｃ１，１ｘ１（ｉ）＋ｃ１，２ｘ２（ｉ）＋ｃ１，３ｘ３（ｉ）＋・・・＋ｃ１，ｎｘｎ（ｉ）と、の和として表される。付加多項式は、少なくとも一つの他の変数（対象変数ｘ１以外の変数）ｘ２，・・・ｘｎを含む。付加多項式は、対象変数ｘ１を含んでも良い。第１例において、付加多項式は、付加多項式に含まれる複数の変数ｘに関して、ｃｋ，ｌを係数とした線形結合となっている。なお、本明細書において、多項式は、単項式を含む。以上の更新式本体Ｇ１についての説明は、他の変数ｘ２，・・・，ｘｎについての更新式本体Ｇ２，・・・，Ｇｎにおいても同様である。
【００４３】
更新式の第１例では、各一筆書き多項式に付加多項式が付加されているが、各更新式全体における一筆書き周期性が維持されている。
【００４４】
更新式の第１例において、一筆書き周期性を持つための条件は、以下のとおりである。
・係数ｃｋ，ｌ（ｋ＝１，２，・・・，ｎ，ｌ＝１，２，・・・，ｎ）はすべて偶数（偶数は０を含む、以下同様）である。
・任意のｋに対して、ｃｋ，１，ｃｋ，２，・・・，ｃｋ，ｎのうち、４で割り切れないものの個数は偶数である。
【００４５】
なお、付加多項式中の”＋”、及び、付加多項式と置換多項式（一筆書き多項式）との和をとるための”＋”は、算術和演算である必要はなく、排他的論理和演算であってもよい。また、複数の”＋”に対応する演算として、算術和演算と排他的論理和演算とが混在してもよい。算術和演算と排他的論理和演算とが混在する場合には、両演算の優先順位を適宜決めればよい。
【００４６】
更新式の第１例は、以下の点で有用である。まず、各更新式は一筆書き周期性を持つため、各変数の周期は、２ｗという長周期になることが保証される。すなわち、以下が成り立つ。
【数６】
2017150672.tif 000008
なお、長周期性は、疑似乱数発生器やストリーム暗号において重要な性質である。
【００４７】
更新式の第１例の時間発展は、単なる一筆書き多項式単体の時間発展より複雑な挙動となるため有利である。更新式の第１例では、各更新式の次数は２に抑えられているが、次数を高くしなくても、時間発展の複雑な挙動が得られる。次数の増加は、演算負荷が大きい乗算の増加を招くが、更新式の第１例では、各更新式の次数を低く抑えられて有利である。
【００４８】
また、更新式の第１例は、一筆多項式に付加多項式が付加されているが、一筆書き多項式と同様に、実質的に除算を行う必要がない。つまり、剰余算はデジタルコンピュータ上では無視できるという一筆書き多項式の優れた点が維持されている。
【００４９】
ｎ個の更新式を並列に演算することで、すなわち、各演算器１３０−１，・・・，１３０−ｎが並列に演算することで、変数の数が増加しても演算時間の増加を抑えることができる。
【００５０】
係数ｃｋ，ｌの値として、２の冪乗のものを選択すると、更新式中では乗算として表現されているｃｋ，ｌｘｋ，ｌを、変数ｘｋ，ｌのビットシフト操作で実現できるため、より高速化が可能である。また、係数ｃｋ，ｌの値としては、上記の条件を満たす限り、様々な値を採用できる。したがって、乱数発生装置としての設計の自由度が高くなる。
【００５１】
［３．３  更新式の第１例の評価］
更新式の第１例の乱数性を評価するため、以下のｎ個の更新式を用いた。
【数７】
2017150672.tif 000009
【００５２】
評価は、図１の乱数発生装置における演算部１３０が上記のｎ個の更新式を演算するようにコンピュータを機能させるプログラムを、コンピュータに実行させて行った。乱数発生装置として機能させたコンピュータのプロセッサは、１．３ＧＨｚ  Ｉｎｔｅｌ  Ｃｏｒｅ  ｉ５である。なお、評価は、ｎ個の更新式の演算を並列化せずに行った。
【００５３】
評価において、生成部１１０は、演算部１３０が出力した変数ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６の排他的論理和をとり、その結果を、４８ビット右シフトさせた１６ビットの値（出力系列）を評価系列として生成する。すなわち、生成部１１０は、以下の演算を行う。
【数８】
2017150672.tif 000010
【００５４】
乱数性の評価は、以下を１セットとして４０セット行った。
１．ｘ１，ｘ２，ｘ３，ｘ４，ｘ５，ｘ６，ａ１，ａ２，ａ３，ａ４，ａ５，ａ６，ｂ１，ｂ２，ｂ３，ｂ４，ｂ５，ｂ６の値をランダムに決める。
２．「１．」で決めた値をセットした乱数発生装置を実行させ、生成された評価系列から１０９ビットの乱数を生成する。
３．得られた乱数１０９ビットの乱数を、１０６ビットの乱数１０００本とする。１０００本の乱数を、米国商務省標準技術局（ＮＩＳＴ）  ＳＰ  ８００−２２で定義される乱数検定にかける。
【００５５】
表１は、乱数検定結果を示している。
【表１】
2017150672.tif 000011
【００５６】
ＮＩＳＴ  ＳＰ  ８００−２２は、１８８項目のテストで構成されている。１８８項目すべてについて合格したのは、４０セット中２６セットであった。理想的な乱数の場合に、１８８項目すべてをクリアするセット数の理論値は、標準偏差の範囲で、４０セット中２１セットから２７セットである。また、すべての項目に合格しなかった１４セットについても、理想的な乱数が十分にとり得る成績である。よって、乱数性に関し良好な結果が得られていることがわかる。
【００５７】
また、評価では、３Ｇｂｐｓ以上の実行速度が得られており、実行速度の観点からも良好な結果が得られた。
【００５８】
［３．４  更新式の第２例］
Ｎ個の変数ｘ１，・・・，ｘＮそれぞれ更新するＮ個の更新式の第２例は、以下のとおりである。
【数９】
2017150672.tif 000012
【００５９】
なお、第２例中の”＋”も、算術和演算である必要はなく、排他的論理和演算であってもよい。また、複数の”＋”に対応する演算として、算術和演算と排他的論理和演算とが混在してもよい。算術和演算と排他的論理和演算とが混在する場合には、両演算の優先順位を適宜決めればよい。
【００６０】
更新式の第２例は、第１例を包含する形式で定義されている。つまり、全係数ｃi,j,k,ｌのうち、添え字ｊが０かつ添え字ｌが１（他の添え字ｉ，ｋは、０でもよいし０でなくてよい）である係数ｃi,0,k,１以外のものすべてを０にすると、
【数１０】
2017150672.tif 000013
となり、第１例に対応する。
【００６１】
第２例においても、各変数ｘ１，・・・，ｘＮの更新式は、一筆書き周期性を有する。第２例においても、各更新式の右辺は、”ｍｏｄ  ２ｗ”の部分と、”ｍｏｄ  ２ｗ”以外の部分である更新式本体と、を有する。第２例でも、更新式本体は、対象変数の置換多項式（一筆書き多項式）と、付加多項式としての和として表されるが、第２例では、付加多項式が含まれていなくても良い。第２例では、置換多項式の係数部分（対象変数に乗じられる部分）が、対象変数以外の他の変数を含む多項式で表される。
【００６２】
以下は、第２例の具体例を示している。
【数１１】
2017150672.tif 000014
【００６３】
例えば、変数ｘ１の更新式は、”ｍｏｄ２６４”以外の更新式本体Ｇ１を有している。更新式本体Ｇ１において、対象変数ｘ１のための一筆書き多項式に相当するのは、”２｛ｘ１（ｔ）｝２＋｛４ｘ３（ｔ）＋３｝ｘ１（ｔ）＋１”の部分であり、付加多項式に相当するのが、”４ｘ２（ｔ）”の部分である。更新式本体Ｇ１の付加多項式は、他の変数としてｘ２（ｔ）を有する。
【００６４】
更新式本体Ｇ１の一筆書き多項式においては、ｘ１（ｔ）の係数が、定数ではなく、他の変数ｘ３（ｔ）を含んでいる。したがって、一筆書き多項式の係数が時間的に変化し、更新式の時間発展が、第１例よりも複雑になる。他の変数ｘ２〜ｘ８の更新式についても同様である。
【００６５】
また、第２例は、第１例を包含しており、第１例と同様の有用性が得られる。さらに、第２例では、置換多項式（一筆書き多項式）の係数部分を他の変数によって変化させることができるため、係数部分が、時間的に値が変化しない定数を含んでいてもその値は小さくてよい。したがって、値が変化しない定数に大きなメモリを割り当てなくても良くなり、メモリ効率が向上する。
【００６６】
［３．５  更新式の第２例の評価］
更新式の第２例の乱数性の評価を、上記の具体例として示したｎ個の更新式を用いて行った。
【００６７】
評価の方法は、第１例の評価方法とほぼ同様である。第２例では、５２セットについて評価した。また、第２例では、各変数が６４ビットであり、各変数の上位３２ビットを出力系列生成に用いた。
【００６８】
第２例の場合、実行速度の最高値は、４９３６．８２４７８０Ｍｐｂｓとなり、暗号化速度に換算すると、２．１６ｃｙｃｌｅ／Ｂｙｔｅとなり、非常に高い速度が得られている。
【００６９】
第２例の場合、ＮＩＳＴ  ＳＰ  ８００−２２で定義される乱数検定の結果は、５２セット中、４０セットが、１８８項目すべてについて合格した。第２例においても良好な乱数性が確認された。
【００７０】
本発明は、上記実施形態に限定されるものではなく、様々な変形が可能である。
【符号の説明】
【００７１】
１００  乱数発生装置
１１０  生成器
１２０  記憶部
１３０  演算部
【図１】
2017150672.tif 000015
【図２】
2017150672.tif 000016
【図３】
2017150672.tif 000017
【国際調査報告】
2017150672.tif 000018
2017150672.tif 000019
2017150672.tif 000020