(57)【要約】【課題】構成が簡易でありながら内部パラメータの頻繁な変動なしに長周期の擬似乱数を得る。【解決手段】初期パラメータ及び写像初期値を準備する初期値準備手段１０と、前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段２０と、前記写像計算手段２０により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段３０と、前記写像計算手段２０により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段２０が用いる他のパラメータを作成更新するパラメータ作成更新手段５０と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段２０による次の計算への進行と、前記ビット抽出手段３０と前記パラメータ作成更新手段５０による次処理への進行とを制御する制御手段７０とを具備する。【選択図】  図１
2010237735.tif 000002
【特許請求の範囲】
【請求項１】
初期パラメータ及び写像初期値を準備する初期値準備手段と、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段と
を具備することを特徴とする擬似乱数生成器。
【請求項２】
写像計算手段は、複数のテント関数により写像計算を行うものであり、
初期値準備手段は、シード情報を準備するものであり、
前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする請求項１に記載の擬似乱数生成器。
【請求項３】
ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項２に記載の擬似乱数生成器。
【請求項４】
初期パラメータ及び写像初期値を準備する初期値準備ステップと、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、
前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、
前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップと
を具備することを特徴とする擬似乱数生成方法。
【請求項５】
写像計算ステップでは、複数のテント関数により写像計算を行い、
初期値準備ステップでは、シード情報を準備し、
前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする請求項４に記載の擬似乱数生成方法。
【請求項６】
ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項５に記載の擬似乱数生成方法。
【請求項７】
演算により擬似乱数を生成するコンピュータを、
初期パラメータ及び写像初期値を準備する初期値準備手段、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段
として機能させる特徴とする擬似乱数生成プログラム。
【請求項８】
コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、
コンピュータを初期値準備手段として、シード情報を準備するように機能させ、
コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする請求項７に記載の擬似乱数生成プログラム。
【請求項９】
コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、
コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする請求項７に記載の擬似乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、変形テント関数を用いて擬似乱数生成を行う擬似乱数生成器、またその擬似乱数生成方法及び擬似乱数生成プログラムに関するものである。
【背景技術】
【０００２】
従来のテント型写像を用いた乱数の生成においては、内部パラメータの変動を写像計算の都度に行うことにより軌道の拡散を図っている（特許文献１参照）。しかしながら、この手法によると、内部パラメータの変動処理が写像計算の都度に発生し、処理が複雑化し時間を要するものであった。また、乱数として使用できる部分は写像値の下位側ビットに限られるという問題があった。
【０００３】
また、平文を初期値X0としX0を変形テント写像を用いて写像し暗号文Y を生成する一方、復号は逆写像し暗号文Y を平文X0に戻すという暗号化及び復号手法も知られている。この暗号化及び復号においては、鍵A から副鍵ANを複数生成し、写像(N) 毎に異なる副鍵ANを入力することでスライド攻撃に強い暗号方式を提供するものである（特許文献２参照）。この技術は、暗号化と復号を行うものであり、擬似乱数そのものを生成する手法ではなく、生成した擬似乱数により暗号化を行うものではない。
【０００４】
更に、変形テント関数を用い、固定演算化したカオスの系から乱数値を抽出するものも知られている。この手法においては、周期の検出機構を設け、周期検出後に副鍵を用いるものである（特許文献３参照）。このものでは、カオスのシステムはどれでもよいとされているが、特に連続系のカオス（微分方程式系）での例が示されており、微分方程式系では一般的に乱数生成に時間がかかる問題がある。また、長い乱数値を抽出する場合には、その分、副鍵が複数個必要となることが予想され、鍵の管理が煩雑になるという問題がある。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、上記のような擬似乱数生成における問題に鑑みなされたもので、その目的は、構成が簡易でありながら内部パラメータの頻繁な変動なしに長周期の擬似乱数を得ることができ、また、生成が短時間で可能な擬似乱数生成器を提供することである。また、このような擬似乱数の生成を行う擬似乱数生成方法と擬似乱数生成プログラムを提供することを他の目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る擬似乱数生成器は、初期パラメータ及び写像初期値を準備する初期値準備手段と、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段とを具備することを特徴とする。
【０００７】
本発明に係る擬似乱数生成器では、写像計算手段は、複数のテント関数により写像計算を行うものであり、初期値準備手段は、シード情報を準備するものであり、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする。
【０００８】
本発明に係る擬似乱数生成器では、ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【０００９】
本発明に係る擬似乱数生成方法は、初期パラメータ及び写像初期値を準備する初期値準備ステップと、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップとを具備することを特徴とする。
【００１０】
本発明に係る擬似乱数生成方法は、写像計算ステップでは、複数のテント関数により写像計算を行い、初期値準備ステップでは、シード情報を準備し、前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする。
【００１１】
本発明に係る擬似乱数生成方法は、ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【００１２】
本発明に係る擬似乱数生成プログラムは、演算により擬似乱数を生成するコンピュータを、初期パラメータ及び写像初期値を準備する初期値準備手段、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段として機能させる特徴とする。
【００１３】
本発明に係る擬似乱数生成プログラムでは、コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、コンピュータを初期値準備手段として、シード情報を準備するように機能させ、コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする。
【００１４】
本発明に係る擬似乱数生成プログラムでは、コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、変形テント関数を用いているため、写像計算毎に内部パラメータを変動させる必要がなく乱数生成を高速化することができるばかりでなく、ビット信号が一様にランダム化されており、所定ビットを抽出して擬似乱数を得ることができる。しかも、写像値と写像初期値との比較結果に基づき、写像計算手段が用いる他のパラメータを作成更新するので、パラメータ変更してランダム化された擬似乱数生成を続けることができる。
【００１６】
また、本発明によれば、シード情報に基づき写像計算手段が用いるテント関数を切り換えるので、テント関数の切り換えによって生成される擬似乱数のランダム化を図ることが可能である。更に、本発明によれば、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するので、写像計算によりビット信号が一様にランダム化されて写像値について抽出によって更なるランダム化を図ることができる利点がある。
【図面の簡単な説明】
【００１７】
【図１】本発明に係る擬似乱数生成器の第１の実施例の構成を示すブロック図。
【図２】本発明に係る擬似乱数生成器の第１の実施例において採用する変形テント関数を示す図。
【図３】本発明に係る擬似乱数生成器を実現するコンピュータの一例を示すブロック図。
【図４】本発明に係る擬似乱数生成器の第１の実施例の動作を説明するためのフローチャート。
【図５】本発明に係る擬似乱数生成器の第１の実施例による初期値準備処理の一例のプログラムを示す図。
【図６】本発明に係る擬似乱数生成器の第１の実施例による関数切換処理の一例のフローチャートを示す図。
【図７】本発明に係る擬似乱数生成器の第１の実施例による関数切換処理の一例のプログラムを示す図。
【図８】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一例のプログラムを示す図。
【図９】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一動作例を示す図。
【図１０】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一例のプログラムを示す図。
【図１１】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一動作例を示す図。
【図１２】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一例のプログラムを示す図。
【図１３】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一例を示す図。
【図１４】本発明に係る擬似乱数生成器の第１の実施例によるビット抽出処理の一例を示す図。
【図１５】本発明に係る擬似乱数生成器の第１の実施例によるビット列記憶処理の一例を示す図。
【図１６】本発明に係る擬似乱数生成器の第１の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【図１７】本発明に係る擬似乱数生成器の第２の実施例の構成を示すブロック図。
【図１８】本発明に係る擬似乱数生成器の第２の実施例の動作を説明するためのフローチャート。
【図１９】本発明に係る擬似乱数生成器の第２の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【発明を実施するための形態】
【００１８】
以下添付図面を参照して本発明に係る擬似乱数生成器、擬似乱数生成方法及び擬似乱数生成プログラムについて、それぞれの実施例を説明する。各図において、同一の構成要素には同一の符号を付して重複する説明を省略する。第１の実施例に係る擬似乱数生成器は、図１に示されるように、初期値準備手段１０、写像計算手段２０、ビット抽出手段３０、ビット列記憶部４０、パラメータ作成更新手段５０、切換指示手段６０、制御手段７０を備える。
【００１９】
初期値準備手段１０は、シード情報Ｓｅｅｄ、ランダムビット長ｎ、写像関数選択情報ｋ0〜ｋm-1、初期パラメータＰ及び写像初期値Ｘ0を準備するものである。シード情報Ｓｅｅｄは、ｍビットの情報であり、例えばユーザによりランダムビット長ｎと共にキー入力等されるものである。写像関数選択情報ｋ0〜ｋm-1は、切換指示手段６０により用いられる情報であり、ここで各ビットｋjは、シード情報Ｓｅｅｄを用いた任意の演算などの数値処理により得られる結果値を、更にｍビットに変更した数値列中ビットであって、先頭からｊ番目のビットを意味する。
【００２０】
写像初期値Ｘ0は、ｍビットのシードＳｅｅｄを用いた任意の演算などの数値処理により得られる結果値を、指定可能な範囲内（１≦Ｘ0≦２L−１）に適応選択した値である。例えば、ｍｏｄ  （２L−１）＋１の計算後の値を採用することができる。また、初期パラメータＰは、ｍビットのシードＳｅｅｄを用いた任意の演算などの数値処理による得られる結果値を、指定可能な範囲内（１≦Ｘ0≦２L−１）に適応選択した値である。例えば、ｍｏｄ  （２L−１）＋１の計算後の値を採用することができる。上記のＬは、写像計算手段２０における演算精度がＬビットであり、後述する変形テント関数の係数ＭがＭ＝２Lであることに起因する数値である。そして、（２L−１）は、０〜２Lには整数値（０を含む）が（２L＋１）個存在するから、この内の両端の数値である０と２Lとを除いて（２L−１）個となることを意味している。この両端の数値を除く意味は、後に説明する写像関数において、左右いずれかの写像関数の傾きが無限大となる場合を除くためのものである。
【００２１】
写像計算手段２０は、初回は初期値準備手段１０により準備された初期パラメータと写像初期値を変形テント関数に適用し写像計算を行い、２回目以降は初期パラメータ或いは他のパラメータと前回求められた写像値を変形テント関数に適用し写像計算を行うものである。
【００２２】
本実施例の写像計算手段２０は、複数のテント関数により写像計算を行うものである。ここでは、図２（ａ）と図２（ｂ）に示す２通りの変形テント関数Ｆ１、Ｆ２により写像計算を行うものであり、図２（ａ）の変形テント関数Ｆ１による変形テント写像の整数演算化式は次の式（１）に示すようであり、また、図２（ｂ）の変形テント関数Ｆ２による変形テント写像の整数演算化式は次の式（２）に示すようである。
【００２３】
【数１】
2010237735.tif 000003
【００２４】
切換指示手段６０は、シード情報Ｓｅｅｄに基づき写像計算手段２０が用いるテント関数の切り換えを指示するものである。前述の通り、初期値準備手段１０は、シード情報Ｓｅｅｄから写像関数選択情報ｋ0〜ｋm-1を得ており、この写像関数選択情報ｋ0〜ｋm-1が「１」か「０」かによって、式（１）と式（２）とのいずれか一方を選択する指示を与える。
【００２５】
ビット抽出手段３０は、写像計算手段２０により得られた写像値から所定ビットを抽出して擬似乱数とするものである。ビット抽出手段３０は、シード情報Ｓｅｅｄに基づき写像値から所定ビットを抽出する範囲を決定して、抽出を行う。つまり、写像計算手段２０により得られた写像値がＬビット長であるとき、Ｌビット長から抽出するビット数ｑをシード情報Ｓｅｅｄに基づき決定し、また、Ｌビット中のどのビットを抽出してｑビットとするかを決定する。抽出したビットは、バッファを備えるビット列記憶部４０に記憶する。記憶は、例えばビット列記憶部４０の先頭側から記憶する。
【００２６】
ビット列記憶部４０は、バッファからビット列を出力する機能を備えており、予め定められたタイミングに出力処理を行う。具体例としては、バッファが満杯になったときに出力を行う。この場合には、出力後にバッファをクリアし、バッファが満杯になったときに記憶できずに残ったビットをビット列記憶部４０の先頭側から記憶し、以降同じ処理を繰り返す。
【００２７】
パラメータ作成更新手段５０は、上記写像計算手段２０により得られる写像値Ｘiと上記写像初期値Ｘ0との比較結果に基づき、写像計算手段２０が用いる他のパラメータを作成更新するものである。写像初期値Ｘ0は初期値準備手段１０により送られるので、これをレジスタｍｅｍに記憶しておき、上記写像計算手段２０により、シード情報Ｓｅｅｄのビット長ｍと同じｍ回目の写像値Ｘiが計算されたときに、当該計算されたｍ回目の写像値Ｘiが写像初期値Ｘ0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。
【００２８】
具体的には、次の関数ｈ（Ｐ，Ｓｅｅｄ）により他のパラメータを作成更新する。
ｈ（Ｐ，Ｓｅｅｄ）＝（Ｐ＋ｒ（Ｓｅｅｄ））ｍｏｄ（２L−１）＋１
上記において、ｒ（Ｓｅｅｄ）は、シード情報Ｓｅｅｄを用いた任意の演算などの数値処理により得られる結果値を示す。
【００２９】
制御手段７０は、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、上記写像計算手段２０による次の計算への進行と、上記ビット抽出手段３０と上記パラメータ作成更新手段５０による次処理への進行とを制御するものである。具体的には、ビット抽出手段３０により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長ｎとなったかを検出し、ランダムビット長ｎとなっていなければ、次の写像計算等を行わせる一方、ランダムビット長ｎとなっている場合には、各手段による処理を終了させる。
【００３０】
以上の通りに構成された擬似乱数生成器は、例えば、図３に示されるようなコンピュータシステムにより実現される。コンピュータシステムは、ＣＰＵ１がバス２を介して主メモリ３、入力装置４、出力装置５、外部記憶装置６に接続された構成を有し、主メモリ３には擬似乱数生成プログラムＰＲＧが記憶されている。
【００３１】
上記のＣＰＵ１が、図４に示されるフローチャートに対応する擬似乱数生成プログラムＰＲＧを実行することにより図１の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。ここでは、シード情報Ｓｅｅｄとランダムビット長ｎが例えば入力装置４などの外部により与えられるものとしてあるが、擬似乱数生成プログラムＰＲＧに含まれているようにしても良い。
【００３２】
ＣＰＵ１は、擬似乱数生成プログラムＰＲＧによる動作を開始し、初期値準備処理を行う（Ｓ１１）。初期値準備処理Ｓ１１では、シード情報Ｓｅｅｄを用いて、写像関数選択情報ｋ0〜ｋm-1、初期パラメータＰ及び写像初期値Ｘ0を準備する。ここでは、図５に示す処理プログラムのように、シード情報Ｓｅｅｄをそのまま写像関数選択情報ｋ0〜ｋm-1、初期パラメータＰ及び写像初期値Ｘ0として保持し、また、ランダムビット長ｎも保持する。更に、写像初期値Ｘ0は、レジスタｍｅｍに保持する一方、写像回数ｉをリセットして０とする。
【００３３】
次に、ＣＰＵ１は、カウントアップを行う（Ｓ１２）。このカウントアップは、写像回数ｉのカウントアップであり、「ｉ←ｉ＋１」という処理である。次にＣＰＵ１は、関数切換・写像計算処理を行う（Ｓ１３）。この関数切換・写像計算処理は、切換指示手段６０と写像計算手段２０による処理であり、詳細には、前段では、図６のフローチャートに示されるように、写像関数選択情報ｋjを参照し、この写像関数選択情報ｋjが０であるか１であるかに応じて（Ｓ２１）、前述の式（１）と式（２）とのいずれか一方を整数演算化式として選択する（Ｓ２２、Ｓ２３）。これを処理プログラムとして示すと、図７のように表すことができる。上記処理より後段では、選択した上記整数演算化式により写像値Ｘiを計算する。
【００３４】
次に、ＣＰＵ１は、ビット抽出処理を行う（Ｓ１４）。ビット抽出処理では、具体的には、次の３例を挙げることができる。第１例の関数は、
ｂs〜ｂs+q＝ｇ１（Ｘi，Ｘi+1，Ｓｅｅｄ）と表すことができ、
ｑは１回の抽出ビット数（任意）を示し、ｓは抽出した総ビット数を示し、処理後において「ｓ＝ｓ＋ｑ」となる。ｇ１（Ｘi，Ｘi+1，Ｓｅｅｄ）の具体的内容は図８に示すＣ言語によるプログラムにより表すことができる。図８の右に、記号の内容を示す。
【００３５】
具体例により説明すると、図９に示すように計算された第１回目から第３回目までの写像値Ｘiを２進数で示すと、Ｘ1、Ｘ2、Ｘ3の右辺のようであり、対応するシード情報対応の写像関数選択情報ｋjが（ｋ1，ｋ2，ｋ3）＝（１，１，０）であるとすると、ｋjが０の写像値Ｘ3をビット反転させて/Ｘ3を得る。そして、Ｘ1、Ｘ2、/Ｘ3のそれぞれについて、後に得られた写像値Ｘi+1（もしくは、/Ｘi+1）におけるビットが１となっているビット位置に対応して、先に得られた写像値Ｘi（もしくは、/Ｘi）のビット値を取り出す。
【００３６】
以上の結果、図９において丸にて囲われたビット値が取り出され、バッファにＢＵＦのように、｛１，０，１，０，０，１，１，０，０，・・・｝が保持される。
【００３７】
第２例の関数は、
ｂi＝ｇ２（Ｘi，Ｘi+1，Ｓｅｅｄ）と表すことができ、
ｇ２（Ｘi，Ｘi+1，Ｓｅｅｄ）の具体的内容は図１０に示すＣ言語によるプログラムにより表すことができる。図１０の右に、記号の内容を示す。
【００３８】
具体例により説明すると、図９と途中までは等しく、図１１に示すように計算された第１回目から第３回目までの写像値Ｘiを２進数で示すと、Ｘ1、Ｘ2、Ｘ3の右辺のようであり、対応するシード情報対応の写像関数選択情報ｋjが（ｋ1，ｋ2，ｋ3）＝（１，１，０）であるとすると、ｋjが０の写像値Ｘ3をビット反転させて/Ｘ3を得る。そして、Ｘ1、Ｘ2、/Ｘ3のそれぞれについて、後に得られた写像値Ｘi+1（もしくは、/Ｘi+1）におけるビットが１となっているビット位置に対応して、先に得られた写像値Ｘi（もしくは、/Ｘi）のビット値を取り出す。
【００３９】
以上の結果、図９と同様に図１１において丸にて囲われたビット値が取り出されるわけであるが、この後に各写像値単位で、排他的論理和演算を行って、Ｘ1に対して１を抽出し、Ｘ2に対して０を抽出する。
【００４０】
第３例の関数は、
ｂi＝ｇ３（Ｘi，Ｓｅｅｄ）と表すことができ、
ｇ３（Ｘi，Ｓｅｅｄ）の具体的内容は図１２に示すＣ言語によるプログラムにより表すことができる。図１２の右に、記号の内容を示す。
【００４１】
具体例により説明すると、図１３に示すようにシード情報対応の写像関数選択情報ｋjが｛１，１，０，０，１，１，・・・｝であるとすると、１の場合にシフト量が２増加されて｛２，４，４，４，６，０（８），・・・｝とシフト量が計算される。第ｉ回目の写像値Ｘiを２進数で示すと、Ｘ1＝｛１，０，１，０，０，１，１，０，０｝であると、上記計算されたシフト量の右シフトが行われる。ｋjのシフト量が６であると、シフトＸ1は｛０，０，０，０，０，０，１，０，１｝となり、これと１の論理積を作成してビットとする。
【００４２】
図１４（ａ）は、写像関数選択情報ｋjが１の場合にシフト量が２増加される場合を示し、図１４（ｂ）は、写像関数選択情報ｋjでは２ビット（例えば、ｋjとｋj+1）を用いて、これらが００の場合にシフト量が０増加され、これらが０１の場合にシフト量が３増加され、これらが１０の場合にシフト量が９増加され、これらが１１の場合にシフト量が０増加される場合を示している。
【００４３】
ここでは、シフトして巡回シフト（ローテイト）を用いるため、シフト量７以上を許容しても、巡回シフト結果値において全ビットが０の値となることはない。例えば図１４（ａ）に対応した処理にて、シフト量が３の場合には巡回シフトにより図１４（ｃ）のようにシフト結果値が得られ、この結果値において最下位（最右）の１ビットを抽出することで、ステップＳ１４におけるビット抽出処理を完了するように構成することもできる。
【００４４】
本発明では、変形テント写像を用いることで写像値の全桁が乱数値として利用可能となるため、写像値ビット桁の抽出位置を任意選択でき、自由度を広く活用できるという特徴がある。こうした特徴を活かす手法として、本実施例では、ビット抽出処理においてシード情報対応の写像関数選択情報を参照することで、ユーザがランダムビット生成パターンを自在に変更可能な機構が提供できるように構成している。
【００４５】
更に、初期値設定で用いるシード情報Ｓｅｅｄと別シード情報をビット抽出処理に利用することで、ユーザはランダムビット列のパターンをバリエーション豊富にすることができる。また、本実施例のように写像関数に与えるシード情報と別シード情報を用いることでもランダムビット列の生成パターンが変更でき、ランダムビット列パターンのバリエーションをより増加することも可能である。
【００４６】
ステップＳ１４におけるビット抽出処理の次に、ＣＰＵ１は、ビット列記録出力処理を行う（Ｓ１５）。ビット列記録出力処理においては、ビット抽出処理において抽出されたビットを先頭側から順にバッファに記憶してビット列を作り、予め定められたタイミングに出力する。具体例としては、バッファが満杯になったときに出力を行う。
【００４７】
例えば、図１５に示すように、バッファＢＵＦのサイズが１バイトであり、第１回目のビット抽出により｛１，０，１｝が、第２回目のビット抽出により｛０，０，１，１，０，０｝が、それぞれ抽出されたとする。この場合には、バッファＢＵＦに、第１回目の抽出ビット｛１，０，１｝が記憶され、次に、第２回目の抽出ビット中の５ビット目までの｛０，０，１，１，０｝が記憶されると、バッファＢＵＦが満杯となる。ここで、出力ビット列｛１，０，１，０，０，１，１，０｝が出力される。出力の後に、バッファＢＵＦはクリアされ、第２回目の抽出ビット中の残余の１ビット｛０｝がバッファＢＵＦに記憶される。以降は、上記と同様に処理が進められる。
【００４８】
上記のような出力ビット列の出力処理に代えて、擬似乱数を使用するシステムから要求を発生させるように構成し、ＣＰＵ１はこのシステムから要求があった場合に出力ビット列の出力を行うようにしても良い。また、ユーザが出力要求を発生させるように構成し、ユーザから要求があった場合に出力ビット列の出力を行うようにしても良い。更に、擬似乱数生成が終了した場合に出力ビット列の出力を行うようにしても良い。いずれの出力タイミングを採用しても良いが、それぞれの場合にバッファＢＵＦの容量を必要な容量とする。
【００４９】
ビット列記録出力処理に続いて、ＣＰＵ１は、パラメータ作成更新処理を行う（Ｓ１６）。パラメータ作成更新処理では、ステップＳ１３の関数切換・写像計算処理を行って得られた写像値Ｘiと上記ステップＳ１１の初期値準備処理において準備してレジスタｍｅｍに記憶した写像初期値Ｘ0との比較結果に基づき、パラメータＰを作成更新する。
【００５０】
具体的には、図１６に示すように、写像計算回数がシード情報Ｓｅｅｄのビット長ｍと同じになったことを検出したときに、レジスタｍｅｍに記憶されている写像初期値Ｘ0と今回において写像計算した写像値Ｘiとを比較し（Ｓ３１）、同じ値かを検出する（Ｓ３２）。
【００５１】
同じ値でないことをステップ３２において検出すると、そのまま通過し、同じ値であることをステップ３２において検出すると、次の関数ｈ（Ｐ，Ｓｅｅｄ）により他のパラメータを作成更新する（Ｓ３３）。
ｈ（Ｐ，Ｓｅｅｄ）＝（Ｐ＋ｒ（Ｓｅｅｄ））ｍｏｄ（２L−１）＋１
上記において、ｒ（Ｓｅｅｄ）は、シード情報Ｓｅｅｄを用いた任意の演算などの数値処理により得られる結果値を示す。
【００５２】
上記ステップＳ１６のパラメータ作成更新処理を終了すると、ＣＰＵ１は終了判定処理Ｓ１７を行う（Ｓ１７）。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長ｎとなったかを検出し、ランダムビット長ｎとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理（Ｓ１２）へ戻って処理を継続する一方、ランダムビット長ｎとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理（Ｓ１５）により出力された出力ビット列が｛ｂ1，ｂ2，ｂ3，・・・，ｂn｝となり所要ビット長の擬似乱数を得ることができる。
【００５３】
次に、第２の実施例を説明する。この第２の実施例に係る擬似乱数生成器においては、図１７に示すように、図１の擬似乱数生成器に備えられていた切換指示手段６０が備えられず、また、写像計算手段２０Ａとパラメータ作成更新手段５０Ａを備える。これ以外は、図１の擬似乱数生成器と同じ構成を有する。
【００５４】
写像計算手段２０Ａは、一つの変形テント関数により写像計算を行うものであり、例えば、図２（ａ）に示された変形テント関数Ｆ１を用いる。このため、テント関数の切り換えを指示する切換指示手段６０が不要である。
【００５５】
パラメータ作成更新手段５０Ａは、写像計算手段２０Ａによる写像計算が行われる毎に当該計算された写像値Ｘiが写像初期値Ｘ0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。この処理は、写像計算手段２０により、シード情報Ｓｅｅｄのビット長ｍと同じｍ回目の写像値Ｘiが計算されたときに、当該計算されたｍ回目の写像値Ｘiが写像初期値Ｘ0と一致しているかを検出し、一致している場合に他のパラメータを作成更新したパラメータ作成更新手段５０と相違している。
【００５６】
以上の通りに構成された第２の実施例に係る擬似乱数生成器は第１の実施例に係る擬似乱数生成器と同様に、例えば、図３に示されるようなコンピュータシステムにより実現される。上記図３に示されたＣＰＵ１が、図１８に示されるフローチャートに対応する擬似乱数生成プログラムＰＲＧを実行することにより図１７の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。
【００５７】
図１８に示されるフローチャートを図４に示されるフローチャートと比較して明らかな通り、図４のステップＳ１３に代えて、図１８ではステップＳ１３Ａとして写像計算処理を行う。また、図４のステップＳ１６に代えて、図１８ではステップＳ１６Ａとしてパラメータ作成更新処理を行う。それ以外の処理は第１の実施例と第２の実施例とは同じ処理を行うため、ステップＳ１３ＡとステップＳ１６Ａのみについて説明を行う。
【００５８】
ステップＳ１３Ａの写像計算処理においては、変形テント関数Ｆ１を用いて次の式により写像計算を行う。
Ｘi＝Ｆ１（Ｘi-1，Ｐ）
Ｆ１は既に式（１）として示されているものである。このようにして、ステップＳ１３Ａの写像計算処理が行われて、写像値Ｘiが得られると、ＣＰＵ１は、既に説明したような、ビット抽出処理（Ｓ１４）、ビット列記録出力処理（Ｓ１５）を行い、ステップＳ１６Ａのパラメータ作成更新処理を行う。
【００５９】
ステップＳ１６Ａのパラメータ作成更新処理においては、図１９に示すように、写像計算が行われたことを検出したときに、レジスタｍｅｍに記憶されている写像初期値Ｘ0と今回において写像計算した写像値Ｘiとを比較し（Ｓ３１Ａ）、同じ値かを検出する（Ｓ３２）。
【００６０】
同じ値でないことをステップ３２において検出すると、そのまま通過し、同じ値であることをステップ３２において検出すると、次の関数ｈ（Ｐ，Ｓｅｅｄ）により他のパラメータを作成更新する（Ｓ３３）。
ｈ（Ｐ，Ｓｅｅｄ）＝（Ｐ＋ｒ（Ｓｅｅｄ））ｍｏｄ（２L−１）＋１
上記において、ｒ（Ｓｅｅｄ）は、シード情報Ｓｅｅｄを用いた任意の演算などの数値処理により得られる結果値を示す。
【００６１】
上記ステップＳ１６Ａのパラメータ作成更新処理を終了すると、ＣＰＵ１は終了判定処理Ｓ１７を行う（Ｓ１７）。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長ｎとなったかを検出し、ランダムビット長ｎとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理（Ｓ１２）へ戻って処理を継続する一方、ランダムビット長ｎとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理（Ｓ１５）により出力された出力ビット列が｛ｂ1，ｂ2，ｂ3，・・・，ｂn｝となり所要ビット長の擬似乱数を得ることができる。
【符号の説明】
【００６２】
１  ＣＰＵ
２  バス
３  主メモリ
４  入力装置
５  出力装置
６  外部記憶装置
１０  初期値準備手段
２０、２０Ａ  写像計算手段
３０  ビット抽出手段
４０  ビット列記憶部
５０、５０Ａ  パラメータ作成更新手段
６０  切換指示手段
７０  制御手段
【先行技術文献】
【特許文献】
【００６３】
【特許文献１】特開２００１−２８５２７７号公報
【特許文献２】特開２００２−２１５０１８号公報
【特許文献３】特表２００５−５２９３６４号公報
【図１】
2010237735.tif 000004
【図２】
2010237735.tif 000005
【図３】
2010237735.tif 000006
【図４】
2010237735.tif 000007
【図５】
2010237735.tif 000008
【図６】
2010237735.tif 000009
【図７】
2010237735.tif 000010
【図８】
2010237735.tif 000011
【図９】
2010237735.tif 000012
【図１０】
2010237735.tif 000013
【図１１】
2010237735.tif 000014
【図１２】
2010237735.tif 000015
【図１３】
2010237735.tif 000016
【図１４】
2010237735.tif 000017
【図１５】
2010237735.tif 000018
【図１６】
2010237735.tif 000019
【図１７】
2010237735.tif 000020
【図１８】
2010237735.tif 000021
【図１９】
2010237735.tif 000022