擬似乱数生成器、擬似乱数生成方法及び擬似乱数生成プログラム
【課題】構成が簡易でありながら内部パラメータの頻繁な変動なしに長周期の擬似乱数を得る。
【解決手段】初期パラメータ及び写像初期値を準備する初期値準備手段10と、前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段20と、前記写像計算手段20により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段30と、前記写像計算手段20により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段20が用いる他のパラメータを作成更新するパラメータ作成更新手段50と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段20による次の計算への進行と、前記ビット抽出手段30と前記パラメータ作成更新手段50による次処理への進行とを制御する制御手段70とを具備する。
【解決手段】初期パラメータ及び写像初期値を準備する初期値準備手段10と、前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段20と、前記写像計算手段20により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段30と、前記写像計算手段20により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段20が用いる他のパラメータを作成更新するパラメータ作成更新手段50と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段20による次の計算への進行と、前記ビット抽出手段30と前記パラメータ作成更新手段50による次処理への進行とを制御する制御手段70とを具備する。
【発明の詳細な説明】
【技術分野】
【0001】
この発明は、変形テント関数を用いて擬似乱数生成を行う擬似乱数生成器、またその擬似乱数生成方法及び擬似乱数生成プログラムに関するものである。
【背景技術】
【0002】
従来のテント型写像を用いた乱数の生成においては、内部パラメータの変動を写像計算の都度に行うことにより軌道の拡散を図っている(特許文献1参照)。しかしながら、この手法によると、内部パラメータの変動処理が写像計算の都度に発生し、処理が複雑化し時間を要するものであった。また、乱数として使用できる部分は写像値の下位側ビットに限られるという問題があった。
【0003】
また、平文を初期値X0としX0を変形テント写像を用いて写像し暗号文Y を生成する一方、復号は逆写像し暗号文Y を平文X0に戻すという暗号化及び復号手法も知られている。この暗号化及び復号においては、鍵A から副鍵ANを複数生成し、写像(N) 毎に異なる副鍵ANを入力することでスライド攻撃に強い暗号方式を提供するものである(特許文献2参照)。この技術は、暗号化と復号を行うものであり、擬似乱数そのものを生成する手法ではなく、生成した擬似乱数により暗号化を行うものではない。
【0004】
更に、変形テント関数を用い、固定演算化したカオスの系から乱数値を抽出するものも知られている。この手法においては、周期の検出機構を設け、周期検出後に副鍵を用いるものである(特許文献3参照)。このものでは、カオスのシステムはどれでもよいとされているが、特に連続系のカオス(微分方程式系)での例が示されており、微分方程式系では一般的に乱数生成に時間がかかる問題がある。また、長い乱数値を抽出する場合には、その分、副鍵が複数個必要となることが予想され、鍵の管理が煩雑になるという問題がある。
【発明の概要】
【発明が解決しようとする課題】
【0005】
本発明は、上記のような擬似乱数生成における問題に鑑みなされたもので、その目的は、構成が簡易でありながら内部パラメータの頻繁な変動なしに長周期の擬似乱数を得ることができ、また、生成が短時間で可能な擬似乱数生成器を提供することである。また、このような擬似乱数の生成を行う擬似乱数生成方法と擬似乱数生成プログラムを提供することを他の目的とする。
【課題を解決するための手段】
【0006】
本発明に係る擬似乱数生成器は、初期パラメータ及び写像初期値を準備する初期値準備手段と、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段とを具備することを特徴とする。
【0007】
本発明に係る擬似乱数生成器では、写像計算手段は、複数のテント関数により写像計算を行うものであり、初期値準備手段は、シード情報を準備するものであり、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする。
【0008】
本発明に係る擬似乱数生成器では、ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【0009】
本発明に係る擬似乱数生成方法は、初期パラメータ及び写像初期値を準備する初期値準備ステップと、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップとを具備することを特徴とする。
【0010】
本発明に係る擬似乱数生成方法は、写像計算ステップでは、複数のテント関数により写像計算を行い、初期値準備ステップでは、シード情報を準備し、前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする。
【0011】
本発明に係る擬似乱数生成方法は、ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【0012】
本発明に係る擬似乱数生成プログラムは、演算により擬似乱数を生成するコンピュータを、初期パラメータ及び写像初期値を準備する初期値準備手段、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段として機能させる特徴とする。
【0013】
本発明に係る擬似乱数生成プログラムでは、コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、コンピュータを初期値準備手段として、シード情報を準備するように機能させ、コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする。
【0014】
本発明に係る擬似乱数生成プログラムでは、コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする。
【発明の効果】
【0015】
本発明によれば、変形テント関数を用いているため、写像計算毎に内部パラメータを変動させる必要がなく乱数生成を高速化することができるばかりでなく、ビット信号が一様にランダム化されており、所定ビットを抽出して擬似乱数を得ることができる。しかも、写像値と写像初期値との比較結果に基づき、写像計算手段が用いる他のパラメータを作成更新するので、パラメータ変更してランダム化された擬似乱数生成を続けることができる。
【0016】
また、本発明によれば、シード情報に基づき写像計算手段が用いるテント関数を切り換えるので、テント関数の切り換えによって生成される擬似乱数のランダム化を図ることが可能である。更に、本発明によれば、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するので、写像計算によりビット信号が一様にランダム化されて写像値について抽出によって更なるランダム化を図ることができる利点がある。
【図面の簡単な説明】
【0017】
【図1】本発明に係る擬似乱数生成器の第1の実施例の構成を示すブロック図。
【図2】本発明に係る擬似乱数生成器の第1の実施例において採用する変形テント関数を示す図。
【図3】本発明に係る擬似乱数生成器を実現するコンピュータの一例を示すブロック図。
【図4】本発明に係る擬似乱数生成器の第1の実施例の動作を説明するためのフローチャート。
【図5】本発明に係る擬似乱数生成器の第1の実施例による初期値準備処理の一例のプログラムを示す図。
【図6】本発明に係る擬似乱数生成器の第1の実施例による関数切換処理の一例のフローチャートを示す図。
【図7】本発明に係る擬似乱数生成器の第1の実施例による関数切換処理の一例のプログラムを示す図。
【図8】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図9】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一動作例を示す図。
【図10】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図11】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一動作例を示す図。
【図12】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図13】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例を示す図。
【図14】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例を示す図。
【図15】本発明に係る擬似乱数生成器の第1の実施例によるビット列記憶処理の一例を示す図。
【図16】本発明に係る擬似乱数生成器の第1の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【図17】本発明に係る擬似乱数生成器の第2の実施例の構成を示すブロック図。
【図18】本発明に係る擬似乱数生成器の第2の実施例の動作を説明するためのフローチャート。
【図19】本発明に係る擬似乱数生成器の第2の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【発明を実施するための形態】
【0018】
以下添付図面を参照して本発明に係る擬似乱数生成器、擬似乱数生成方法及び擬似乱数生成プログラムについて、それぞれの実施例を説明する。各図において、同一の構成要素には同一の符号を付して重複する説明を省略する。第1の実施例に係る擬似乱数生成器は、図1に示されるように、初期値準備手段10、写像計算手段20、ビット抽出手段30、ビット列記憶部40、パラメータ作成更新手段50、切換指示手段60、制御手段70を備える。
【0019】
初期値準備手段10は、シード情報Seed、ランダムビット長n、写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0を準備するものである。シード情報Seedは、mビットの情報であり、例えばユーザによりランダムビット長nと共にキー入力等されるものである。写像関数選択情報k0〜km-1は、切換指示手段60により用いられる情報であり、ここで各ビットkjは、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を、更にmビットに変更した数値列中ビットであって、先頭からj番目のビットを意味する。
【0020】
写像初期値X0は、mビットのシードSeedを用いた任意の演算などの数値処理により得られる結果値を、指定可能な範囲内(1≦X0≦2L−1)に適応選択した値である。例えば、mod (2L−1)+1の計算後の値を採用することができる。また、初期パラメータPは、mビットのシードSeedを用いた任意の演算などの数値処理による得られる結果値を、指定可能な範囲内(1≦X0≦2L−1)に適応選択した値である。例えば、mod (2L−1)+1の計算後の値を採用することができる。上記のLは、写像計算手段20における演算精度がLビットであり、後述する変形テント関数の係数MがM=2Lであることに起因する数値である。そして、(2L−1)は、0〜2Lには整数値(0を含む)が(2L+1)個存在するから、この内の両端の数値である0と2Lとを除いて(2L−1)個となることを意味している。この両端の数値を除く意味は、後に説明する写像関数において、左右いずれかの写像関数の傾きが無限大となる場合を除くためのものである。
【0021】
写像計算手段20は、初回は初期値準備手段10により準備された初期パラメータと写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は初期パラメータ或いは他のパラメータと前回求められた写像値を変形テント関数に適用し写像計算を行うものである。
【0022】
本実施例の写像計算手段20は、複数のテント関数により写像計算を行うものである。ここでは、図2(a)と図2(b)に示す2通りの変形テント関数F1、F2により写像計算を行うものであり、図2(a)の変形テント関数F1による変形テント写像の整数演算化式は次の式(1)に示すようであり、また、図2(b)の変形テント関数F2による変形テント写像の整数演算化式は次の式(2)に示すようである。
【0023】
【数1】
【0024】
切換指示手段60は、シード情報Seedに基づき写像計算手段20が用いるテント関数の切り換えを指示するものである。前述の通り、初期値準備手段10は、シード情報Seedから写像関数選択情報k0〜km-1を得ており、この写像関数選択情報k0〜km-1が「1」か「0」かによって、式(1)と式(2)とのいずれか一方を選択する指示を与える。
【0025】
ビット抽出手段30は、写像計算手段20により得られた写像値から所定ビットを抽出して擬似乱数とするものである。ビット抽出手段30は、シード情報Seedに基づき写像値から所定ビットを抽出する範囲を決定して、抽出を行う。つまり、写像計算手段20により得られた写像値がLビット長であるとき、Lビット長から抽出するビット数qをシード情報Seedに基づき決定し、また、Lビット中のどのビットを抽出してqビットとするかを決定する。抽出したビットは、バッファを備えるビット列記憶部40に記憶する。記憶は、例えばビット列記憶部40の先頭側から記憶する。
【0026】
ビット列記憶部40は、バッファからビット列を出力する機能を備えており、予め定められたタイミングに出力処理を行う。具体例としては、バッファが満杯になったときに出力を行う。この場合には、出力後にバッファをクリアし、バッファが満杯になったときに記憶できずに残ったビットをビット列記憶部40の先頭側から記憶し、以降同じ処理を繰り返す。
【0027】
パラメータ作成更新手段50は、上記写像計算手段20により得られる写像値Xiと上記写像初期値X0との比較結果に基づき、写像計算手段20が用いる他のパラメータを作成更新するものである。写像初期値X0は初期値準備手段10により送られるので、これをレジスタmemに記憶しておき、上記写像計算手段20により、シード情報Seedのビット長mと同じm回目の写像値Xiが計算されたときに、当該計算されたm回目の写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。
【0028】
具体的には、次の関数h(P,Seed)により他のパラメータを作成更新する。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0029】
制御手段70は、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、上記写像計算手段20による次の計算への進行と、上記ビット抽出手段30と上記パラメータ作成更新手段50による次処理への進行とを制御するものである。具体的には、ビット抽出手段30により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせる一方、ランダムビット長nとなっている場合には、各手段による処理を終了させる。
【0030】
以上の通りに構成された擬似乱数生成器は、例えば、図3に示されるようなコンピュータシステムにより実現される。コンピュータシステムは、CPU1がバス2を介して主メモリ3、入力装置4、出力装置5、外部記憶装置6に接続された構成を有し、主メモリ3には擬似乱数生成プログラムPRGが記憶されている。
【0031】
上記のCPU1が、図4に示されるフローチャートに対応する擬似乱数生成プログラムPRGを実行することにより図1の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。ここでは、シード情報Seedとランダムビット長nが例えば入力装置4などの外部により与えられるものとしてあるが、擬似乱数生成プログラムPRGに含まれているようにしても良い。
【0032】
CPU1は、擬似乱数生成プログラムPRGによる動作を開始し、初期値準備処理を行う(S11)。初期値準備処理S11では、シード情報Seedを用いて、写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0を準備する。ここでは、図5に示す処理プログラムのように、シード情報Seedをそのまま写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0として保持し、また、ランダムビット長nも保持する。更に、写像初期値X0は、レジスタmemに保持する一方、写像回数iをリセットして0とする。
【0033】
次に、CPU1は、カウントアップを行う(S12)。このカウントアップは、写像回数iのカウントアップであり、「i←i+1」という処理である。次にCPU1は、関数切換・写像計算処理を行う(S13)。この関数切換・写像計算処理は、切換指示手段60と写像計算手段20による処理であり、詳細には、前段では、図6のフローチャートに示されるように、写像関数選択情報kjを参照し、この写像関数選択情報kjが0であるか1であるかに応じて(S21)、前述の式(1)と式(2)とのいずれか一方を整数演算化式として選択する(S22、S23)。これを処理プログラムとして示すと、図7のように表すことができる。上記処理より後段では、選択した上記整数演算化式により写像値Xiを計算する。
【0034】
次に、CPU1は、ビット抽出処理を行う(S14)。ビット抽出処理では、具体的には、次の3例を挙げることができる。第1例の関数は、
bs〜bs+q=g1(Xi,Xi+1,Seed)と表すことができ、
qは1回の抽出ビット数(任意)を示し、sは抽出した総ビット数を示し、処理後において「s=s+q」となる。g1(Xi,Xi+1,Seed)の具体的内容は図8に示すC言語によるプログラムにより表すことができる。図8の右に、記号の内容を示す。
【0035】
具体例により説明すると、図9に示すように計算された第1回目から第3回目までの写像値Xiを2進数で示すと、X1、X2、X3の右辺のようであり、対応するシード情報対応の写像関数選択情報kjが(k1,k2,k3)=(1,1,0)であるとすると、kjが0の写像値X3をビット反転させて/X3を得る。そして、X1、X2、/X3のそれぞれについて、後に得られた写像値Xi+1(もしくは、/Xi+1)におけるビットが1となっているビット位置に対応して、先に得られた写像値Xi(もしくは、/Xi)のビット値を取り出す。
【0036】
以上の結果、図9において丸にて囲われたビット値が取り出され、バッファにBUFのように、{1,0,1,0,0,1,1,0,0,・・・}が保持される。
【0037】
第2例の関数は、
bi=g2(Xi,Xi+1,Seed)と表すことができ、
g2(Xi,Xi+1,Seed)の具体的内容は図10に示すC言語によるプログラムにより表すことができる。図10の右に、記号の内容を示す。
【0038】
具体例により説明すると、図9と途中までは等しく、図11に示すように計算された第1回目から第3回目までの写像値Xiを2進数で示すと、X1、X2、X3の右辺のようであり、対応するシード情報対応の写像関数選択情報kjが(k1,k2,k3)=(1,1,0)であるとすると、kjが0の写像値X3をビット反転させて/X3を得る。そして、X1、X2、/X3のそれぞれについて、後に得られた写像値Xi+1(もしくは、/Xi+1)におけるビットが1となっているビット位置に対応して、先に得られた写像値Xi(もしくは、/Xi)のビット値を取り出す。
【0039】
以上の結果、図9と同様に図11において丸にて囲われたビット値が取り出されるわけであるが、この後に各写像値単位で、排他的論理和演算を行って、X1に対して1を抽出し、X2に対して0を抽出する。
【0040】
第3例の関数は、
bi=g3(Xi,Seed)と表すことができ、
g3(Xi,Seed)の具体的内容は図12に示すC言語によるプログラムにより表すことができる。図12の右に、記号の内容を示す。
【0041】
具体例により説明すると、図13に示すようにシード情報対応の写像関数選択情報kjが{1,1,0,0,1,1,・・・}であるとすると、1の場合にシフト量が2増加されて{2,4,4,4,6,0(8),・・・}とシフト量が計算される。第i回目の写像値Xiを2進数で示すと、X1={1,0,1,0,0,1,1,0,0}であると、上記計算されたシフト量の右シフトが行われる。kjのシフト量が6であると、シフトX1は{0,0,0,0,0,0,1,0,1}となり、これと1の論理積を作成してビットとする。
【0042】
図14(a)は、写像関数選択情報kjが1の場合にシフト量が2増加される場合を示し、図14(b)は、写像関数選択情報kjでは2ビット(例えば、kjとkj+1)を用いて、これらが00の場合にシフト量が0増加され、これらが01の場合にシフト量が3増加され、これらが10の場合にシフト量が9増加され、これらが11の場合にシフト量が0増加される場合を示している。
【0043】
ここでは、シフトして巡回シフト(ローテイト)を用いるため、シフト量7以上を許容しても、巡回シフト結果値において全ビットが0の値となることはない。例えば図14(a)に対応した処理にて、シフト量が3の場合には巡回シフトにより図14(c)のようにシフト結果値が得られ、この結果値において最下位(最右)の1ビットを抽出することで、ステップS14におけるビット抽出処理を完了するように構成することもできる。
【0044】
本発明では、変形テント写像を用いることで写像値の全桁が乱数値として利用可能となるため、写像値ビット桁の抽出位置を任意選択でき、自由度を広く活用できるという特徴がある。こうした特徴を活かす手法として、本実施例では、ビット抽出処理においてシード情報対応の写像関数選択情報を参照することで、ユーザがランダムビット生成パターンを自在に変更可能な機構が提供できるように構成している。
【0045】
更に、初期値設定で用いるシード情報Seedと別シード情報をビット抽出処理に利用することで、ユーザはランダムビット列のパターンをバリエーション豊富にすることができる。また、本実施例のように写像関数に与えるシード情報と別シード情報を用いることでもランダムビット列の生成パターンが変更でき、ランダムビット列パターンのバリエーションをより増加することも可能である。
【0046】
ステップS14におけるビット抽出処理の次に、CPU1は、ビット列記録出力処理を行う(S15)。ビット列記録出力処理においては、ビット抽出処理において抽出されたビットを先頭側から順にバッファに記憶してビット列を作り、予め定められたタイミングに出力する。具体例としては、バッファが満杯になったときに出力を行う。
【0047】
例えば、図15に示すように、バッファBUFのサイズが1バイトであり、第1回目のビット抽出により{1,0,1}が、第2回目のビット抽出により{0,0,1,1,0,0}が、それぞれ抽出されたとする。この場合には、バッファBUFに、第1回目の抽出ビット{1,0,1}が記憶され、次に、第2回目の抽出ビット中の5ビット目までの{0,0,1,1,0}が記憶されると、バッファBUFが満杯となる。ここで、出力ビット列{1,0,1,0,0,1,1,0}が出力される。出力の後に、バッファBUFはクリアされ、第2回目の抽出ビット中の残余の1ビット{0}がバッファBUFに記憶される。以降は、上記と同様に処理が進められる。
【0048】
上記のような出力ビット列の出力処理に代えて、擬似乱数を使用するシステムから要求を発生させるように構成し、CPU1はこのシステムから要求があった場合に出力ビット列の出力を行うようにしても良い。また、ユーザが出力要求を発生させるように構成し、ユーザから要求があった場合に出力ビット列の出力を行うようにしても良い。更に、擬似乱数生成が終了した場合に出力ビット列の出力を行うようにしても良い。いずれの出力タイミングを採用しても良いが、それぞれの場合にバッファBUFの容量を必要な容量とする。
【0049】
ビット列記録出力処理に続いて、CPU1は、パラメータ作成更新処理を行う(S16)。パラメータ作成更新処理では、ステップS13の関数切換・写像計算処理を行って得られた写像値Xiと上記ステップS11の初期値準備処理において準備してレジスタmemに記憶した写像初期値X0との比較結果に基づき、パラメータPを作成更新する。
【0050】
具体的には、図16に示すように、写像計算回数がシード情報Seedのビット長mと同じになったことを検出したときに、レジスタmemに記憶されている写像初期値X0と今回において写像計算した写像値Xiとを比較し(S31)、同じ値かを検出する(S32)。
【0051】
同じ値でないことをステップ32において検出すると、そのまま通過し、同じ値であることをステップ32において検出すると、次の関数h(P,Seed)により他のパラメータを作成更新する(S33)。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0052】
上記ステップS16のパラメータ作成更新処理を終了すると、CPU1は終了判定処理S17を行う(S17)。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理(S12)へ戻って処理を継続する一方、ランダムビット長nとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理(S15)により出力された出力ビット列が{b1,b2,b3,・・・,bn}となり所要ビット長の擬似乱数を得ることができる。
【0053】
次に、第2の実施例を説明する。この第2の実施例に係る擬似乱数生成器においては、図17に示すように、図1の擬似乱数生成器に備えられていた切換指示手段60が備えられず、また、写像計算手段20Aとパラメータ作成更新手段50Aを備える。これ以外は、図1の擬似乱数生成器と同じ構成を有する。
【0054】
写像計算手段20Aは、一つの変形テント関数により写像計算を行うものであり、例えば、図2(a)に示された変形テント関数F1を用いる。このため、テント関数の切り換えを指示する切換指示手段60が不要である。
【0055】
パラメータ作成更新手段50Aは、写像計算手段20Aによる写像計算が行われる毎に当該計算された写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。この処理は、写像計算手段20により、シード情報Seedのビット長mと同じm回目の写像値Xiが計算されたときに、当該計算されたm回目の写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新したパラメータ作成更新手段50と相違している。
【0056】
以上の通りに構成された第2の実施例に係る擬似乱数生成器は第1の実施例に係る擬似乱数生成器と同様に、例えば、図3に示されるようなコンピュータシステムにより実現される。上記図3に示されたCPU1が、図18に示されるフローチャートに対応する擬似乱数生成プログラムPRGを実行することにより図17の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。
【0057】
図18に示されるフローチャートを図4に示されるフローチャートと比較して明らかな通り、図4のステップS13に代えて、図18ではステップS13Aとして写像計算処理を行う。また、図4のステップS16に代えて、図18ではステップS16Aとしてパラメータ作成更新処理を行う。それ以外の処理は第1の実施例と第2の実施例とは同じ処理を行うため、ステップS13AとステップS16Aのみについて説明を行う。
【0058】
ステップS13Aの写像計算処理においては、変形テント関数F1を用いて次の式により写像計算を行う。
Xi=F1(Xi-1,P)
F1は既に式(1)として示されているものである。このようにして、ステップS13Aの写像計算処理が行われて、写像値Xiが得られると、CPU1は、既に説明したような、ビット抽出処理(S14)、ビット列記録出力処理(S15)を行い、ステップS16Aのパラメータ作成更新処理を行う。
【0059】
ステップS16Aのパラメータ作成更新処理においては、図19に示すように、写像計算が行われたことを検出したときに、レジスタmemに記憶されている写像初期値X0と今回において写像計算した写像値Xiとを比較し(S31A)、同じ値かを検出する(S32)。
【0060】
同じ値でないことをステップ32において検出すると、そのまま通過し、同じ値であることをステップ32において検出すると、次の関数h(P,Seed)により他のパラメータを作成更新する(S33)。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0061】
上記ステップS16Aのパラメータ作成更新処理を終了すると、CPU1は終了判定処理S17を行う(S17)。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理(S12)へ戻って処理を継続する一方、ランダムビット長nとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理(S15)により出力された出力ビット列が{b1,b2,b3,・・・,bn}となり所要ビット長の擬似乱数を得ることができる。
【符号の説明】
【0062】
1 CPU
2 バス
3 主メモリ
4 入力装置
5 出力装置
6 外部記憶装置
10 初期値準備手段
20、20A 写像計算手段
30 ビット抽出手段
40 ビット列記憶部
50、50A パラメータ作成更新手段
60 切換指示手段
70 制御手段
【先行技術文献】
【特許文献】
【0063】
【特許文献1】特開2001−285277号公報
【特許文献2】特開2002−215018号公報
【特許文献3】特表2005−529364号公報
【技術分野】
【0001】
この発明は、変形テント関数を用いて擬似乱数生成を行う擬似乱数生成器、またその擬似乱数生成方法及び擬似乱数生成プログラムに関するものである。
【背景技術】
【0002】
従来のテント型写像を用いた乱数の生成においては、内部パラメータの変動を写像計算の都度に行うことにより軌道の拡散を図っている(特許文献1参照)。しかしながら、この手法によると、内部パラメータの変動処理が写像計算の都度に発生し、処理が複雑化し時間を要するものであった。また、乱数として使用できる部分は写像値の下位側ビットに限られるという問題があった。
【0003】
また、平文を初期値X0としX0を変形テント写像を用いて写像し暗号文Y を生成する一方、復号は逆写像し暗号文Y を平文X0に戻すという暗号化及び復号手法も知られている。この暗号化及び復号においては、鍵A から副鍵ANを複数生成し、写像(N) 毎に異なる副鍵ANを入力することでスライド攻撃に強い暗号方式を提供するものである(特許文献2参照)。この技術は、暗号化と復号を行うものであり、擬似乱数そのものを生成する手法ではなく、生成した擬似乱数により暗号化を行うものではない。
【0004】
更に、変形テント関数を用い、固定演算化したカオスの系から乱数値を抽出するものも知られている。この手法においては、周期の検出機構を設け、周期検出後に副鍵を用いるものである(特許文献3参照)。このものでは、カオスのシステムはどれでもよいとされているが、特に連続系のカオス(微分方程式系)での例が示されており、微分方程式系では一般的に乱数生成に時間がかかる問題がある。また、長い乱数値を抽出する場合には、その分、副鍵が複数個必要となることが予想され、鍵の管理が煩雑になるという問題がある。
【発明の概要】
【発明が解決しようとする課題】
【0005】
本発明は、上記のような擬似乱数生成における問題に鑑みなされたもので、その目的は、構成が簡易でありながら内部パラメータの頻繁な変動なしに長周期の擬似乱数を得ることができ、また、生成が短時間で可能な擬似乱数生成器を提供することである。また、このような擬似乱数の生成を行う擬似乱数生成方法と擬似乱数生成プログラムを提供することを他の目的とする。
【課題を解決するための手段】
【0006】
本発明に係る擬似乱数生成器は、初期パラメータ及び写像初期値を準備する初期値準備手段と、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段とを具備することを特徴とする。
【0007】
本発明に係る擬似乱数生成器では、写像計算手段は、複数のテント関数により写像計算を行うものであり、初期値準備手段は、シード情報を準備するものであり、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする。
【0008】
本発明に係る擬似乱数生成器では、ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【0009】
本発明に係る擬似乱数生成方法は、初期パラメータ及び写像初期値を準備する初期値準備ステップと、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップとを具備することを特徴とする。
【0010】
本発明に係る擬似乱数生成方法は、写像計算ステップでは、複数のテント関数により写像計算を行い、初期値準備ステップでは、シード情報を準備し、前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする。
【0011】
本発明に係る擬似乱数生成方法は、ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする。
【0012】
本発明に係る擬似乱数生成プログラムは、演算により擬似乱数を生成するコンピュータを、初期パラメータ及び写像初期値を準備する初期値準備手段、初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段として機能させる特徴とする。
【0013】
本発明に係る擬似乱数生成プログラムでは、コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、コンピュータを初期値準備手段として、シード情報を準備するように機能させ、コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする。
【0014】
本発明に係る擬似乱数生成プログラムでは、コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする。
【発明の効果】
【0015】
本発明によれば、変形テント関数を用いているため、写像計算毎に内部パラメータを変動させる必要がなく乱数生成を高速化することができるばかりでなく、ビット信号が一様にランダム化されており、所定ビットを抽出して擬似乱数を得ることができる。しかも、写像値と写像初期値との比較結果に基づき、写像計算手段が用いる他のパラメータを作成更新するので、パラメータ変更してランダム化された擬似乱数生成を続けることができる。
【0016】
また、本発明によれば、シード情報に基づき写像計算手段が用いるテント関数を切り換えるので、テント関数の切り換えによって生成される擬似乱数のランダム化を図ることが可能である。更に、本発明によれば、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するので、写像計算によりビット信号が一様にランダム化されて写像値について抽出によって更なるランダム化を図ることができる利点がある。
【図面の簡単な説明】
【0017】
【図1】本発明に係る擬似乱数生成器の第1の実施例の構成を示すブロック図。
【図2】本発明に係る擬似乱数生成器の第1の実施例において採用する変形テント関数を示す図。
【図3】本発明に係る擬似乱数生成器を実現するコンピュータの一例を示すブロック図。
【図4】本発明に係る擬似乱数生成器の第1の実施例の動作を説明するためのフローチャート。
【図5】本発明に係る擬似乱数生成器の第1の実施例による初期値準備処理の一例のプログラムを示す図。
【図6】本発明に係る擬似乱数生成器の第1の実施例による関数切換処理の一例のフローチャートを示す図。
【図7】本発明に係る擬似乱数生成器の第1の実施例による関数切換処理の一例のプログラムを示す図。
【図8】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図9】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一動作例を示す図。
【図10】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図11】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一動作例を示す図。
【図12】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例のプログラムを示す図。
【図13】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例を示す図。
【図14】本発明に係る擬似乱数生成器の第1の実施例によるビット抽出処理の一例を示す図。
【図15】本発明に係る擬似乱数生成器の第1の実施例によるビット列記憶処理の一例を示す図。
【図16】本発明に係る擬似乱数生成器の第1の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【図17】本発明に係る擬似乱数生成器の第2の実施例の構成を示すブロック図。
【図18】本発明に係る擬似乱数生成器の第2の実施例の動作を説明するためのフローチャート。
【図19】本発明に係る擬似乱数生成器の第2の実施例のパラメータ作成変更動作を説明するためのフローチャート。
【発明を実施するための形態】
【0018】
以下添付図面を参照して本発明に係る擬似乱数生成器、擬似乱数生成方法及び擬似乱数生成プログラムについて、それぞれの実施例を説明する。各図において、同一の構成要素には同一の符号を付して重複する説明を省略する。第1の実施例に係る擬似乱数生成器は、図1に示されるように、初期値準備手段10、写像計算手段20、ビット抽出手段30、ビット列記憶部40、パラメータ作成更新手段50、切換指示手段60、制御手段70を備える。
【0019】
初期値準備手段10は、シード情報Seed、ランダムビット長n、写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0を準備するものである。シード情報Seedは、mビットの情報であり、例えばユーザによりランダムビット長nと共にキー入力等されるものである。写像関数選択情報k0〜km-1は、切換指示手段60により用いられる情報であり、ここで各ビットkjは、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を、更にmビットに変更した数値列中ビットであって、先頭からj番目のビットを意味する。
【0020】
写像初期値X0は、mビットのシードSeedを用いた任意の演算などの数値処理により得られる結果値を、指定可能な範囲内(1≦X0≦2L−1)に適応選択した値である。例えば、mod (2L−1)+1の計算後の値を採用することができる。また、初期パラメータPは、mビットのシードSeedを用いた任意の演算などの数値処理による得られる結果値を、指定可能な範囲内(1≦X0≦2L−1)に適応選択した値である。例えば、mod (2L−1)+1の計算後の値を採用することができる。上記のLは、写像計算手段20における演算精度がLビットであり、後述する変形テント関数の係数MがM=2Lであることに起因する数値である。そして、(2L−1)は、0〜2Lには整数値(0を含む)が(2L+1)個存在するから、この内の両端の数値である0と2Lとを除いて(2L−1)個となることを意味している。この両端の数値を除く意味は、後に説明する写像関数において、左右いずれかの写像関数の傾きが無限大となる場合を除くためのものである。
【0021】
写像計算手段20は、初回は初期値準備手段10により準備された初期パラメータと写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は初期パラメータ或いは他のパラメータと前回求められた写像値を変形テント関数に適用し写像計算を行うものである。
【0022】
本実施例の写像計算手段20は、複数のテント関数により写像計算を行うものである。ここでは、図2(a)と図2(b)に示す2通りの変形テント関数F1、F2により写像計算を行うものであり、図2(a)の変形テント関数F1による変形テント写像の整数演算化式は次の式(1)に示すようであり、また、図2(b)の変形テント関数F2による変形テント写像の整数演算化式は次の式(2)に示すようである。
【0023】
【数1】
【0024】
切換指示手段60は、シード情報Seedに基づき写像計算手段20が用いるテント関数の切り換えを指示するものである。前述の通り、初期値準備手段10は、シード情報Seedから写像関数選択情報k0〜km-1を得ており、この写像関数選択情報k0〜km-1が「1」か「0」かによって、式(1)と式(2)とのいずれか一方を選択する指示を与える。
【0025】
ビット抽出手段30は、写像計算手段20により得られた写像値から所定ビットを抽出して擬似乱数とするものである。ビット抽出手段30は、シード情報Seedに基づき写像値から所定ビットを抽出する範囲を決定して、抽出を行う。つまり、写像計算手段20により得られた写像値がLビット長であるとき、Lビット長から抽出するビット数qをシード情報Seedに基づき決定し、また、Lビット中のどのビットを抽出してqビットとするかを決定する。抽出したビットは、バッファを備えるビット列記憶部40に記憶する。記憶は、例えばビット列記憶部40の先頭側から記憶する。
【0026】
ビット列記憶部40は、バッファからビット列を出力する機能を備えており、予め定められたタイミングに出力処理を行う。具体例としては、バッファが満杯になったときに出力を行う。この場合には、出力後にバッファをクリアし、バッファが満杯になったときに記憶できずに残ったビットをビット列記憶部40の先頭側から記憶し、以降同じ処理を繰り返す。
【0027】
パラメータ作成更新手段50は、上記写像計算手段20により得られる写像値Xiと上記写像初期値X0との比較結果に基づき、写像計算手段20が用いる他のパラメータを作成更新するものである。写像初期値X0は初期値準備手段10により送られるので、これをレジスタmemに記憶しておき、上記写像計算手段20により、シード情報Seedのビット長mと同じm回目の写像値Xiが計算されたときに、当該計算されたm回目の写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。
【0028】
具体的には、次の関数h(P,Seed)により他のパラメータを作成更新する。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0029】
制御手段70は、擬似乱数生成の終了条件情報に基づき終了時の判定を行い、上記写像計算手段20による次の計算への進行と、上記ビット抽出手段30と上記パラメータ作成更新手段50による次処理への進行とを制御するものである。具体的には、ビット抽出手段30により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせる一方、ランダムビット長nとなっている場合には、各手段による処理を終了させる。
【0030】
以上の通りに構成された擬似乱数生成器は、例えば、図3に示されるようなコンピュータシステムにより実現される。コンピュータシステムは、CPU1がバス2を介して主メモリ3、入力装置4、出力装置5、外部記憶装置6に接続された構成を有し、主メモリ3には擬似乱数生成プログラムPRGが記憶されている。
【0031】
上記のCPU1が、図4に示されるフローチャートに対応する擬似乱数生成プログラムPRGを実行することにより図1の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。ここでは、シード情報Seedとランダムビット長nが例えば入力装置4などの外部により与えられるものとしてあるが、擬似乱数生成プログラムPRGに含まれているようにしても良い。
【0032】
CPU1は、擬似乱数生成プログラムPRGによる動作を開始し、初期値準備処理を行う(S11)。初期値準備処理S11では、シード情報Seedを用いて、写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0を準備する。ここでは、図5に示す処理プログラムのように、シード情報Seedをそのまま写像関数選択情報k0〜km-1、初期パラメータP及び写像初期値X0として保持し、また、ランダムビット長nも保持する。更に、写像初期値X0は、レジスタmemに保持する一方、写像回数iをリセットして0とする。
【0033】
次に、CPU1は、カウントアップを行う(S12)。このカウントアップは、写像回数iのカウントアップであり、「i←i+1」という処理である。次にCPU1は、関数切換・写像計算処理を行う(S13)。この関数切換・写像計算処理は、切換指示手段60と写像計算手段20による処理であり、詳細には、前段では、図6のフローチャートに示されるように、写像関数選択情報kjを参照し、この写像関数選択情報kjが0であるか1であるかに応じて(S21)、前述の式(1)と式(2)とのいずれか一方を整数演算化式として選択する(S22、S23)。これを処理プログラムとして示すと、図7のように表すことができる。上記処理より後段では、選択した上記整数演算化式により写像値Xiを計算する。
【0034】
次に、CPU1は、ビット抽出処理を行う(S14)。ビット抽出処理では、具体的には、次の3例を挙げることができる。第1例の関数は、
bs〜bs+q=g1(Xi,Xi+1,Seed)と表すことができ、
qは1回の抽出ビット数(任意)を示し、sは抽出した総ビット数を示し、処理後において「s=s+q」となる。g1(Xi,Xi+1,Seed)の具体的内容は図8に示すC言語によるプログラムにより表すことができる。図8の右に、記号の内容を示す。
【0035】
具体例により説明すると、図9に示すように計算された第1回目から第3回目までの写像値Xiを2進数で示すと、X1、X2、X3の右辺のようであり、対応するシード情報対応の写像関数選択情報kjが(k1,k2,k3)=(1,1,0)であるとすると、kjが0の写像値X3をビット反転させて/X3を得る。そして、X1、X2、/X3のそれぞれについて、後に得られた写像値Xi+1(もしくは、/Xi+1)におけるビットが1となっているビット位置に対応して、先に得られた写像値Xi(もしくは、/Xi)のビット値を取り出す。
【0036】
以上の結果、図9において丸にて囲われたビット値が取り出され、バッファにBUFのように、{1,0,1,0,0,1,1,0,0,・・・}が保持される。
【0037】
第2例の関数は、
bi=g2(Xi,Xi+1,Seed)と表すことができ、
g2(Xi,Xi+1,Seed)の具体的内容は図10に示すC言語によるプログラムにより表すことができる。図10の右に、記号の内容を示す。
【0038】
具体例により説明すると、図9と途中までは等しく、図11に示すように計算された第1回目から第3回目までの写像値Xiを2進数で示すと、X1、X2、X3の右辺のようであり、対応するシード情報対応の写像関数選択情報kjが(k1,k2,k3)=(1,1,0)であるとすると、kjが0の写像値X3をビット反転させて/X3を得る。そして、X1、X2、/X3のそれぞれについて、後に得られた写像値Xi+1(もしくは、/Xi+1)におけるビットが1となっているビット位置に対応して、先に得られた写像値Xi(もしくは、/Xi)のビット値を取り出す。
【0039】
以上の結果、図9と同様に図11において丸にて囲われたビット値が取り出されるわけであるが、この後に各写像値単位で、排他的論理和演算を行って、X1に対して1を抽出し、X2に対して0を抽出する。
【0040】
第3例の関数は、
bi=g3(Xi,Seed)と表すことができ、
g3(Xi,Seed)の具体的内容は図12に示すC言語によるプログラムにより表すことができる。図12の右に、記号の内容を示す。
【0041】
具体例により説明すると、図13に示すようにシード情報対応の写像関数選択情報kjが{1,1,0,0,1,1,・・・}であるとすると、1の場合にシフト量が2増加されて{2,4,4,4,6,0(8),・・・}とシフト量が計算される。第i回目の写像値Xiを2進数で示すと、X1={1,0,1,0,0,1,1,0,0}であると、上記計算されたシフト量の右シフトが行われる。kjのシフト量が6であると、シフトX1は{0,0,0,0,0,0,1,0,1}となり、これと1の論理積を作成してビットとする。
【0042】
図14(a)は、写像関数選択情報kjが1の場合にシフト量が2増加される場合を示し、図14(b)は、写像関数選択情報kjでは2ビット(例えば、kjとkj+1)を用いて、これらが00の場合にシフト量が0増加され、これらが01の場合にシフト量が3増加され、これらが10の場合にシフト量が9増加され、これらが11の場合にシフト量が0増加される場合を示している。
【0043】
ここでは、シフトして巡回シフト(ローテイト)を用いるため、シフト量7以上を許容しても、巡回シフト結果値において全ビットが0の値となることはない。例えば図14(a)に対応した処理にて、シフト量が3の場合には巡回シフトにより図14(c)のようにシフト結果値が得られ、この結果値において最下位(最右)の1ビットを抽出することで、ステップS14におけるビット抽出処理を完了するように構成することもできる。
【0044】
本発明では、変形テント写像を用いることで写像値の全桁が乱数値として利用可能となるため、写像値ビット桁の抽出位置を任意選択でき、自由度を広く活用できるという特徴がある。こうした特徴を活かす手法として、本実施例では、ビット抽出処理においてシード情報対応の写像関数選択情報を参照することで、ユーザがランダムビット生成パターンを自在に変更可能な機構が提供できるように構成している。
【0045】
更に、初期値設定で用いるシード情報Seedと別シード情報をビット抽出処理に利用することで、ユーザはランダムビット列のパターンをバリエーション豊富にすることができる。また、本実施例のように写像関数に与えるシード情報と別シード情報を用いることでもランダムビット列の生成パターンが変更でき、ランダムビット列パターンのバリエーションをより増加することも可能である。
【0046】
ステップS14におけるビット抽出処理の次に、CPU1は、ビット列記録出力処理を行う(S15)。ビット列記録出力処理においては、ビット抽出処理において抽出されたビットを先頭側から順にバッファに記憶してビット列を作り、予め定められたタイミングに出力する。具体例としては、バッファが満杯になったときに出力を行う。
【0047】
例えば、図15に示すように、バッファBUFのサイズが1バイトであり、第1回目のビット抽出により{1,0,1}が、第2回目のビット抽出により{0,0,1,1,0,0}が、それぞれ抽出されたとする。この場合には、バッファBUFに、第1回目の抽出ビット{1,0,1}が記憶され、次に、第2回目の抽出ビット中の5ビット目までの{0,0,1,1,0}が記憶されると、バッファBUFが満杯となる。ここで、出力ビット列{1,0,1,0,0,1,1,0}が出力される。出力の後に、バッファBUFはクリアされ、第2回目の抽出ビット中の残余の1ビット{0}がバッファBUFに記憶される。以降は、上記と同様に処理が進められる。
【0048】
上記のような出力ビット列の出力処理に代えて、擬似乱数を使用するシステムから要求を発生させるように構成し、CPU1はこのシステムから要求があった場合に出力ビット列の出力を行うようにしても良い。また、ユーザが出力要求を発生させるように構成し、ユーザから要求があった場合に出力ビット列の出力を行うようにしても良い。更に、擬似乱数生成が終了した場合に出力ビット列の出力を行うようにしても良い。いずれの出力タイミングを採用しても良いが、それぞれの場合にバッファBUFの容量を必要な容量とする。
【0049】
ビット列記録出力処理に続いて、CPU1は、パラメータ作成更新処理を行う(S16)。パラメータ作成更新処理では、ステップS13の関数切換・写像計算処理を行って得られた写像値Xiと上記ステップS11の初期値準備処理において準備してレジスタmemに記憶した写像初期値X0との比較結果に基づき、パラメータPを作成更新する。
【0050】
具体的には、図16に示すように、写像計算回数がシード情報Seedのビット長mと同じになったことを検出したときに、レジスタmemに記憶されている写像初期値X0と今回において写像計算した写像値Xiとを比較し(S31)、同じ値かを検出する(S32)。
【0051】
同じ値でないことをステップ32において検出すると、そのまま通過し、同じ値であることをステップ32において検出すると、次の関数h(P,Seed)により他のパラメータを作成更新する(S33)。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0052】
上記ステップS16のパラメータ作成更新処理を終了すると、CPU1は終了判定処理S17を行う(S17)。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理(S12)へ戻って処理を継続する一方、ランダムビット長nとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理(S15)により出力された出力ビット列が{b1,b2,b3,・・・,bn}となり所要ビット長の擬似乱数を得ることができる。
【0053】
次に、第2の実施例を説明する。この第2の実施例に係る擬似乱数生成器においては、図17に示すように、図1の擬似乱数生成器に備えられていた切換指示手段60が備えられず、また、写像計算手段20Aとパラメータ作成更新手段50Aを備える。これ以外は、図1の擬似乱数生成器と同じ構成を有する。
【0054】
写像計算手段20Aは、一つの変形テント関数により写像計算を行うものであり、例えば、図2(a)に示された変形テント関数F1を用いる。このため、テント関数の切り換えを指示する切換指示手段60が不要である。
【0055】
パラメータ作成更新手段50Aは、写像計算手段20Aによる写像計算が行われる毎に当該計算された写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新する。この処理は、写像計算手段20により、シード情報Seedのビット長mと同じm回目の写像値Xiが計算されたときに、当該計算されたm回目の写像値Xiが写像初期値X0と一致しているかを検出し、一致している場合に他のパラメータを作成更新したパラメータ作成更新手段50と相違している。
【0056】
以上の通りに構成された第2の実施例に係る擬似乱数生成器は第1の実施例に係る擬似乱数生成器と同様に、例えば、図3に示されるようなコンピュータシステムにより実現される。上記図3に示されたCPU1が、図18に示されるフローチャートに対応する擬似乱数生成プログラムPRGを実行することにより図17の各手段が実現されるので、このフローチャートを参照して擬似乱数生成方法の処理を説明する。
【0057】
図18に示されるフローチャートを図4に示されるフローチャートと比較して明らかな通り、図4のステップS13に代えて、図18ではステップS13Aとして写像計算処理を行う。また、図4のステップS16に代えて、図18ではステップS16Aとしてパラメータ作成更新処理を行う。それ以外の処理は第1の実施例と第2の実施例とは同じ処理を行うため、ステップS13AとステップS16Aのみについて説明を行う。
【0058】
ステップS13Aの写像計算処理においては、変形テント関数F1を用いて次の式により写像計算を行う。
Xi=F1(Xi-1,P)
F1は既に式(1)として示されているものである。このようにして、ステップS13Aの写像計算処理が行われて、写像値Xiが得られると、CPU1は、既に説明したような、ビット抽出処理(S14)、ビット列記録出力処理(S15)を行い、ステップS16Aのパラメータ作成更新処理を行う。
【0059】
ステップS16Aのパラメータ作成更新処理においては、図19に示すように、写像計算が行われたことを検出したときに、レジスタmemに記憶されている写像初期値X0と今回において写像計算した写像値Xiとを比較し(S31A)、同じ値かを検出する(S32)。
【0060】
同じ値でないことをステップ32において検出すると、そのまま通過し、同じ値であることをステップ32において検出すると、次の関数h(P,Seed)により他のパラメータを作成更新する(S33)。
h(P,Seed)=(P+r(Seed))mod(2L−1)+1
上記において、r(Seed)は、シード情報Seedを用いた任意の演算などの数値処理により得られる結果値を示す。
【0061】
上記ステップS16Aのパラメータ作成更新処理を終了すると、CPU1は終了判定処理S17を行う(S17)。即ち、ビット抽出処理により抽出されたビットの総ビット数が、予め設定された所望擬似乱数のランダムビット長nとなったかを検出し、ランダムビット長nとなっていなければ、次の写像計算等を行わせるためにカウントアップ処理(S12)へ戻って処理を継続する一方、ランダムビット長nとなっている場合には、処理を終了させる。このようにして、ビット列記録出力処理(S15)により出力された出力ビット列が{b1,b2,b3,・・・,bn}となり所要ビット長の擬似乱数を得ることができる。
【符号の説明】
【0062】
1 CPU
2 バス
3 主メモリ
4 入力装置
5 出力装置
6 外部記憶装置
10 初期値準備手段
20、20A 写像計算手段
30 ビット抽出手段
40 ビット列記憶部
50、50A パラメータ作成更新手段
60 切換指示手段
70 制御手段
【先行技術文献】
【特許文献】
【0063】
【特許文献1】特開2001−285277号公報
【特許文献2】特開2002−215018号公報
【特許文献3】特表2005−529364号公報
【特許請求の範囲】
【請求項1】
初期パラメータ及び写像初期値を準備する初期値準備手段と、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段と
を具備することを特徴とする擬似乱数生成器。
【請求項2】
写像計算手段は、複数のテント関数により写像計算を行うものであり、
初期値準備手段は、シード情報を準備するものであり、
前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする請求項1に記載の擬似乱数生成器。
【請求項3】
ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項2に記載の擬似乱数生成器。
【請求項4】
初期パラメータ及び写像初期値を準備する初期値準備ステップと、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、
前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、
前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップと
を具備することを特徴とする擬似乱数生成方法。
【請求項5】
写像計算ステップでは、複数のテント関数により写像計算を行い、
初期値準備ステップでは、シード情報を準備し、
前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする請求項4に記載の擬似乱数生成方法。
【請求項6】
ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項5に記載の擬似乱数生成方法。
【請求項7】
演算により擬似乱数を生成するコンピュータを、
初期パラメータ及び写像初期値を準備する初期値準備手段、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段
として機能させる特徴とする擬似乱数生成プログラム。
【請求項8】
コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、
コンピュータを初期値準備手段として、シード情報を準備するように機能させ、
コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする請求項7に記載の擬似乱数生成プログラム。
【請求項9】
コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、
コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする請求項7に記載の擬似乱数生成プログラム。
【請求項1】
初期パラメータ及び写像初期値を準備する初期値準備手段と、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段と、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段と、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段と
を具備することを特徴とする擬似乱数生成器。
【請求項2】
写像計算手段は、複数のテント関数により写像計算を行うものであり、
初期値準備手段は、シード情報を準備するものであり、
前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段を具備することを特徴とする請求項1に記載の擬似乱数生成器。
【請求項3】
ビット抽出手段は、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新手段は、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項2に記載の擬似乱数生成器。
【請求項4】
初期パラメータ及び写像初期値を準備する初期値準備ステップと、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算ステップと、
前記写像計算ステップにより得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出ステップと、
前記写像計算ステップにより得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算ステップにおいて用いられる他のパラメータを作成更新するパラメータ作成更新ステップと、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算ステップによる次の計算への進行と、前記ビット抽出ステップと前記パラメータ作成更新ステップによる次処理への進行とを制御する制御ステップと
を具備することを特徴とする擬似乱数生成方法。
【請求項5】
写像計算ステップでは、複数のテント関数により写像計算を行い、
初期値準備ステップでは、シード情報を準備し、
前記シード情報に基づき写像計算ステップが用いるテント関数の切り換えを指示する切換指示ステップを具備することを特徴とする請求項4に記載の擬似乱数生成方法。
【請求項6】
ビット抽出ステップでは、シード情報に基づき写像値から所定ビットを抽出する範囲を決定し、
パラメータ作成更新ステップでは、シード情報に基づきパラメータの作成更新を行うことを特徴とする請求項5に記載の擬似乱数生成方法。
【請求項7】
演算により擬似乱数を生成するコンピュータを、
初期パラメータ及び写像初期値を準備する初期値準備手段、
初回は前記初期パラメータと前記写像初期値を変形テント関数に適用し写像計算を行い、2回目以降は前記初期パラメータ或いは他のパラメータと前回求められた写像値を前記変形テント関数に適用し写像計算を行う写像計算手段、
前記写像計算手段により得られた写像値から所定ビットを抽出して擬似乱数とするビット抽出手段、
前記写像計算手段により得られる写像値と前記写像初期値との比較結果に基づき、前記写像計算手段が用いる他のパラメータを作成更新するパラメータ作成更新手段と、
擬似乱数生成の終了条件情報に基づき終了時の判定を行い、前記写像計算手段による次の計算への進行と、前記ビット抽出手段と前記パラメータ作成更新手段による次処理への進行とを制御する制御手段
として機能させる特徴とする擬似乱数生成プログラム。
【請求項8】
コンピュータを写像計算手段として、複数のテント関数により写像計算を行うように機能させ、
コンピュータを初期値準備手段として、シード情報を準備するように機能させ、
コンピュータを、前記シード情報に基づき写像計算手段が用いるテント関数の切り換えを指示する切換指示手段として機能させることを特徴とする請求項7に記載の擬似乱数生成プログラム。
【請求項9】
コンピュータをビット抽出手段として、シード情報に基づき写像値から所定ビットを抽出する範囲を決定するように機能させ、
コンピュータをパラメータ作成更新手段として、シード情報に基づきパラメータの作成更新を行うように機能させることを特徴とする請求項7に記載の擬似乱数生成プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【公開番号】特開2010−237735(P2010−237735A)
【公開日】平成22年10月21日(2010.10.21)
【国際特許分類】
【出願番号】特願2009−81847(P2009−81847)
【出願日】平成21年3月30日(2009.3.30)
【出願人】(899000057)学校法人日本大学 (650)
【出願人】(391016358)東芝情報システム株式会社 (149)
【Fターム(参考)】
【公開日】平成22年10月21日(2010.10.21)
【国際特許分類】
【出願日】平成21年3月30日(2009.3.30)
【出願人】(899000057)学校法人日本大学 (650)
【出願人】(391016358)東芝情報システム株式会社 (149)
【Fターム(参考)】
[ Back to top ]