擬似乱数生成装置及び擬似乱数生成用プログラム
【課題】周期延長を行い、最大周期長と一様性を確保する。
【解決手段】初期値設定手段１１により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段１２と、前記全単射写像準備手段１２により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段１３と、前記写像値計算手段１３により得られた写像値からビット列を抽出するビット列抽出手段１５と、前記ビット列抽出手段１４によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段１５とを具備する。
【解決手段】初期値設定手段１１により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段１２と、前記全単射写像準備手段１２により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段１３と、前記写像値計算手段１３により得られた写像値からビット列を抽出するビット列抽出手段１５と、前記ビット列抽出手段１４によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段１５とを具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、全単射写像を用いて擬似乱数を生成する擬似乱数生成装置及び擬似乱数生成用プログラムに関するものである。
【背景技術】
【０００２】
従来の擬似乱数生成装置においては、有限演算実装における非線形（カオス）写像を用いた擬似乱数生成法を採用したものが知られている（特許文献１参照）。この従来例にあっては、全単射を保証しない写像を用いていた。また、全単射を保証するものでも、短周期帯に落ち入ることで長い周期が得られなくなることから、周期を監視する機構が必要であった。
【０００３】
また、最大周期と一様性を保証する擬似乱数生成器として線形合同法や、Ｍ系列乱数(GFSR:Generalized Feedbacked Shift Register)が知られている。しかしながら、周期が限定されており生成パターンも一方向的に決定されたものを出力する方式であり、生成パターンが限られていた。また、これらの生成法では、一素周期の中で各値が一度だけ出現する。従って、ある値を観測したらその後、その値はその周期中で出現しない。
【０００４】
上記GFSRの改良としてTwisted GFSR、メルセンヌツイスターが存在するが、周期を延ばすパラメータ帯が固定値であり、それを探索する必要があるという労力が存在する。
【０００５】
更に、写像変更ないしは写像変換を用いた擬似乱数生成装置としては、二次元キャットマップのような写像を用いるものが知られている（特許文献２参照）。しかしながら、この二次元キャットマップは暗号化や復号に不適切と言われており、また、周期延長が可能なものでもない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１５２７０６号公報
【特許文献２】特開２００７−２６４１４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は上記のような擬似乱数生成における現状に鑑みてなされたもので、その目的は、周期延長を行い、最大周期長と一様性を確保し、かつ大量に乱数を生成することのできる、全単射写像を用いた擬似乱数生成装置及び擬似乱数生成用プログラムを提供することである。
【課題を解決するための手段】
【０００８】
本発明に係る擬似乱数生成装置は、擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段と、この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段と、前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段と、前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段と、前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段とを具備することを特徴とする。
【０００９】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、写像関数として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを用いることを特徴とする。
【００１０】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備することを特徴とする。
【００１１】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備することを特徴とする。
【００１２】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備することを特徴とする。
【００１３】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段、この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段、前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段、前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段、前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段として機能させることを特徴とする。
【００１４】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを写像関数として用いるように機能させることを特徴とする。
【００１５】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するように機能させることを特徴とする。
【００１６】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備するように機能させることを特徴とする。
【００１７】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備するように機能させることを特徴とする
【発明の効果】
【００１８】
本発明によれば、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備し、準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返すことにより写像値計算を行うので、周期延長用全単射写像によって周期延長が行われ、最大周期長と一様性を確保することができる。
【００１９】
本発明では、全単射写像であれば制限なく利用可能であり、写像の順番の入れ替えや再利用もできるため、生成パターンを豊富に提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の擬似乱数生成装置における全単射族による写像値の周期延長手法について説明するための写像値巡回状態を示す図。
【図２】本発明の擬似乱数生成装置における全単射族による写像値の周期延長全単射写像の生成について説明するための図。
【図３】本発明に係る擬似乱数生成装置の構成を示すブロック図。
【図４】本発明に係る擬似乱数生成装置を構成するコンピュータシステムのブロック図。
【図５】本発明に係る擬似乱数生成装置の第１の実施例の動作を説明するためのフローチャート。
【図６】本発明に係る擬似乱数生成装置の第２の実施例の動作を説明するためのフローチャート。
【図７】本発明の擬似乱数生成装置における全単射族による写像として、線形合同法を用いた各初期値の列を示す図。
【図８】本発明の擬似乱数生成装置における全単射族による写像として、M系列(GFSR)を用いた各初期値の列を示す図。
【図９】本発明の擬似乱数生成装置における全単射族による写像として、M系列(TGFSR)を用いた各初期値の列を示す図。
【図１０】本発明の擬似乱数生成装置における全単射族による写像として用いる、変形テント写像のマップを示す図。
【図１１】本発明の擬似乱数生成装置における全単射族による写像として、変形テント写像を用いた写像遷移を示す図。
【発明を実施するための形態】
【００２１】
以下添付図面を参照して、本発明に係る擬似乱数生成装置及び擬似乱数生成用プログラムを説明する。原理は次の通りである。例として次の（式１）に示す有限集合ｘ（集合の数が４）の全単射族の写像“ f0、f1、f2”を３つ用意した場合の、図１の如き写像の列を例とする。
【００２２】
【数１】
【００２３】
これらの漸化式は次の（式２）により表わされる。
【００２４】
【数２】
【００２５】
上記において、選択する写像関数ｆｙｉの順番ｙｉに制限はないが、図１の例では
ｙｉ＝（ｉ＋１）ｍｏｄ３ （ｉ＝０，１，…）を用いている。
【００２６】
上記写像によって繰り返し写像を行って得られる数列は、初期値ｘ０＝０のとき、
0, 2, 1, 3, 1, 2, 2, 0, 3
を繰り返す周期長９の周期帯（初期値ｘ０＝２、ｘ０＝３によっても写像結果である数列のパターンが同じ）が得られる。また、初期値ｘ０＝１のときには、
1, 3, 0
を繰り返す周期長３の周期帯が得られる。このように例示の写像をそのまま用いた場合には、生成パターンが２つの周期帯に分かれて存在する。
【００２７】
このように全単射写像を単に用いただけでは周期帯がいくつかに分かれ、短周期が存在し、各値の出現頻度が一様にならない。係る系として、有限演算下での非線形写像を用いて得られる乱数列があり、長周期性と一様性の保証された擬似乱数列を得ようとした場合に課題となる。
【００２８】
ここで、“f2”を理想的な写像“Q”に変更することによって、３種類の写像を用いる場合の最大周期長１２を実現し、かつ各値の出現頻度が一様に３となる数列を得ることを可能にする。即ち、長周期性と一様性の保証された擬似乱数列を得るための理想的な全単射写像“Ｑ”を次のようにして作成する。
【００２９】
まず、図１にて用いた全単射写像“f0、f1”の逆写像“f0-1、f1-1 ”を生成する。また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ”とエルゴード的な全単射写像“α“を用いて、図２に示すように写像“Ｑ”を作る計算（Ｑ＝αf0-1f1-1）を実行する。
【００３０】
このように、図１にて用いた全単射写像“f2”を“Q”に変更することで、初期値ｘ０＝１のとき
0, 2, 1, 1, 3, 0, 2, 0, 3, 3, 1, 2
を繰り返す最大周期長１２の数列が得られ、各値の出現頻度が一様な値（3回）である数列を得ることが可能となる。
【００３１】
即ち、図２で用いた全単射写像の数が“３”であり、集合の数が“４”であり、素周期が３種類の全単射写像を用いるとき、その最大周期長は、３×４＝１２から求められる。そして、上記の通り、各値の出現頻度が一様に３回となっている擬似乱数列が得られていることが分かる。
【００３２】
上記において、選択する写像関数“ｆｙｉ”（ｙｉ＝ｉｍｏｄＫ:iは写像回数、Ｋは用意した全単射写像の数）は全単射であれば何でもよく、写像関数“ｆｙｉ”は１回の写像の度に変更する。
【００３３】
図２で用いた周期延長計算に利用する写像“α“はいくつかの周期帯に分かれて短周期に落ちない、最大周期を持つ全単射写像であればよい（本発明において、周期延長計算に利用する写像“α“を「エルゴード的な全単射写像」と呼ぶ）。例えば、写像の集合要素を単純にシフト（ｆ（ｘ）＝（ｘ＋１）ｍｏｄＮ ただし、Ｎは集合の数）したものとすることができる。選択した全単射写像の逆写像とエルゴード的な全単射写像とを用い、周期を延長する写像“Ｑ”を計算して作ることが重要である。これによって、最大周期長と一様性を持つ乱数列を生成可能になることが分かった。
【００３４】
選択し得る全単射写像は、最大周期をもつ擬似乱数生成方法で知られる線形合同法、M系列(GSFR)、GSFRの周期を延長させた改良版（Twisted GFSR、メルセンヌツイスター等）のような完成されたものを用いることもできるが、短周期帯を含んでいても全単射写像であれば特に制限はない。これらの系では乱数列パターンは決定されているが、全単射写像“ｆｙｉ”の順番の入れ替えや写像“Q”を変更することで乱数列のパターンを、より豊富に作ることが可能である。
【００３５】
本発明の実施例に係る擬似乱数生成装置は、図３に示すように構成される。即ち、初期値設定手段１１、全単射写像準備手段１２、写像値計算手段１３、ビット列抽出手段１４及び擬似乱数出力手段１５を備える。初期値設定手段１１は、擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定するものである。初期値に関しては、コンピュータシステムのキーボードなどの入力手段から入力することができる。
【００３６】
全単射写像準備手段１２は、上記初期値設定手段１１により設定された写像関数を用いて、少なくとも１つの原全単射写像と、上記原全単射写像の逆写像と上記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備するものである。また、写像値計算手段１３は、上記全単射写像準備手段１２により準備された、上記原全単射写像を一度ずつ用いて写像値を得た後に更に上記周期延長用全単射写像により写像値を得る処理を繰り返すものである。
【００３７】
ビット列抽出手段１４は、上記写像値計算手段１３により得られた写像値からビット列を抽出するものである。擬似乱数出力手段１５は、上記ビット列抽出手段１４によって抽出されたビット列を上記初期値設定手段１１により設定されたビット長となるまで出力するものである。
【００３８】
擬似乱数生成装置は、図４に示されるコンピュータシステム１００により実現される。このコンピュータシステム１００は、擬似乱数を生成するコンピュータとしてのＣＰＵ１０１と、ＣＰＵ１０１が用いる擬似乱数生成用プログラムが格納され、またＣＰＵ１０１が行った演算結果などが記憶されるメモリ１０２とを備えている。
【００３９】
ＣＰＵ１０１には、キーボードやマウスなどのデータを入力するための入力部１０３と、生成された擬似乱数を表示出力やプリント出力或いは別システムに出力するための出力部１０４が備えられている。
【００４０】
このＣＰＵ１０１がメモリ１０２内の図５に示されるフローチャートに対応する擬似乱数生成用プログラムを実行することによって、図３の各手段として機能する。以下、このフローチャートに基づき擬似乱数生成装置の動作を説明する。スタートとなり、初期化処理を行う（Ｓ１１）。初期化処理Ｓ１１においは、例えばシードＳｅｅｄが与えられ、このシードＳｅｅｄに基づき予め用意されている写像関数が複数である場合に、１写像関数を選択する。写像関数としては、線形合同法による写像、Ｍ系列乱数の写像、GFSR(Generalized Feedbacked Shift Register)の写像、Twisted GFSR（GFSRの改良）の写像、メルセンヌツイスター（TGFSRの改良）の写像、変形テント写像、その他全単射を満たす任意の全単射写像（図２に示した写像等）を用いることができる。１つの写像関数を有する場合には、シードＳｅｅｄに基づく選択は行われない。シードＳｅｅｄは、プログラムの立ち上り毎に適当な数値を発生させるなどにより与えられるようにし、シードＳｅｅｄと写像関数を対応付けたテーブルなどにより関数選択を行う。
【００４１】
更に、初期化処理Ｓ１１においは、シードＳｅｅｄに基づく写像初期値ｘ0の決定（決定手法は写像関数と同様）、写像回数ｉを０とする初期化、写像の順番の設定、擬似乱数のランダムビット長ｎの設定（ユーザによる入力）などが行われる。
【００４２】
ステップＳ１１に続いて、上記で選択した写像関数からＫ個の全単射写像ｆ0〜ｆK-1を生成して写像の準備を行う（Ｓ１２）。ここで準備された全単射写像ｆ0〜ｆK-1を、上記写像関数から生成したという意味で原全単射写像という。ステップＳ１２の次には、上記ステップＳ１２において準備された原全単射写像を用いて、ステップＳ１１の初期化処理において設定された写像の順番に基づき、写像計算を行って１つの写像値を得る。（Ｓ１３）。
【００４３】
写像計算（Ｓ１３）では、ステップＳ１２において準備された原単射写像ｆy1の数がＫであるとき、次の（式３）の漸化式により計算を行う。また、関数ｈによって写像の順番を選択する。
【数３】
【００４４】
上記のステップＳ１３において写像値ｘi+1が得られると、ｉをｉ＋１へカウントアップし（Ｓ１４）、ステップＳ１１の初期化処理において設定された位置の所定ビットを抽出してバッファへ蓄積する（Ｓ１５）。例えば、最下位１ビットを抽出する場合の抽出式は、ｘi+1＆１である。
【００４５】
ステップＳ１５に続いて、蓄積したビット列を出力するタイミングであるかを検出し（Ｓ１６）、ＹＥＳである場合には蓄積しておいたビット列を出力する（Ｓ１７）。出力タイミングとしては、（１）バッファが満杯になった時点に出力、（２）システムの要求時に出力、（３）ユーザの要求時に出力のいずれかなどが初期設定される。ステップＳ１６においてＮＯである場合には、ステップＳ１８へ進む。
【００４６】
ステップＳ１６においてＮＯへ分岐するか、またはステップＳ１７における処理が終わると、周期延長用全単射写像を準備するか否かの判定を行う（Ｓ１８）。つまり、Ｋ回の原全単射写像による写像が終わったか検出される。ここで、ステップＳ１８においてＹＥＳとなると、ステップＳ１９において周期延長用全単射写像を準備する。
【００４７】
具体的には、既に述べた通り、原全単射写像“f0、f1・・・、fK-1”の逆写像“f0-1、f1-1 ・・・、fK-1-1”を生成し、また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ・・・、fK-1-1”とエルゴード的な全単射写像“α“を用いて乗算を行い、写像“Ｑ”を作る。ここで、次の（式４）以降の関係が成り立っている。
【００４８】
【数４】
【００４９】
このステップＳ１９の次には、ステップＳ１３へ進み、ステップＳ１９において準備された周期延長用全単射写像xi+1による写像計算を行って１つの写像値を得る（Ｓ１３）。一方、上記ステップＳ１８において、ＮＯとなるとステップＳ２０へ進んで、これまでに生成された擬似乱数のランダムビット長が初期設定された長さｎとなったかを検出し（Ｓ２０）、ＮＯであればステップＳ１２へ戻って処理を続け、ステップＳ２０においてＹＥＳとなると処理を終了してエンドとなる。
【００５０】
このように、全単射写像準備手段１２は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するものである。そして、上記図５に示されるフローチャートでは、全単射写像準備手段１２が、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備する（ステップＳ１９）ことを示した。しかし、これによらず、次の図６のフローチャートに示すように、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備する（ステップＳ３０）としても良い。
【００５１】
図６のフローチャートにおいては、ステップＳ３０において、ステップＳ１１で選択した写像関数からＫ個の全単射写像ｆ0〜ｆK-1を生成して写像の準備を行うと共に、原全単射写像“f0、f1・・・、fK-1”の逆写像“f0-1、f1-1 ・・・、fK-1-1”を生成し、また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ・・・、fK-1-1”とエルゴード的な全単射写像“α“を用いて乗算を行い、写像“Ｑ”を作る。
【００５２】
作成した写像“Ｑ”は、処理に備えてメモリ１０２内のバッファに格納しておき、必要な周期においてステップＳ１３において用いる。エルゴード的な全単射写像“α“は、写像の集合要素を単純にシフト（ｆ（ｘ）＝（ｘ＋１）ｍｏｄＮ ただし、Ｎは集合の数）したものとすることができる。この場合、１周期毎にシフト量を変化させるなどして１周期毎に異なるαを作成し、これを用いて周期延長用全単射写像を準備するようにしても良い。１周期毎に異なるαを作成することは、図５のフローチャートにおいてステップＳ１９で行うようにしても良い。
【００５３】
図６のフローチャートにおいてステップＳ３０以外では、図５のフローチャートにおける、周期延長用全単射写像を準備するか否かの判定を行うステップＳ１８と周期延長用全単射写像を準備するステップＳ１９の処理が削除される。また、ステップＳ２０において、ＮＯへ分岐するとステップＳ１３へ戻って処理を続ける。これ以外は、図５において説明した処理と同様の処理が行われる。
【００５４】
次に、写像関数を線形合同法の写像とした場合に行われる擬似乱数生成処理の一例を説明する。一般的に利用されている線形合同法の式は次の（式５）で与えられる。
【００５５】
【数５】
【００５６】
例としてM＝7とした場合、ａ＝２，ｃ＝０の時、全単射写像“f0”とすると
【００５７】
【数６】
【００５８】
上記（式６）による列は、初期値Ｘ0 ＝１のとき、
１，２，４を繰り返す周期長３の周期帯と、
初期値Ｘ0 ＝３のとき
３，６，５を繰り返す周期長３の周期帯との計２つの周期帯が存在する。
【００５９】
ａ＝５，ｃ＝０のとき、全単射写像“f1”とすると
【００６０】
【数７】
【００６１】
上記（式７）から
１，５，４，６，２，３の最大周期長６で循環する列が得られる。
２つの全単射写像“f0、f1”と、最大周期と一様性を実現する写像“Ｑ”を用いて写像の列を作る。“f0、f1”の逆写像“f0-1、f1-1 ”と、ここでエルゴード的な全単射写像αは、次の通りである。
【００６２】
【数８】
【００６３】
このような全単射写像“α“と、上記逆写像“f0-1、f1-1 ”を用意して最大周期と一様性を実現する写像“Ｑ”をＱ＝αf0-1f1-1により計算すると
【００６４】
【数９】
【００６５】
が得られ、“ｆ０→ｆ１→Ｑ”の各初期値から得られる列は、図７のようになる。初期値が１の場合
1, 2, 3, 2, 4, 6, 3, 6, 2, 4, 1, 5, 5, 3, 1, 6, 5, 4
になり、最大周期長が３×６＝１８である、一様な出現頻度を満たす数列が得られる。
【００６６】
次に、写像関数をM系列乱数で知られるGFSR(Generalized Feedbacked Shift Register)の写像とした場合に行われる擬似乱数生成処理の一例を説明する。GFSRの漸化式は（式８）の通りであり、ここでｎ＝３，ｍ＝１の場合には、（式９）となる。
【００６７】
【数１０】
【００６８】
これにより、周期長７(2n-1)の循環する数列が生成できる。GFSRの全単射写像を“f0”とすると、f0は次の（式１０）となる。
【００６９】
【数１１】
【００７０】
次に、“ f0” と最大周期と一様性を実現する写像“Ｑ”を用いて写像の列を作る。なお、GFSRでは設定の自由度が初期値ｘ0のみであり、数列のパターンは１つだけである。“f0”の逆写像“f0-1”と、ここでエルゴード的な全単射写像αは、次の通りである。
【００７１】
【数１２】
【００７２】
このような全単射写像“α“と、上記逆写像“f0-1”を用意して最大周期と一様性を実現する写像 “Ｑ”をＱ＝αf0-1により計算すると次のＱが得られる。
【００７３】
【数１３】
【００７４】
ｆ０とＱを用いて、“ｆ０→Ｑ”とする写像を繰り返し、各初期値から得られる数列は図８に示す通りとなる。初期値が１の場合
1, 4, 2, 5, 3, 1, 4, 2, 5, 6, 6, 7, 7, 3, 1
となり、最大周期長が２×７＝１４であり、一様な出現頻度を満たす数列が得られる。
【００７５】
次に、写像関数をM系列乱数で知られるGFSRの改良版であるTGFSR(Twisted Generalized Feedbacked Shift Register)を含む写像とした場合に行われる擬似乱数生成処理の一例を説明する。TGFSRの漸化式は次の（式１１）により表わされ、Aは次のような行列である。
【００７６】
【数１４】
【００７７】
上記行列の最下行におけるベクトルａが最大周期を実現するものを選択すれば、周期は２nω-1になる。ここでｎ＝２，ｍ＝１，ω＝２の場合には、（式１１）は次の（式１２）の漸化式となるので、この漸化式を計算する。
【００７８】
【数１５】
【００７９】
Ａの行列を次の通りとして、全単射写像を計算すると、次の“f0”が得られる。
【００８０】
【数１６】
【００８１】
上記“ f0”の写像は、
１，８，１０，１４，１１，６の周期長６の列と
２，４，５，１３，７，９の周期長６の列と
３，１２，１５の周期長３の列との、３つの短周期からなる周期帯を持つ。このため“f0”単独では最大周期が得られず、TGFSRとはならない。
【００８２】
Ａの行列を次の通りとして、全単射写像を計算すると“f1”が得られる。
【００８３】
【数１７】
上記“ f1”の写像では、
1, 12, 15, 7, 13, 3, 8, 10, 14, 11, 2, 4, 5, 9, 6
の最大周期を実現する周期長１５の数列が得られる。“f1”はエルゴード的であり、TGFSRであるといえる。“f0”の逆写像“f0-1 ”と、“f1”の逆写像“f1-1 ”と、更に、ここでエルゴード的な全単射写像αとを次の通りに用意する。
【００８４】
【数１８】
【００８５】
最大周期と一様性を実現する写像 “Ｑ”をＱ＝αf0-1f1-1により計算すると、次のＱが得られる。
【００８６】
【数１９】
【００８７】
そして、“ｆ０→ｆ１→Ｑ”の各初期値から得られる列は、図９に示す通りとなる。初期値が１の場合、
1, 8, 10, 2, 4, 5, 3, 12, 15, 4, 5, 9, 5, 13, 3, 6, 1, 12, 7, 9, 6, 8, 10, 14, 9, 2, 4, 10, 14, 11, 11, 6, 1, 12, 15, 7, 13, 7, 13, 14, 11, 2, 15, 3, 8
で循環し、最大周期長が３×１５＝４５となり、一様な出現頻度を満たす数列が得られる。
【００８８】
この設計において、一般に任意のｎ，ωでは全単射写像が２ω−１＋１個存在する。従って、全単射写像の周期を最低でも２ω−１＋１とすることができる。このとき、擬似乱数列の素周期は、（２ω−１＋１）（２nω−１）となり、各値の出現頻度は一様に、２ω−１＋１となる。例えば、ω＝３２，ｎ＝６２４のとき、素周期は（２３１＋１）（２１９９６８−１）となり、同じ演算精度32ビットで、状態の次元が３２×６２４であるメルセンヌツイスター19937の周期２１９９３７−１より、遥かに長い周期列が得られる。
【００８９】
次に、写像関数を、一次元写像を用いた全単射族である変形テント写像とした場合に行われる擬似乱数生成処理の一例を説明する。演算精度Lビットとした時、演算幅Ｎ＝２Ｌ−１で表した変形テント写像式は次の式の通りであり、変形テント写像のマップを図１０に示す。
【００９０】
【数２０】
【００９１】
上記変形テント写像式から用意できる全単射写像の数をＫとすると、下記のように各写像“ｆＭ j”の全単射写像を用意できる。ここで、用意できる全単射写像の最大個数は、Ｋ≦Nである。また、逆写像“ｆＭ j−１”は次の通りとなる。
【００９２】
【数２１】
【００９３】
更に、エルゴード的な全単射写像“α“を用意し、次式のように写像“Ｑ”を作る計算を実行する。
【００９４】
【数２２】
【００９５】
上記のように、用意したＫ個の写像“ｆＭ j“によってK回分の写像計算を行った後、写像“Ｑ”を適応して、図１１に示すようにサイクリックに写像を行う。このばあいにおいて、各全単射写像“ｆＭ j“の集合の要素数は演算精度のＮ＋１であることから、素周期（Ｎ＋１）（Ｋ＋１）であり、各値はＫ＋１回出現する。素周期長はＫ＝Ｎの時（Ｎ＋１）２であり、一様性が保証された擬似乱数列を得ることができる。
【符号の説明】
【００９６】
１１ 初期値設定手段
１２ 全単射写像準備手段
１３ 写像値計算手段
１４ ビット列抽出手段
１５ 擬似乱数出力手段
１００ コンピュータシステム
１０２ メモリ
１０３ 入力部
１０４ 出力部
【技術分野】
【０００１】
この発明は、全単射写像を用いて擬似乱数を生成する擬似乱数生成装置及び擬似乱数生成用プログラムに関するものである。
【背景技術】
【０００２】
従来の擬似乱数生成装置においては、有限演算実装における非線形（カオス）写像を用いた擬似乱数生成法を採用したものが知られている（特許文献１参照）。この従来例にあっては、全単射を保証しない写像を用いていた。また、全単射を保証するものでも、短周期帯に落ち入ることで長い周期が得られなくなることから、周期を監視する機構が必要であった。
【０００３】
また、最大周期と一様性を保証する擬似乱数生成器として線形合同法や、Ｍ系列乱数(GFSR:Generalized Feedbacked Shift Register)が知られている。しかしながら、周期が限定されており生成パターンも一方向的に決定されたものを出力する方式であり、生成パターンが限られていた。また、これらの生成法では、一素周期の中で各値が一度だけ出現する。従って、ある値を観測したらその後、その値はその周期中で出現しない。
【０００４】
上記GFSRの改良としてTwisted GFSR、メルセンヌツイスターが存在するが、周期を延ばすパラメータ帯が固定値であり、それを探索する必要があるという労力が存在する。
【０００５】
更に、写像変更ないしは写像変換を用いた擬似乱数生成装置としては、二次元キャットマップのような写像を用いるものが知られている（特許文献２参照）。しかしながら、この二次元キャットマップは暗号化や復号に不適切と言われており、また、周期延長が可能なものでもない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−１５２７０６号公報
【特許文献２】特開２００７−２６４１４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は上記のような擬似乱数生成における現状に鑑みてなされたもので、その目的は、周期延長を行い、最大周期長と一様性を確保し、かつ大量に乱数を生成することのできる、全単射写像を用いた擬似乱数生成装置及び擬似乱数生成用プログラムを提供することである。
【課題を解決するための手段】
【０００８】
本発明に係る擬似乱数生成装置は、擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段と、この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段と、前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段と、前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段と、前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段とを具備することを特徴とする。
【０００９】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、写像関数として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを用いることを特徴とする。
【００１０】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備することを特徴とする。
【００１１】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備することを特徴とする。
【００１２】
本発明に係る擬似乱数生成装置では、全単射写像準備手段は、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備することを特徴とする。
【００１３】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段、この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段、前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段、前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段、前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段として機能させることを特徴とする。
【００１４】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを写像関数として用いるように機能させることを特徴とする。
【００１５】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するように機能させることを特徴とする。
【００１６】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備するように機能させることを特徴とする。
【００１７】
本発明に係る擬似乱数生成用プログラムは、擬似乱数を生成するコンピュータを、全単射写像準備手段として、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備するように機能させることを特徴とする
【発明の効果】
【００１８】
本発明によれば、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備し、準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返すことにより写像値計算を行うので、周期延長用全単射写像によって周期延長が行われ、最大周期長と一様性を確保することができる。
【００１９】
本発明では、全単射写像であれば制限なく利用可能であり、写像の順番の入れ替えや再利用もできるため、生成パターンを豊富に提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の擬似乱数生成装置における全単射族による写像値の周期延長手法について説明するための写像値巡回状態を示す図。
【図２】本発明の擬似乱数生成装置における全単射族による写像値の周期延長全単射写像の生成について説明するための図。
【図３】本発明に係る擬似乱数生成装置の構成を示すブロック図。
【図４】本発明に係る擬似乱数生成装置を構成するコンピュータシステムのブロック図。
【図５】本発明に係る擬似乱数生成装置の第１の実施例の動作を説明するためのフローチャート。
【図６】本発明に係る擬似乱数生成装置の第２の実施例の動作を説明するためのフローチャート。
【図７】本発明の擬似乱数生成装置における全単射族による写像として、線形合同法を用いた各初期値の列を示す図。
【図８】本発明の擬似乱数生成装置における全単射族による写像として、M系列(GFSR)を用いた各初期値の列を示す図。
【図９】本発明の擬似乱数生成装置における全単射族による写像として、M系列(TGFSR)を用いた各初期値の列を示す図。
【図１０】本発明の擬似乱数生成装置における全単射族による写像として用いる、変形テント写像のマップを示す図。
【図１１】本発明の擬似乱数生成装置における全単射族による写像として、変形テント写像を用いた写像遷移を示す図。
【発明を実施するための形態】
【００２１】
以下添付図面を参照して、本発明に係る擬似乱数生成装置及び擬似乱数生成用プログラムを説明する。原理は次の通りである。例として次の（式１）に示す有限集合ｘ（集合の数が４）の全単射族の写像“ f0、f1、f2”を３つ用意した場合の、図１の如き写像の列を例とする。
【００２２】
【数１】
【００２３】
これらの漸化式は次の（式２）により表わされる。
【００２４】
【数２】
【００２５】
上記において、選択する写像関数ｆｙｉの順番ｙｉに制限はないが、図１の例では
ｙｉ＝（ｉ＋１）ｍｏｄ３ （ｉ＝０，１，…）を用いている。
【００２６】
上記写像によって繰り返し写像を行って得られる数列は、初期値ｘ０＝０のとき、
0, 2, 1, 3, 1, 2, 2, 0, 3
を繰り返す周期長９の周期帯（初期値ｘ０＝２、ｘ０＝３によっても写像結果である数列のパターンが同じ）が得られる。また、初期値ｘ０＝１のときには、
1, 3, 0
を繰り返す周期長３の周期帯が得られる。このように例示の写像をそのまま用いた場合には、生成パターンが２つの周期帯に分かれて存在する。
【００２７】
このように全単射写像を単に用いただけでは周期帯がいくつかに分かれ、短周期が存在し、各値の出現頻度が一様にならない。係る系として、有限演算下での非線形写像を用いて得られる乱数列があり、長周期性と一様性の保証された擬似乱数列を得ようとした場合に課題となる。
【００２８】
ここで、“f2”を理想的な写像“Q”に変更することによって、３種類の写像を用いる場合の最大周期長１２を実現し、かつ各値の出現頻度が一様に３となる数列を得ることを可能にする。即ち、長周期性と一様性の保証された擬似乱数列を得るための理想的な全単射写像“Ｑ”を次のようにして作成する。
【００２９】
まず、図１にて用いた全単射写像“f0、f1”の逆写像“f0-1、f1-1 ”を生成する。また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ”とエルゴード的な全単射写像“α“を用いて、図２に示すように写像“Ｑ”を作る計算（Ｑ＝αf0-1f1-1）を実行する。
【００３０】
このように、図１にて用いた全単射写像“f2”を“Q”に変更することで、初期値ｘ０＝１のとき
0, 2, 1, 1, 3, 0, 2, 0, 3, 3, 1, 2
を繰り返す最大周期長１２の数列が得られ、各値の出現頻度が一様な値（3回）である数列を得ることが可能となる。
【００３１】
即ち、図２で用いた全単射写像の数が“３”であり、集合の数が“４”であり、素周期が３種類の全単射写像を用いるとき、その最大周期長は、３×４＝１２から求められる。そして、上記の通り、各値の出現頻度が一様に３回となっている擬似乱数列が得られていることが分かる。
【００３２】
上記において、選択する写像関数“ｆｙｉ”（ｙｉ＝ｉｍｏｄＫ:iは写像回数、Ｋは用意した全単射写像の数）は全単射であれば何でもよく、写像関数“ｆｙｉ”は１回の写像の度に変更する。
【００３３】
図２で用いた周期延長計算に利用する写像“α“はいくつかの周期帯に分かれて短周期に落ちない、最大周期を持つ全単射写像であればよい（本発明において、周期延長計算に利用する写像“α“を「エルゴード的な全単射写像」と呼ぶ）。例えば、写像の集合要素を単純にシフト（ｆ（ｘ）＝（ｘ＋１）ｍｏｄＮ ただし、Ｎは集合の数）したものとすることができる。選択した全単射写像の逆写像とエルゴード的な全単射写像とを用い、周期を延長する写像“Ｑ”を計算して作ることが重要である。これによって、最大周期長と一様性を持つ乱数列を生成可能になることが分かった。
【００３４】
選択し得る全単射写像は、最大周期をもつ擬似乱数生成方法で知られる線形合同法、M系列(GSFR)、GSFRの周期を延長させた改良版（Twisted GFSR、メルセンヌツイスター等）のような完成されたものを用いることもできるが、短周期帯を含んでいても全単射写像であれば特に制限はない。これらの系では乱数列パターンは決定されているが、全単射写像“ｆｙｉ”の順番の入れ替えや写像“Q”を変更することで乱数列のパターンを、より豊富に作ることが可能である。
【００３５】
本発明の実施例に係る擬似乱数生成装置は、図３に示すように構成される。即ち、初期値設定手段１１、全単射写像準備手段１２、写像値計算手段１３、ビット列抽出手段１４及び擬似乱数出力手段１５を備える。初期値設定手段１１は、擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定するものである。初期値に関しては、コンピュータシステムのキーボードなどの入力手段から入力することができる。
【００３６】
全単射写像準備手段１２は、上記初期値設定手段１１により設定された写像関数を用いて、少なくとも１つの原全単射写像と、上記原全単射写像の逆写像と上記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備するものである。また、写像値計算手段１３は、上記全単射写像準備手段１２により準備された、上記原全単射写像を一度ずつ用いて写像値を得た後に更に上記周期延長用全単射写像により写像値を得る処理を繰り返すものである。
【００３７】
ビット列抽出手段１４は、上記写像値計算手段１３により得られた写像値からビット列を抽出するものである。擬似乱数出力手段１５は、上記ビット列抽出手段１４によって抽出されたビット列を上記初期値設定手段１１により設定されたビット長となるまで出力するものである。
【００３８】
擬似乱数生成装置は、図４に示されるコンピュータシステム１００により実現される。このコンピュータシステム１００は、擬似乱数を生成するコンピュータとしてのＣＰＵ１０１と、ＣＰＵ１０１が用いる擬似乱数生成用プログラムが格納され、またＣＰＵ１０１が行った演算結果などが記憶されるメモリ１０２とを備えている。
【００３９】
ＣＰＵ１０１には、キーボードやマウスなどのデータを入力するための入力部１０３と、生成された擬似乱数を表示出力やプリント出力或いは別システムに出力するための出力部１０４が備えられている。
【００４０】
このＣＰＵ１０１がメモリ１０２内の図５に示されるフローチャートに対応する擬似乱数生成用プログラムを実行することによって、図３の各手段として機能する。以下、このフローチャートに基づき擬似乱数生成装置の動作を説明する。スタートとなり、初期化処理を行う（Ｓ１１）。初期化処理Ｓ１１においは、例えばシードＳｅｅｄが与えられ、このシードＳｅｅｄに基づき予め用意されている写像関数が複数である場合に、１写像関数を選択する。写像関数としては、線形合同法による写像、Ｍ系列乱数の写像、GFSR(Generalized Feedbacked Shift Register)の写像、Twisted GFSR（GFSRの改良）の写像、メルセンヌツイスター（TGFSRの改良）の写像、変形テント写像、その他全単射を満たす任意の全単射写像（図２に示した写像等）を用いることができる。１つの写像関数を有する場合には、シードＳｅｅｄに基づく選択は行われない。シードＳｅｅｄは、プログラムの立ち上り毎に適当な数値を発生させるなどにより与えられるようにし、シードＳｅｅｄと写像関数を対応付けたテーブルなどにより関数選択を行う。
【００４１】
更に、初期化処理Ｓ１１においは、シードＳｅｅｄに基づく写像初期値ｘ0の決定（決定手法は写像関数と同様）、写像回数ｉを０とする初期化、写像の順番の設定、擬似乱数のランダムビット長ｎの設定（ユーザによる入力）などが行われる。
【００４２】
ステップＳ１１に続いて、上記で選択した写像関数からＫ個の全単射写像ｆ0〜ｆK-1を生成して写像の準備を行う（Ｓ１２）。ここで準備された全単射写像ｆ0〜ｆK-1を、上記写像関数から生成したという意味で原全単射写像という。ステップＳ１２の次には、上記ステップＳ１２において準備された原全単射写像を用いて、ステップＳ１１の初期化処理において設定された写像の順番に基づき、写像計算を行って１つの写像値を得る。（Ｓ１３）。
【００４３】
写像計算（Ｓ１３）では、ステップＳ１２において準備された原単射写像ｆy1の数がＫであるとき、次の（式３）の漸化式により計算を行う。また、関数ｈによって写像の順番を選択する。
【数３】
【００４４】
上記のステップＳ１３において写像値ｘi+1が得られると、ｉをｉ＋１へカウントアップし（Ｓ１４）、ステップＳ１１の初期化処理において設定された位置の所定ビットを抽出してバッファへ蓄積する（Ｓ１５）。例えば、最下位１ビットを抽出する場合の抽出式は、ｘi+1＆１である。
【００４５】
ステップＳ１５に続いて、蓄積したビット列を出力するタイミングであるかを検出し（Ｓ１６）、ＹＥＳである場合には蓄積しておいたビット列を出力する（Ｓ１７）。出力タイミングとしては、（１）バッファが満杯になった時点に出力、（２）システムの要求時に出力、（３）ユーザの要求時に出力のいずれかなどが初期設定される。ステップＳ１６においてＮＯである場合には、ステップＳ１８へ進む。
【００４６】
ステップＳ１６においてＮＯへ分岐するか、またはステップＳ１７における処理が終わると、周期延長用全単射写像を準備するか否かの判定を行う（Ｓ１８）。つまり、Ｋ回の原全単射写像による写像が終わったか検出される。ここで、ステップＳ１８においてＹＥＳとなると、ステップＳ１９において周期延長用全単射写像を準備する。
【００４７】
具体的には、既に述べた通り、原全単射写像“f0、f1・・・、fK-1”の逆写像“f0-1、f1-1 ・・・、fK-1-1”を生成し、また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ・・・、fK-1-1”とエルゴード的な全単射写像“α“を用いて乗算を行い、写像“Ｑ”を作る。ここで、次の（式４）以降の関係が成り立っている。
【００４８】
【数４】
【００４９】
このステップＳ１９の次には、ステップＳ１３へ進み、ステップＳ１９において準備された周期延長用全単射写像xi+1による写像計算を行って１つの写像値を得る（Ｓ１３）。一方、上記ステップＳ１８において、ＮＯとなるとステップＳ２０へ進んで、これまでに生成された擬似乱数のランダムビット長が初期設定された長さｎとなったかを検出し（Ｓ２０）、ＮＯであればステップＳ１２へ戻って処理を続け、ステップＳ２０においてＹＥＳとなると処理を終了してエンドとなる。
【００５０】
このように、全単射写像準備手段１２は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するものである。そして、上記図５に示されるフローチャートでは、全単射写像準備手段１２が、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備する（ステップＳ１９）ことを示した。しかし、これによらず、次の図６のフローチャートに示すように、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備する（ステップＳ３０）としても良い。
【００５１】
図６のフローチャートにおいては、ステップＳ３０において、ステップＳ１１で選択した写像関数からＫ個の全単射写像ｆ0〜ｆK-1を生成して写像の準備を行うと共に、原全単射写像“f0、f1・・・、fK-1”の逆写像“f0-1、f1-1 ・・・、fK-1-1”を生成し、また、エルゴード的な全単射写像“α“を用意する。そして、これら逆写像“f0-1、f1-1 ・・・、fK-1-1”とエルゴード的な全単射写像“α“を用いて乗算を行い、写像“Ｑ”を作る。
【００５２】
作成した写像“Ｑ”は、処理に備えてメモリ１０２内のバッファに格納しておき、必要な周期においてステップＳ１３において用いる。エルゴード的な全単射写像“α“は、写像の集合要素を単純にシフト（ｆ（ｘ）＝（ｘ＋１）ｍｏｄＮ ただし、Ｎは集合の数）したものとすることができる。この場合、１周期毎にシフト量を変化させるなどして１周期毎に異なるαを作成し、これを用いて周期延長用全単射写像を準備するようにしても良い。１周期毎に異なるαを作成することは、図５のフローチャートにおいてステップＳ１９で行うようにしても良い。
【００５３】
図６のフローチャートにおいてステップＳ３０以外では、図５のフローチャートにおける、周期延長用全単射写像を準備するか否かの判定を行うステップＳ１８と周期延長用全単射写像を準備するステップＳ１９の処理が削除される。また、ステップＳ２０において、ＮＯへ分岐するとステップＳ１３へ戻って処理を続ける。これ以外は、図５において説明した処理と同様の処理が行われる。
【００５４】
次に、写像関数を線形合同法の写像とした場合に行われる擬似乱数生成処理の一例を説明する。一般的に利用されている線形合同法の式は次の（式５）で与えられる。
【００５５】
【数５】
【００５６】
例としてM＝7とした場合、ａ＝２，ｃ＝０の時、全単射写像“f0”とすると
【００５７】
【数６】
【００５８】
上記（式６）による列は、初期値Ｘ0 ＝１のとき、
１，２，４を繰り返す周期長３の周期帯と、
初期値Ｘ0 ＝３のとき
３，６，５を繰り返す周期長３の周期帯との計２つの周期帯が存在する。
【００５９】
ａ＝５，ｃ＝０のとき、全単射写像“f1”とすると
【００６０】
【数７】
【００６１】
上記（式７）から
１，５，４，６，２，３の最大周期長６で循環する列が得られる。
２つの全単射写像“f0、f1”と、最大周期と一様性を実現する写像“Ｑ”を用いて写像の列を作る。“f0、f1”の逆写像“f0-1、f1-1 ”と、ここでエルゴード的な全単射写像αは、次の通りである。
【００６２】
【数８】
【００６３】
このような全単射写像“α“と、上記逆写像“f0-1、f1-1 ”を用意して最大周期と一様性を実現する写像“Ｑ”をＱ＝αf0-1f1-1により計算すると
【００６４】
【数９】
【００６５】
が得られ、“ｆ０→ｆ１→Ｑ”の各初期値から得られる列は、図７のようになる。初期値が１の場合
1, 2, 3, 2, 4, 6, 3, 6, 2, 4, 1, 5, 5, 3, 1, 6, 5, 4
になり、最大周期長が３×６＝１８である、一様な出現頻度を満たす数列が得られる。
【００６６】
次に、写像関数をM系列乱数で知られるGFSR(Generalized Feedbacked Shift Register)の写像とした場合に行われる擬似乱数生成処理の一例を説明する。GFSRの漸化式は（式８）の通りであり、ここでｎ＝３，ｍ＝１の場合には、（式９）となる。
【００６７】
【数１０】
【００６８】
これにより、周期長７(2n-1)の循環する数列が生成できる。GFSRの全単射写像を“f0”とすると、f0は次の（式１０）となる。
【００６９】
【数１１】
【００７０】
次に、“ f0” と最大周期と一様性を実現する写像“Ｑ”を用いて写像の列を作る。なお、GFSRでは設定の自由度が初期値ｘ0のみであり、数列のパターンは１つだけである。“f0”の逆写像“f0-1”と、ここでエルゴード的な全単射写像αは、次の通りである。
【００７１】
【数１２】
【００７２】
このような全単射写像“α“と、上記逆写像“f0-1”を用意して最大周期と一様性を実現する写像 “Ｑ”をＱ＝αf0-1により計算すると次のＱが得られる。
【００７３】
【数１３】
【００７４】
ｆ０とＱを用いて、“ｆ０→Ｑ”とする写像を繰り返し、各初期値から得られる数列は図８に示す通りとなる。初期値が１の場合
1, 4, 2, 5, 3, 1, 4, 2, 5, 6, 6, 7, 7, 3, 1
となり、最大周期長が２×７＝１４であり、一様な出現頻度を満たす数列が得られる。
【００７５】
次に、写像関数をM系列乱数で知られるGFSRの改良版であるTGFSR(Twisted Generalized Feedbacked Shift Register)を含む写像とした場合に行われる擬似乱数生成処理の一例を説明する。TGFSRの漸化式は次の（式１１）により表わされ、Aは次のような行列である。
【００７６】
【数１４】
【００７７】
上記行列の最下行におけるベクトルａが最大周期を実現するものを選択すれば、周期は２nω-1になる。ここでｎ＝２，ｍ＝１，ω＝２の場合には、（式１１）は次の（式１２）の漸化式となるので、この漸化式を計算する。
【００７８】
【数１５】
【００７９】
Ａの行列を次の通りとして、全単射写像を計算すると、次の“f0”が得られる。
【００８０】
【数１６】
【００８１】
上記“ f0”の写像は、
１，８，１０，１４，１１，６の周期長６の列と
２，４，５，１３，７，９の周期長６の列と
３，１２，１５の周期長３の列との、３つの短周期からなる周期帯を持つ。このため“f0”単独では最大周期が得られず、TGFSRとはならない。
【００８２】
Ａの行列を次の通りとして、全単射写像を計算すると“f1”が得られる。
【００８３】
【数１７】
上記“ f1”の写像では、
1, 12, 15, 7, 13, 3, 8, 10, 14, 11, 2, 4, 5, 9, 6
の最大周期を実現する周期長１５の数列が得られる。“f1”はエルゴード的であり、TGFSRであるといえる。“f0”の逆写像“f0-1 ”と、“f1”の逆写像“f1-1 ”と、更に、ここでエルゴード的な全単射写像αとを次の通りに用意する。
【００８４】
【数１８】
【００８５】
最大周期と一様性を実現する写像 “Ｑ”をＱ＝αf0-1f1-1により計算すると、次のＱが得られる。
【００８６】
【数１９】
【００８７】
そして、“ｆ０→ｆ１→Ｑ”の各初期値から得られる列は、図９に示す通りとなる。初期値が１の場合、
1, 8, 10, 2, 4, 5, 3, 12, 15, 4, 5, 9, 5, 13, 3, 6, 1, 12, 7, 9, 6, 8, 10, 14, 9, 2, 4, 10, 14, 11, 11, 6, 1, 12, 15, 7, 13, 7, 13, 14, 11, 2, 15, 3, 8
で循環し、最大周期長が３×１５＝４５となり、一様な出現頻度を満たす数列が得られる。
【００８８】
この設計において、一般に任意のｎ，ωでは全単射写像が２ω−１＋１個存在する。従って、全単射写像の周期を最低でも２ω−１＋１とすることができる。このとき、擬似乱数列の素周期は、（２ω−１＋１）（２nω−１）となり、各値の出現頻度は一様に、２ω−１＋１となる。例えば、ω＝３２，ｎ＝６２４のとき、素周期は（２３１＋１）（２１９９６８−１）となり、同じ演算精度32ビットで、状態の次元が３２×６２４であるメルセンヌツイスター19937の周期２１９９３７−１より、遥かに長い周期列が得られる。
【００８９】
次に、写像関数を、一次元写像を用いた全単射族である変形テント写像とした場合に行われる擬似乱数生成処理の一例を説明する。演算精度Lビットとした時、演算幅Ｎ＝２Ｌ−１で表した変形テント写像式は次の式の通りであり、変形テント写像のマップを図１０に示す。
【００９０】
【数２０】
【００９１】
上記変形テント写像式から用意できる全単射写像の数をＫとすると、下記のように各写像“ｆＭ j”の全単射写像を用意できる。ここで、用意できる全単射写像の最大個数は、Ｋ≦Nである。また、逆写像“ｆＭ j−１”は次の通りとなる。
【００９２】
【数２１】
【００９３】
更に、エルゴード的な全単射写像“α“を用意し、次式のように写像“Ｑ”を作る計算を実行する。
【００９４】
【数２２】
【００９５】
上記のように、用意したＫ個の写像“ｆＭ j“によってK回分の写像計算を行った後、写像“Ｑ”を適応して、図１１に示すようにサイクリックに写像を行う。このばあいにおいて、各全単射写像“ｆＭ j“の集合の要素数は演算精度のＮ＋１であることから、素周期（Ｎ＋１）（Ｋ＋１）であり、各値はＫ＋１回出現する。素周期長はＫ＝Ｎの時（Ｎ＋１）２であり、一様性が保証された擬似乱数列を得ることができる。
【符号の説明】
【００９６】
１１ 初期値設定手段
１２ 全単射写像準備手段
１３ 写像値計算手段
１４ ビット列抽出手段
１５ 擬似乱数出力手段
１００ コンピュータシステム
１０２ メモリ
１０３ 入力部
１０４ 出力部
【特許請求の範囲】
【請求項１】
擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段と、
この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段と、
前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段と、
前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段と、
前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段と
を具備することを特徴とする擬似乱数生成装置。
【請求項２】
全単射写像準備手段は、写像関数として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを用いることを特徴とする請求項１に記載の擬似乱数生成装置。
【請求項３】
全単射写像準備手段は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備することを特徴とする請求項１または２に記載の擬似乱数生成装置。
【請求項４】
全単射写像準備手段は、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備することを特徴とする請求項１乃至３のいずれか１項に記載の擬似乱数生成装置。
【請求項５】
全単射写像準備手段は、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備することを特徴とする請求項１乃至３のいずれか１項に記載の擬似乱数生成装置。
【請求項６】
擬似乱数を生成するコンピュータを、
擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段、
この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段、
前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段、
前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段、
前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段
として機能させる擬似乱数生成用プログラム。
【請求項７】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを写像関数として用いるように機能させることを特徴とする請求項６に記載の擬似乱数生成用プログラム。
【請求項８】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するように機能させることを特徴とする請求項６または７に記載の擬似乱数生成装置。
【請求項９】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備するように機能させることを特徴とする請求項６乃至８のいずれか１項に記載の擬似乱数生成用プログラム。
【請求項１０】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備するように機能させることを特徴とする請求項６乃至８のいずれか１項に記載の擬似乱数生成用プログラム。
【請求項１】
擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段と、
この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段と、
前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段と、
前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段と、
前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段と
を具備することを特徴とする擬似乱数生成装置。
【請求項２】
全単射写像準備手段は、写像関数として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを用いることを特徴とする請求項１に記載の擬似乱数生成装置。
【請求項３】
全単射写像準備手段は、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備することを特徴とする請求項１または２に記載の擬似乱数生成装置。
【請求項４】
全単射写像準備手段は、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備することを特徴とする請求項１乃至３のいずれか１項に記載の擬似乱数生成装置。
【請求項５】
全単射写像準備手段は、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備することを特徴とする請求項１乃至３のいずれか１項に記載の擬似乱数生成装置。
【請求項６】
擬似乱数を生成するコンピュータを、
擬似乱数の生成に必要な写像関数と擬似乱数のビット長の初期値を設定する初期値設定手段、
この初期値設定手段により設定された写像関数を用いて、少なくとも１つの原全単射写像と、前記原全単射写像の逆写像と前記原全単射写像についてエルゴード的な全単射写像との写像計算により得られる周期延長用全単射写像と、を準備する全単射写像準備手段、
前記全単射写像準備手段により準備された、前記原全単射写像を一度ずつ用いて写像値を得た後に更に前記周期延長用全単射写像を用いて写像値を得る処理を繰り返す写像値計算手段、
前記写像値計算手段により得られた写像値からビット列を抽出するビット列抽出手段、
前記ビット列抽出手段によって抽出されたビット列を前記初期値設定手段により設定されたビット長となるまで出力する擬似乱数出力手段
として機能させる擬似乱数生成用プログラム。
【請求項７】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、線形合同法による写像、Ｍ系列乱数による写像、変形テント関数による写像、或いは前記以外の手法により作成した全単射写像のいずれかを写像関数として用いるように機能させることを特徴とする請求項６に記載の擬似乱数生成用プログラム。
【請求項８】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、準備した全単射写像の数と全単射写像に含まれる集合の数の乗算により決まる周期毎に、エルゴード的な全単射写像を変更した新たな周期延長用全単射写像を準備するように機能させることを特徴とする請求項６または７に記載の擬似乱数生成装置。
【請求項９】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、準備した原全単射写像数の全単射写像がなされた場合に周期延長用全単射写像を準備するように機能させることを特徴とする請求項６乃至８のいずれか１項に記載の擬似乱数生成用プログラム。
【請求項１０】
擬似乱数を生成するコンピュータを、
全単射写像準備手段として、全単射写像数の全単射写像がなされる前に予め周期延長用全単射写像を準備するように機能させることを特徴とする請求項６乃至８のいずれか１項に記載の擬似乱数生成用プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１１−１４５４６４（Ｐ２０１１−１４５４６４Ａ）
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願番号】特願２０１０−５８２３（Ｐ２０１０−５８２３）
【出願日】平成２２年１月１４日（２０１０．１．１４）
【出願人】（８９９００００５７）学校法人日本大学 (650)
【出願人】（３９１０１６３５８）東芝情報システム株式会社 (149)
【Ｆターム（参考）】
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願日】平成２２年１月１４日（２０１０．１．１４）
【出願人】（８９９００００５７）学校法人日本大学 (650)
【出願人】（３９１０１６３５８）東芝情報システム株式会社 (149)
【Ｆターム（参考）】
[ Back to top ]