(57)【特許請求の範囲】
【請求項１】
wビットの整数の列s1，s2，…,snを受け付けて、wビットの乱数の列r1，r2，…,rnを生成する乱数列生成装置であって、
wビットの整数の列s1，s2，…,snを種として受け付ける種受付部、
与えられた整数列x1，x2，…,xnのそれぞれに対して所定の変換を施してwビットの整数の列y1，y2，…,ynを得る変換部、
当該受け付けられた整数の列s1，s2，…,snを、整数列x1，x2，…,xnとして前記変換部に与える初期化部、
当該整数の列y1，y2，…,ynをwnビットのビット列と見て所定の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1，z2，…,znを得る回転部、
当該整数の列z1，z2，…,znを整数列x1，x2，…,xnとして前記変換部に与える更新部、
前記変換部における変換ならびに前記回転部における回転が、所定の回数繰り返された場合、最後に得られたz1，z2，…,znを、乱数列r1，r2，…,rnとして出力する出力部
を備え、
前記変換部は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義される写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
（ａ）y1 = g(xn,x1)；yi+1 = g(xi,xi+1)
（ｂ）所定の整数cについて、y1 = g(c,x1)；yi+1 = g(yi,xi+1)
（ｃ）所定の整数cについて、y1 = g(c,x1)；yi+1 = g(xi,xi+1)
のいずれか１つにより、変換を行い、
当該写像h(・)は、
h(a) = a
と定義される
ことを特徴とする乱数列生成装置。
【請求項２】
請求項１に記載の乱数列生成装置であって、
当該写像h(・)は、h(a) = aによる定義にかえて、与えられた値の数値表現の所定のビットをクリアする演算により定義される
ことを特徴とする乱数列生成装置。
【請求項３】
請求項１に記載の乱数列生成装置であって、
当該写像h(a)は、h(a) = aによる定義にかえて、与えられた値の数値表現の所定のビットを反転する演算により定義される
ことを特徴とする乱数列生成装置。
【請求項４】
請求項１に記載の乱数列生成装置であって、
当該写像h(・)は、h(a) = aによる定義にかえて、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される
ことを特徴とする乱数列生成装置。
【請求項５】
請求項１から４のいずれか１項に記載の乱数列生成装置であって、
前記回転部は、当該所定の回転演算として、当該wnビットのビット列を所定のビット数だけ巡回シフトする
ことを特徴とする乱数列生成装置。
【請求項６】
請求項１から４のいずれか１項に記載の乱数列生成装置であって、
前記回転部は、他の乱数をさらに取得し、当該所定の回転演算において、当該整数列y1，y2，…,ynを回転させる回転方向および回転ビット数は、当該他の乱数の値によって決まる
ことを特徴とする乱数列生成装置。
【請求項７】
請求項１から４のいずれか１項に記載の乱数列生成装置であって、
前記回転部は、他の乱数をさらに取得し、当該所定の回転演算は、当該他の乱数が所定の値である場合、当該整数列y1，y2，…,ynを所定のビット数だけある方向に回転し、そうでない場合、これとは逆の方向に回転する
ことを特徴とする乱数列生成装置。
【請求項８】
wビットの整数の列s1，s2，…,snを受け付けて、wビットの乱数の列r1，r2，…,rnを生成する乱数列生成装置にて実行される乱数列生成方法であって、当該乱数列生成装置は、種受付部、変換部、初期化部、回転部、更新部、出力部を備え、
前記種受付部が、wビットの整数の列s1，s2，…,snを種として受け付ける種受付工程、
前記変換部が、与えられた整数列x1，x2，…,xnのそれぞれに対して所定の変換を施してwビットの整数の列y1，y2，…,ynを得る変換工程、
前記初期化部が、当該受け付けられた整数の列s1，s2，…,snを、整数列x1，x2，…,xnとして前記変換部に与える初期化工程、
前記回転部が、当該整数の列y1，y2，…,ynをwnビットのビット列と見て所定の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1，z2，…,znを得る回転工程、
前記更新部が、当該整数の列z1，z2，…,znを整数列x1，x2，…,xnとして前記変換部に与える更新工程、
前記出力部が、前記変換部における変換ならびに前記回転部における回転が、所定の回数繰り返された場合、最後に得られたz1，z2，…,znを、乱数列r1，r2，…,rnとして出力する出力工程
を備え、
前記変換工程では、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義される写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
（ａ）y1 = g(xn,x1)；yi+1 = g(xi,xi+1)
（ｂ）所定の整数cについて、y1 = g(c,x1)；yi+1 = g(yi,xi+1)
（ｃ）所定の整数cについて、y1 = g(c,x1)；yi+1 = g(xi,xi+1)
のいずれか１つにより、変換を行い、
当該写像h(・)は、
h(a) = a
と定義される
ことを特徴とする方法。
【請求項９】
請求項８に記載の乱数列生成方法であって、
当該写像h(・)は、h(a) = aによる定義にかえて、与えられた値の数値表現の所定のビットをクリアする演算により定義される
ことを特徴とする方法。
【請求項１０】
請求項８に記載の乱数列生成装置であって、
当該写像h(a)は、h(a) = aによる定義にかえて、与えられた値の数値表現の所定のビットを反転する演算により定義される
ことを特徴とする方法。
【請求項１１】
請求項８に記載の乱数列生成方法であって、
当該写像h(・)は、h(a) = aによる定義にかえて、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される
ことを特徴とする方法。
【請求項１２】
請求項８から１０のいずれか１項に記載の乱数列生成方法であって、
前記回転部は、当該所定の回転演算として、当該wnビットのビット列を所定のビット数だけ巡回シフトする
ことを特徴とする方法。
【請求項１３】
請求項８から１０のいずれか１項に記載の乱数列生成方法であって、
前記回転工程では、他の乱数をさらに取得し、当該所定の回転演算において、当該整数列y1，y2，…,ynを回転させる回転方向および回転ビット数は、当該他の乱数の値によって決まる
ことを特徴とする乱数列生成方法。
【請求項１４】
請求項８から１０のいずれか１項に記載の乱数列生成方法であって、
前記回転工程では、他の乱数をさらに取得し、当該所定の回転演算は、当該他の乱数が所定の値である場合、当該整数列y1，y2，…,ynを所定のビット数だけある方向に回転し、そうでない場合、これとは逆の方向に回転する
ことを特徴とする方法。
【請求項１５】
コンピュータを、請求項１から７のいずれか１項に記載の乱数列生成装置の各部として機能させることを特徴とするプログラム。
【請求項１６】
コンピュータに、請求項８から１４のいずれか１項に記載の乱数列生成方法を実行させることを特徴とするプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、乱数列生成装置、乱数列生成方法、ならびに、プログラムに関する。
【０００２】
【従来の技術】
従来から、種々の乱数列生成のための技術が提案されている。これらの技術によって得られた乱数は、たとえば、モンテカルロ法による各種の物理現象、化学現象などの模擬実験や、秘密通信のブロック暗号システムにおいて用いられる。
【０００３】
【発明が解決しようとする課題】
さて、このような乱数列の生成技術においては、得られた乱数列に含まれる数値の分布ができるだけ一様であることや、当該数値のコンピュータにおける数値表現の所定のビットのみを見た場合に、当該ビットの「０」と「１」の出現頻度にできるだけ偏りがないことや、乱数列の周期ができるだけ長いことなど、種々の性質を満たすことが望ましい。
【０００４】
本発明は、wビットのn個の整数の列s1，s2，…,snからwビットのn個の整数の列r1，r2，…,rnを生成し、当該整数の列r1，r2，…,rnを乱数列として見た場合、その数値の分布ができるだけ一様であり、その数値のコンピュータにおける数値表現の所定のビットのみを見た場合に、当該ビットの「０」と「１」の出現頻度にできるだけ偏りがなく、その周期ができるだけ長いように、当該整数の列r1，r2，…,rnを生成するのに好適な、乱数列生成装置、乱数列生成方法、ならびに、これらをコンピュータによって実現するためのプログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段】
以上の目的を達成するため、本発明の原理にしたがって、下記の発明を開示する。
【０００６】
本発明の第１の観点に係る乱数生成装置は、wビットの乱数の列を生成し、種受付部と、初期化部と、変換部と、回転部と、更新部と、出力部と、を備え、以下のように構成する。
【０００７】
すなわち、種受付部は、wビットの整数の列s1，s2，…,snを種として受け付ける。
【０００８】
一方、初期化部は、当該受け付けられた整数の列s1，s2，…,snを、整数列x1，x2，…,xnとして変換部に与える。
【０００９】
さらに、変換部は、当該与えられた整数列x1，x2，…,xnのそれぞれに対して所定の変換を施してwビットの整数の列y1，y2，…,ynを得る。
【００１０】
そして、回転部は、当該整数の列y1，y2，…,ynをwnビットのビット列と見て所定の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1，z2，…,znを得る。
【００１１】
一方、更新部は、当該整数の列z1，z2，…,znを整数列x1，x2，…,xnとして変換部に与える。
【００１２】
さらに、出力部は、変換部における変換ならびに回転部における回転が、所定の回数繰り返された場合、最後に得られた整数の列z1，z2，…,znを、乱数列r1，r2，…,rnとして出力する。
【００１３】
また、本発明の乱数列生成装置において、変換部は、写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(xn,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００１４】
また、本発明の乱数列生成装置において、変換部は、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行うように構成することができる。
【００１５】
また、本発明の乱数列生成装置において、変換部は、写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００１６】
また、本発明の乱数列生成装置において、当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義されるように構成することができる。
【００１７】
また、本発明の乱数列生成装置において、当該写像h(・)は、
h(a) = a
と定義されるように構成することができる。
【００１８】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義されるように構成することができる。
【００１９】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義されるように構成することができる。
【００２０】
また、本発明の乱数列生成装置において、当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義されるように構成することができる。
【００２１】
また、本発明の乱数列生成装置において、回転部は、当該所定の回転演算として、当該wnビットのビット列を所定のビット数だけ巡回シフトするように構成することができる。
【００２２】
また、本発明の乱数列生成装置において、回転部は、他の乱数をさらに取得し、当該所定の回転演算は、当該整数列y1，y2，…,ynを回転させる回転方向および回転ビット数は、当該他の乱数の値によって決まるように構成することができる。
【００２３】
また、本発明の乱数列生成装置において、回転部は、他の乱数をさらに取得し、当該所定の回転演算は、当該他の乱数が所定の値である場合、当該整数列y1，y2，…,ynを所定のビット数だけある方向に回転し、そうでない場合、これとは逆の方向に回転するように構成することができる。
【００２４】
本発明の他の観点に係る乱数列生成方法は、wビットの乱数の列を生成し、種受付工程と、初期化工程と、変換工程と、回転工程と、更新工程と、出力工程と、を備え、以下のように構成する。
【００２５】
すなわち、種受付工程では、wビットの整数の列s1，s2，…,snを種として受け付ける。
【００２６】
一方、初期化工程では、当該受け付けられた整数の列s1，s2，…,snを、整数列x1，x2，…,xnとして変換工程に与える。
【００２７】
さらに、変換工程では、当該与えられた整数列x1，x2，…,xnのそれぞれに対して所定の変換を施してwビットの整数の列y1，y2，…,ynを得る。
【００２８】
そして、回転工程では、当該整数の列y1，y2，…,ynをwnビットのビット列と見て所定の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1，z2，…,znを得る。
【００２９】
一方、更新工程では、当該整数の列z1，z2，…,znを整数列x1，x2，…,xnとして変換工程に与える。
【００３０】
さらに、出力工程では、変換工程における変換ならびに回転工程における回転が、所定の回数繰り返された場合、最後に得られた整数の列z1，z2，…,znを、乱数列r1，r2，…,rnとして出力する。
【００３１】
また、本発明の乱数列生成方法において、変換工程では、写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(xn,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００３２】
また、本発明の乱数列生成方法において、変換工程では、所定の整数cと、写像g(・,・)と、を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行うように構成することができる。
【００３３】
また、本発明の乱数列生成方法において、変換工程では、写像g(・,・)を用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行うように構成することができる。
【００３４】
また、本発明の乱数列生成方法において、当該写像g(・,・)は、所定の写像h(・)と所定の整数q (0≦q≦2w-1)により
g(a,b) = 2b2 + h(a)b + q (mod 2w)
と定義されるように構成することができる。
【００３５】
また、本発明の乱数列生成方法において、当該写像h(・)は、
h(a) = a
と定義されるように構成することができる。
【００３６】
また、本発明の乱数列生成方法であって、当該写像h(・)は、与えられた値の数値表現の所定のビットをクリアする演算により定義されるように構成することができる。
【００３７】
また、本発明の乱数列生成方法において、当該写像h(・)は、与えられた値の数値表現の所定のビットを反転する演算により定義されるように構成することができる。
【００３８】
また、本発明の乱数列生成方法において、当該写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義されるように構成することができる。
【００３９】
また、本発明の乱数列生成方法において、回転工程では、当該所定の回転演算として、当該wnビットのビット列を所定のビット数だけ巡回シフトするように構成することができる。
【００４０】
また、本発明の乱数列生成方法において、回転工程では、他の乱数をさらに取得し、当該所定の回転演算は、当該整数列y1，y2，…,ynを回転させる回転方向および回転ビット数は、当該他の乱数の値によって決まるように構成することができる。
【００４１】
また、本発明の乱数列生成方法において、回転工程では、他の乱数をさらに取得し、当該所定の回転演算は、当該他の乱数が所定の値である場合、当該整数列y1，y2，…,ynを所定のビット数だけある方向に回転し、そうでない場合、これとは逆の方向に回転するように構成することができる。
【００４２】
本発明の他の観点に係るプログラムは、コンピュータを、上記の乱数列生成装置として機能させるように構成する。
【００４３】
本発明の他の観点に係るプログラムは、コンピュータに、上記の乱数列生成方法を実行させるように構成する。
【００４４】
これらのプログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記録媒体に記録することができる。
【００４５】
上記プログラムは、当該プログラムが実行されるコンピュータとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記情報記録媒体は、当該コンピュータとは独立して配布・販売することができる。
【００４６】
【発明の実施の形態】
以下に本発明の実施形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本願発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本願発明の範囲に含まれる。
【００４７】
（発明の実施の形態）
以下で説明する本発明の実施形態においては、「wビットの数値表現による乱数」の列を生成するために、有限体上の非線型変換として、所定の写像h(・)と所定の整数q (0≦q≦2w-1)とを用いて
g(a,b) = 2b2 + h(a)b + q (mod 2w)
により定義される写像g(・,・)を用いる。
【００４８】
写像h(・)としては、恒等写像
h(a) = a
を用いることができる。
【００４９】
また、所定のマスク値MASKを利用することにより、与えられた値aの数値表現の所定のビットをクリアする演算
h(a) = a and MASK
や、所定のビットを反転する演算
h(a) = a xor MASK
を採用してもよい。
【００５０】
さらに、最下位の２ビットを値０１に変換する演算
h(a) = (a and (not 3)) or 1
などを採用することができる。
【００５１】
ここで、各演算子は値aの数値表現（整数表現）に対するもので、andはビット積（ビットアンド）、xorはビット排他的和（ビットエクスクルーシブオア）、notはビット反転（ビットノット）、orはビット和（ビットオア）にそれぞれ相当するものである。
【００５２】
したがって、これらの演算は、コンピュータにおいては桁上がりや桁下がりなどをとりたてて考慮せずに、wビットの整数演算として用意されているものをそのまま適用して実現することができる。
【００５３】
またwの値は、当該コンピュータのＣＰＵ（Central Processing Unit）に用意されている機械語のビット幅、もしくは、これよりも小さい幅に対応させることが望ましい。
【００５４】
現在のところ、世界最高速のブロック暗号技術といわれているＲＣ６は、有限体上の非線型変換
f(x) = 2x2 + x (mod 2w)
を用いることによって実現されており、これによって、ある種から生成される乱数列は、これとは異なる種から生成される乱数列とは常に異なるものであり（１対１性）、生成される乱数列の最長周期が2w-1となっている。
【００５５】
本実施形態において採用される写像g(・,・)は、ＲＣ６における有限体上の非線型変換をさらに一般化したものであり、
h(a) = 1；
q = 0
としたg(・,・)を採用した場合には、ＲＣ６と同等の乱数列の生成能力を有する。なお、本発明においては、上記のＲＣ６同等の写像の以外の写像を選択できるため、さまざまなバリエーションの乱数を得ることができる。
【００５６】
また、これ以外の演算や値を選択した場合にも、良好な乱数列が得られることが、実験により実証されている。
【００５７】
図１は、本実施形態に係る乱数生成装置の概要構成を示す模式図である。図２は、本実施形態に係る乱数生成装置において実行させる処理の制御の流れを示すフローチャートである。以下、これらの図を参照して、本実施形態について、詳細に説明する。
【００５８】
乱数列生成装置１０１は、wビットの乱数の列を生成し、種受付部１０２と、初期化部１０３と、変換部１０４と、回転部１０５と、更新部１０６と、出力部１０７と、を備える。
【００５９】
まず、乱数列生成装置１０１の種受付部１０２は、wビットの整数の列s1，s2，…,snを種として受け付ける（ステップＳ２０１）。
【００６０】
典型的には、s1，s2，…,snは、乱数列生成装置が有するＲＡＭ（Random Access Memory）等のメモリに格納されるが、ＣＰＵが有するキャッシュに格納してもよいし、ハードディスク等の読み書き可能な外部記録媒体に一時的に記憶してもよい。
【００６１】
ついで、初期化部１０３は、当該受け付けられたs1，s2，…,snを、整数列x1，x2，…,xnとして変換部１０４に与える（ステップＳ２０２）。
【００６２】
ここで、x1，x2，…,xnも同様に、ＲＡＭ等のメモリに格納される。この場合、初期化部１０３が実行する処理は、s1，s2，…,snに対応するメモリからx1，x2，…,xnに対応するメモリへの値の転送によって実現することができる。
【００６３】
さらに、変換部１０４は、当該与えられた整数列x1，x2，…,xnのそれぞれに対して上記の非線型変換g(・,・)により定義される変換を施してwビットの整数の列y1，y2，…,ynを得る（ステップＳ２０３）。
【００６４】
当該変換としては以下のような漸化式により定義されるものを採用することができる。
【００６５】
（１）整数i (1≦i≦n-1)についての漸化式
y1  = g(xn,x1)；
yi+1 = g(xi,xi+1)
により変換を行う。
【００６６】
（２）所定の整数cを用いて、整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(yi,xi+1)
により変換を行う。
【００６７】
（３）整数i (1≦i≦n-1)についての漸化式
y1  = g(c,x1)；
yi+1 = g(xi,xi+1)
により変換を行う。
【００６８】
これらの計算は、ＣＰＵが有するＡＬＵ（Arithmetic Logic Unit）を用いて実現することができる。y1，y2，…,ynもまた、メモリ等に格納される。
【００６９】
そして、回転部１０５は、当該y1，y2，…,ynをwnビットのビット列と見て所定の回転演算を行って、得られたwnビットのビット列からwビットの整数の列z1，z2，…,znを得る（ステップＳ２０４）。
【００７０】
所定の回転演算としては、以下のようなものを採用することができる。
【００７１】
（１）wnビットのビット列を所定のビット数だけ巡回シフトするもの。図３に、この巡回シフトとして、w=4，n=4であって、y1，y2，…,y4をビッグエンディアンに配列して、１ビット左にシフトする場合の概要構成を示した。
【００７２】
（２）他の乱数をさらに取得して、これによって、回転方向および回転ビット数を決めるもの。たとえば、以下のような態様が考えられる。
（ｉ）得られた乱数が所定の値である場合ある方向に所定のビット数だけ回転し、そうでない場合、これとは逆の方向に所定のビット数だけ回転させる。たとえば、得られた乱数が奇数の場合は左に１ビット、偶数の場合は右に１ビット巡回シフトする。
（ｉｉ）得られた乱数の値のビット数だけ左に巡回シフトする。
（ｉｉｉ）得られた乱数の値を符号付整数と見て、その符号付整数の値だけ左に巡回シフトする（負の場合は、その絶対値分だけ右に巡回シフトすることになる）。
【００７３】
これは、メモリ等に格納されたy1，y2，…,ynを、ＣＰＵにとって自然なビット幅単位で、桁上がり・桁下がりを考慮しつつ、順次巡回シフトすることによって実現することができる。この場合、得られるz1，z2，…,znは、y1，y2，…,ynが格納されていたメモリ内の領域に新たな値として格納されることとなる。
【００７４】
さらに、出力部１０７は、変換部１０４における変換ならびに回転部１０５における回転が、所定の回数繰り返されたか否かを判定する（ステップＳ２０６）。
【００７５】
たとえば、ステップＳ２０１の前において、メモリ内に用意されたカウンタ変数に「所定の回数の値」を代入し、ステップＳ２０５とステップＳ２０６の間において当該カウンタ変数の値を１減じ、ステップＳ２０６においては、当該カウンタ変数の値が０になったか否かを判定することによって、実現することができる。
【００７６】
所定の回数繰り返された場合（ステップＳ２０６；Ｙｅｓ）最後に得られたz1，z2，…,znを、乱数列r1，r2，…,rnとして出力して（ステップＳ２０７）、乱数列の生成を終了する。
【００７７】
一方、所定の回数繰り返されていない場合（ステップＳ２０６；Ｎｏ）、更新部１０６は、当該z1，z2，…,znを整数列x1，x2，…,xnとして変換部１０４に与えて（ステップＳ２０５）、ステップＳ２０３に戻り、変換（ステップＳ２０３）、回転（ステップＳ２０４）の処理を繰り返す。
【００７８】
これは、z1，z2，…,znが格納されているメモリ等内の値を、x1，x2，…,xnが格納されているメモリ等へ転送することによって実現できる。
【００７９】
乱数列生成装置１０１においては、図示しない記憶部が存在し、その記憶部は、s1，s2，…,sn、x1，x2，…,xn、y1，y2，…,yn、z1，z2，…,zn、r1，r2，…,rnなどを異なる領域に、もしくは、値の利用の依存関係を分析することにより、同じ領域に記憶する（たとえば、y1，y2，…,ynとz1，z2，…,zn等。）ような構成をとることができる。また、各部は、上記の共有メモリを用いて互いに計算した値をやりとりするのである。
【００８０】
図４は、本実施形態の乱数列生成装置１０１が実現されるコンピュータの典型的な概要構成を示す模式図である。以下、本図を参照して説明する。
【００８１】
コンピュータ３０１は、ＣＰＵ  ３０２によって制御される。コンピュータ３０１に電源が投入されると、ＣＰＵ  ３０２は、ＲＯＭ（Read Only Memory）３０３に用意されたＩＰＬ（Initial Program Loader）を実行する。
【００８２】
そして、ＩＰＬの実行により、フレキシブルディスクドライブ３０４に装着されたフレキシブルディスクやハードディスク３０５等に記録されたＯＳ（Operating System）がロードされ、ユーザからの各種の指示入力を受け付けることができるようになる。
【００８３】
ユーザは、キーボード３０６やマウス３０７を操作して、コンピュータ３０１に対して各種の指示入力を与える。
【００８４】
これに応じて、ＯＳは、ハードディスク３０５やＣＤ−ＲＯＭ（Compact Disk ROM）ドライブ３０８に装着されたＣＤ−ＲＯＭに記録されたプログラムや各種のデータをＣＰＵ  ３０２に実行させ、実行の過程やその結果をディスプレイ３０９に表示する。
【００８５】
また、ＣＰＵ  ３０２は、一時的な記憶域として、ＲＡＭ  ３１１を利用する。ＲＡＭ  ３１１は、上記のように、計算の途中で利用される各種の数列を記憶するために用いられる。
【００８６】
さらに、ＣＰＵ  ３０２は、プログラムの実行の過程において、ハードディスク３０５に、生成された乱数列などの処理の結果や途中経過などの情報を保存することができる。
【００８７】
なお、本実施形態における演算は、上記のように、きわめて単純なビット演算に還元することができる。したがって、専用の電子回路（加算器、減算器、シフタ、ラッチ等）を組み合わせて乱数列生成装置１０１を構成することができるほか、ＤＳＰ（Digital Signal Processor）やＦＰＧＡ（Field Programmable Gate Array）などのような電子回路の構成状態を可変に変更できる電子素子を利用して、乱数列生成装置１０１を構成することができ、これらの態様も本発明の範囲に含まれる。
【００８８】
（実験の結果）
上記実施形態に係る乱数列生成装置１０１を用いて、以下の諸元で乱数列を生成させた。
W = 32,
n = 32,
g(a,b) = 2b2 + h(a)b
【００８９】
ただし、写像h(・)は、与えられた値の数値表現の最下位２ビットを０１に置換する演算により定義される。
【００９０】
また、変換および回転は、それぞれ１ラウンドごとに１回とした。すなわち、「所定の回数の繰り返し」は１回である。
【００９１】
出力されるのは、全部でwn = 1024ビットの乱数列r1，r2，…，r1024である。
【００９２】
これに対して２００００×８９９９９種類の種を与え、２００００×８９９９９ラウンドだけ乱数列r1，r2，…，r1024を出力させた。
【００９３】
そして、これに対して乱数列のランダム性を検査する標準的なテストであるＦＩＰＳ  １４０−１ならびにＦＩＰＳ  １４０−２のうち、標準セキュリティ規格にあるランダム性検査テストを、１０２４ビットの乱数列の中の各ビット位置毎に適用して、本実施形態の乱数列の性質を検査した。
【００９４】
これらのテストにおいては、各ビット位置から２００００ビットのビット列を取り出し、その２００００ビットのビット列に対して、以下が行われる。
モノビットテスト（monobit test）。所定の位置のビットの値の出現頻度に偏りがないか否かを調べるもの。
ポーカーテスト（poker test）。２００００ビットを５０００個の４ビットパターンに分割し、その４ビットパターンの出現頻度に偏りがないか否かを調べるもの。
ランズテスト（runs test）。乱数列から所定の長さの連を切り出した場合に、当該長さの連の出現頻度に偏りがないか否かを調べるもの。長さとしては１〜６を用いる。
ロングランズテスト（long runs teset）。ランズテストと同様であるが、ＦＩＰＳ  １４０−１の場合は３４以上の連が存在する場合ランダム性が否定され、ＦＩＰＳ  １４０−１の場合は２６以上の連が存在する場合ランダム性が否定される。
【００９５】
実験の結果、ＦＩＰＳ  １４０−１においては、生成された１０２４ビット×８９９９９サンプルの２００００ビット列は、すべて、定められた基準をクリアした。
【００９６】
また、ＦＩＰＳ  １４０−２においては、生成された１０２４ビット×８９９９９サンプルの２００００ビット列の内、９９.９２パーセントのサンプルが、定められた基準をクリアした。
【００９７】
また、本技術をＸＩＬＩＮＸ（登録商標）社のVertex xcv1000（システムゲート数は１００万）のＦＰＧＡに実装したところ、本アルゴリズムの並列性から、25.62Gビット/secのスピードで乱数列を生成させることができた。すなわち、本技術をＦＰＧＡ等のハードウェアに実装すると、高速性の上で多大なメリットを得ることができる。
【００９８】
このようにして、本実施形態によって生成された乱数列は極めて性質が良いものであり、秘密通信の暗号化の分野や物理現象、化学現象などの模擬実験の分野で有用であり、ハードウェア上で高速に良好なランダム性を持つ乱数列を出力するのに極めて有用であることが示された。
【００９９】
【発明の効果】
以上説明したように、本発明によれば、生成される乱数列が乱数列として好ましい性質を有するような乱数列生成装置、乱数列生成方法、ならびに、これらをコンピュータによって実現するためのプログラムを提供することができる。
【図面の簡単な説明】
【図１】  本発明の実施形態に係る乱数列生成装置の概要構成を示す模式図である。
【図２】  本実施形態の乱数列生成装置において実行される乱数列生成処理の制御の流れを示すフローチャートである。
【図３】  本実施形態の乱数列生成装置の回転部において実行される回転演算の様子を示す説明図である。
【図４】  本実施形態の乱数列生成装置が実現される典型的なコンピュータの概要構成を示す模式図である。
【符号の説明】
１０１  乱数列生成装置
１０２  種受付部
１０３  初期化部
１０４  変換部
１０５  回転部
１０６  更新部
１０７  出力部
３０１  コンピュータ
３０２  ＣＰＵ
３０３  ＲＯＭ
３０４  フレキシブルディスクドライブ
３０５  ハードディスク
３０６  キーボード
３０７  マウス
３０８  ＣＤ−ＲＯＭドライブ
３０９  ディスプレイ
３１１  ＲＡＭ
【図１】
0003700002.tif 000002
【図２】
0003700002.tif 000003
【図３】
0003700002.tif 000004
【図４】
0003700002.tif 000005