(57)【特許請求の範囲】
【請求項１】
第１の乱数を生成する擬似乱数生成手段と、
第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には他のすべての記憶要素に記憶される乱数パターンとは異なる乱数パターンがそれぞれ記憶される配列と、
少なくとも選定された第１のアドレスおよび第２のアドレスにより特定される２以上の記憶要素を対象として配列を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する制御手段とを有して構成され、
第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられることを特徴とする擬似乱数生成装置。
【請求項２】
制御手段が、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出し、
第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、前記剰余または前記剰余に基づく演算値として与えられることを特徴とする請求項１記載の擬似乱数生成装置。
【請求項３】
第１のアドレスおよび第３のアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられ、
第２のアドレスが前記剰余または前記剰余に基づく演算値として与えられることを特徴とする請求項２記載の擬似乱数生成装置。
【請求項４】
第１のアドレスおよび第３のアドレスが、前記剰余または前記剰余に基づく演算値として与えられ、
第２のアドレスが第１の乱数または第１の乱数に基づく演算値として与えられることを特徴とする請求項２記載の擬似乱数生成装置。
【請求項５】
擬似乱数生成手段が、線形合同生成器または線形フィードバックシフトレジスタとして与えられることを特徴とする請求項１記載の擬似乱数生成装置。
【請求項６】
第１の乱数を生成する第１の擬似乱数生成手段と、
第３の乱数を生成する第２の擬似乱数生成手段と、
第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には他のすべての記憶要素に記憶される乱数パターンとは異なる乱数パターンがそれぞれ記憶される配列と、
少なくとも選定された第１のアドレスおよび第２のアドレスにより特定される２以上の記憶要素を対象として配列を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する制御手段とを有して構成され、
第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられ、
第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、第３の乱数または第３の乱数に基づく演算値として与えられることを特徴とする擬似乱数生成装置。
【請求項７】
制御手段が、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出し、
第１のアドレスが第３の乱数または第３の乱数に基づく演算値として与えられ、
第２のアドレスが前記剰余または前記剰余に基づく演算値として与えられ、
第３のアドレスが第１の乱数または第１の乱数に基づく演算値として与えられることを特徴とする請求項６記載の擬似乱数生成装置。
【請求項８】
請求項１記載の擬似乱数生成装置を有して構成され、
擬似乱数生成装置から出力される乱数系列と、平文を構成するデータ系列とに対して、ビット毎または所定数のビット列毎に、所定の論理演算を実行して、暗号文を構成するデータ系列を生成することを特徴とする暗号化装置。
【請求項９】
第１の乱数を生成する工程と、
第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出する工程と、
第１のアドレスおよび第２のアドレスを選定する工程と、
第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には他のすべての記憶要素に記憶される乱数パターンとは異なる乱数パターンがそれぞれ記憶される配列において、第１のアドレスにより特定される記憶要素に記憶される数値と第２のアドレスにより特定される記憶要素に記憶される数値とを交換する工程と、
第３のアドレスを選定する工程と、
配列において第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する工程とを有し、
第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数の演算値として与えられ、
第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、前記剰余または前記剰余の演算値として与えられることを特徴とする擬似乱数生成方法。
【請求項１０】
第１の乱数を生成するステップと、
第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出するステップと、
第１のアドレスおよび第２のアドレスを、それぞれ第１の乱数または第１の乱数に基づく演算値あるいは前記剰余または前記剰余に基づく演算値として与えるステップと、
第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には他のすべての記憶要素に記憶される乱数パターンとは異なる乱数パターンがそれぞれ記憶される配列において、第１のアドレスにより特定される記憶要素に記憶される数値と第２のアドレスにより特定される記憶要素に記憶される数値とを交換するステップと、
第３のアドレスを、第１の乱数または第１の乱数に基づく演算値あるいは前記剰余または前記剰余に基づく演算値として与えるステップと、
配列において第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力するステップとを有することを特徴とする擬似乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、擬似乱数生成装置、擬似乱数生成方法および擬似乱数生成プログラム並びに暗号化装置および復号化装置に係り、特に複数の記憶要素から構成されてすべての種類の乱数パターンが記憶される配列を用いて、周期の短い１次乱数から周期の長い２次乱数を生成することができる擬似乱数生成装置、擬似乱数生成方法および擬似乱数生成プログラム並びに当該擬似乱数生成装置を具備する暗号化装置および復号化装置に関する。
【０００２】
ここで、本願明細書において使用する用語について、以下のように定義を行う。乱数パターンとは、所定のビット数を有するビット列を単位として生成される乱数のビットパターンを意味するものとする。乱数値とは、乱数を十進数で表現したものをいう。配列とは、それぞれが固有のアドレスを有する複数の記憶要素の連続的なまたは断続的な集合体をいう。配列は、具体的にはレジスタやＲＡＭ上の所定の記憶領域等として与えられる。
【０００３】
配列の撹拌とは、配列に記憶された数値の組合せを変えることなく、記憶要素に記憶される数値を入れ替えることをいう。例えば、記憶要素Ａ，ＢおよびＣにそれぞれ数値ａ，ｂおよびｃが記憶されているものとする。記憶要素Ａおよび記憶要素Ｂを対象として配列を撹拌する際には、記憶要素Ａに数値ｂを記憶させ、記憶要素Ｂに数値ａを記憶させる。また、記憶要素Ａ，ＢおよびＣを対象として配列を撹拌する際には、記憶要素Ａに数値ｃを記憶させ、記憶要素Ｂに数値ａを記憶させ、記憶要素Ｃに数値ｂを記憶させる。
【０００４】
演算値とは、与えられた１または複数の数値を基にして実行する任意の演算処理の結果として得られる数値を意味するものとする。演算処理の例としては、関数を構成する変数に与えられた数値を代入して関数値を算出する演算処理、所定の規則に基づいて与えられた数値を表すビット列を分割することで１または複数の数値を生成する演算処理、所定の規則に基づいて与えられた複数の数値をそれぞれ表すビット列を結合することで数値を生成する演算処理、ＦＩＦＯ等のバッファに与えられた数値を入力して異なる数値を出力する演算処理、アドレス対応テーブル等のテーブルを参照して与えられた数値に対応する数値を出力する演算処理あるいはこれらの演算処理を任意に組み合わせて実現される演算処理等が挙げられる。
【０００５】
本願発明においては、配列は、擬似乱数生成装置から出力される乱数の乱数パターンの種類数と同数の記憶要素を有する。記憶要素は、乱数の生成単位となるビット数と同数またはそれ以上の記憶容量を有する。配列の撹拌は、少なくとも２つの記憶要素を対象として実行される。配列の撹拌の対象となる２つの記憶要素を特定するための２つのアドレスをそれぞれ第１のアドレスおよび第２のアドレスとする。また、２次乱数を取り出す記憶要素を特定するためのアドレスを第３のアドレスとする。
【背景技術】
【０００６】
現在、使用されている暗号方式は、大きく分けて公開鍵暗号方式と共通鍵暗号方式とに類別される。公開鍵暗号方式では、暗号化に公開鍵または秘密鍵のいずれか一方の鍵が使用され、復号化に他方の鍵が使用される。共通鍵暗号方式では、暗号化および復号化に同一の鍵（共通鍵）を使用する。また、共通鍵暗号方式は、大きく分けてブロック暗号方式とストリーム暗号方式とに類別される。ブロック暗号方式では、平文を所定の大きさのブロックに分割して、ブロック単位に暗号化を実行する。暗号文についても、ブロック毎に当該ブロックを暗号化するのに使用されたキーと同一のキーを使用して、ブロック単位で暗号文を復号化する。ストリーム暗号方式では、暗号化装置側において、例えば共通鍵により与えられる所定の初期状態から逐次的に生成される擬似乱数（キーストリーム）を鍵として平文との間でビット単位にまたは所定数のビット列単位に論理演算（排他的論理和が好適である）を実行して、平文を暗号化する。復号化装置側においても、同一のキーストリームを用いて、暗号文との間でビット単位または所定数のビット列単位に論理演算を実行して、暗号文を復号化する。
【０００７】
共通鍵暗号方式においては、セッション毎に変更されるセッションキーとして、またはキーストリームとして、多くの場合擬似乱数が使用される。特に、ストリーム暗号方式では、擬似乱数として与えられるキーストリームにより平文をそのまま暗号文に暗号化するので、擬似乱数の乱数性が暗号強度に強い影響を及ぼす。擬似乱数を発生させる擬似乱数生成器としては、線形合同生成器や線形フィードバックシフトレジスタ（ＬＦＳＲ：Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  Ｒｅｇｉｓｔｅｒ）等が知られている。
【０００８】
線形合同生成器では、以下のような数式に基づき擬似乱数を生成する。
Ｘｎ＝（ａＸｎ−１＋ｂ）  ｍｏｄ  ｍ          （１）
初期値として与えられるＸ０は、例えば送信側および受信側で共有される共通鍵により与えられる。全状態数がｍであるので、最大周期（最長周期）はｍとなる。この擬似乱数生成方法は、生成アルゴリズムが単純であり、高速に乱数を生成可能であるとともに、統計的にもよい振る舞いを示すことが知られている。
【０００９】
図７は、線形フィードバックシフトレジスタの構成の一例を示す図である。図中のＣ１〜Ｃｎの値は、予め０または１に定められている。ｎ段のシフトレジスタの各段について、Ｃｋ＝１である段の記憶要素に記憶された数値Ｓｉ−ｋの排他的論理和が出力Ｓｉとなる。シフト動作において、この出力Ｓｉがフィードバックされる。この線形フィードバックシフトレジスタの初期状態は、例えば送信側および受信側で共有される共通鍵により与えられる。すべての段に０が記憶された場合には、永続的に０を出力するのみであるので、これは乱数としては使用できない。したがって、線形フィードバックシフトレジスタの最大周期は、２ｎ−１となる。この最大周期をとる乱数系列は、Ｍ系列と呼ばれている。上記のような線形合同生成器や線形フィードバックシフトレジスタ等の擬似乱数生成器に関しては、例えば、「暗号理論入門」（共立出版株式会社、岡本栄司著、１９９３年発行）に記載されている。
【００１０】
【非特許文献１】「暗号理論入門」（共立出版株式会社、岡本栄司著、１９９３年発行）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
上記のような擬似乱数生成器は、乱数生成のアルゴリズムが比較的単純であるとともに周期の比較的短い乱数系列を出力するので、そのまま平文の暗号化に使用すると、暗号文を解読される危険性があるという課題があった。また、複数の線形フィードバックシフトレジスタの出力を非線形コンバイナで結合する手法等が考案されているが、充分な周期を得るためには装置規模が大きくなるという課題があった。
【００１２】
本願発明は、上記課題を解決するために、比較的小さな装置規模で周期の長い乱数系列を生成することができる擬似乱数生成装置、擬似乱数生成方法および擬似乱数生成プログラム並びに当該擬似乱数生成装置を具備する暗号化装置および復号化装置を提供することを目的とする。
【課題を解決するための手段】
【００１３】
乱数は、「０」または「１」の値をとるバイナリビットの集合から成るビット列として与えられる。乱数生成の単位として、例えば２ビットを考える。２ビットとして得られる乱数の乱数パターンは、「００」，「０１」，「１０」，「１１」の４種類である。４つの乱数値から得られる順列は、４！で与えられ、２４パターンとなる。一方、線形合同生成器や線形フィードバックシフトレジスタを用いた乱数生成においては、ある乱数値ｘが出力された次には乱数値ｙが出力され、乱数値ｘが出力された次に乱数値ｙ以外の乱数値が出力されることはない。すなわち、線形合同生成器や線形フィードバックシフトレジスタから出力される乱数系列は循環特性を有している。このような場合に、２ビットを単位として生成される乱数から成る最大周期の乱数系列は８ビット（２ビット＊４パターン）となる。
【００１４】
次に、乱数生成の単位として、コンピュータで扱い易い１バイト（８ビット）を考える。８ビットとして得られる乱数の乱数パターンは、２８＝２５６種類である。２５６個の乱数値から得られる順列は、２５６！で与えられ、約８．６＊１０５０６となり、概ね無限のパターンを得ることができる。一方、線形合同生成器や線形フィードバックシフトレジスタを用いた乱数生成においては、生成される乱数系列が循環特性を有するために、８ビットを単位として生成される乱数から成る最大周期の乱数系列は２０４８ビット（８ビット＊２５６パターン）となる。
【００１５】
上述したように、線形合同生成器や線形フィードバックシフトレジスタから出力されて、循環特性を有する乱数系列の最大周期は大きなものではない。本願発明では、所定のビット数を単位として生成される乱数について、それぞれの乱数パターンに対応する異なる乱数値の集合を基礎として順列により与えられる数値系列が非常に大きなパターン数を有していることに着目する。そこで、乱数パターンの種類数と同数の記憶要素を有する配列を用意する。この配列内のそれぞれの記憶要素に異なる乱数パターンを記憶させることで、配列内で順列としてすべてのパターンの数値系列を表現することができる。
【００１６】
本願発明では、原則的に、所定の規則に基づいて選定される第１のアドレスおよび第２のアドレスにより特定される２つの記憶要素を対象として配列を撹拌する。また、所定の規則に基づいて選定される第３のアドレスにより特定される記憶要素に記憶される数値を擬似乱数生成装置から乱数として出力する。上述したように、異なる乱数値の集合を基礎として順列により与えられる数値系列は概ね無限のパターンを有するから、配列から周期の長い乱数系列を得られる可能性が大きい。本願発明は、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスを、周期の短い第１の乱数または第１の乱数に基づく演算値として与えることで、周期の長い第２の乱数を生成することを意図するものである。
【００１７】
上記の技術的課題を解決するために、本願発明に係る擬似乱数生成装置は、第１の乱数を生成する擬似乱数生成手段と、第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶される配列と、少なくとも選定された第１のアドレスおよび第２のアドレスにより特定される２以上の記憶要素を対象として配列を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する制御手段とを有して構成され、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられるようにしたものである。
【００１８】
また、本願発明に係る擬似乱数生成装置は、制御手段が、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出し、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、前記剰余または前記剰余に基づく演算値として与えられるようにしたものである。
【００１９】
また、本願発明に係る擬似乱数生成装置は、第１のアドレスおよび第３のアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられ、第２のアドレスが前記剰余または前記剰余に基づく演算値として与えられるようにしたものである。
【００２０】
また、本願発明に係る擬似乱数生成装置は、第１のアドレスおよび第３のアドレスが、前記剰余または前記剰余に基づく演算値として与えられ、第２のアドレスが第１の乱数または第１の乱数に基づく演算値として与えられるようにしたものである。
【００２１】
また、本願発明に係る擬似乱数生成装置は、擬似乱数生成手段が、線形合同生成器または線形フィードバックシフトレジスタとして与えられるようにしたものである。
【００２２】
また、本願発明に係る擬似乱数生成装置は、第１の乱数を生成する第１の擬似乱数生成手段と、第３の乱数を生成する第２の擬似乱数生成手段と、第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶される配列と、少なくとも選定された第１のアドレスおよび第２のアドレスにより特定される２以上の記憶要素を対象として配列を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する制御手段とを有して構成され、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられ、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、第３の乱数または第３の乱数に基づく演算値として与えられるようにしたものである。
【００２３】
また、本願発明に係る擬似乱数生成装置は、制御手段が、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出し、第１のアドレスが第３の乱数または第３の乱数に基づく演算値として与えられ、第２のアドレスが前記剰余または前記剰余に基づく演算値として与えられ、第３のアドレスが第１の乱数または第１の乱数に基づく演算値として与えられるようにしたものである。
【００２４】
また、本願発明に係る暗号化装置は、本願発明に係る擬似乱数生成装置を有して構成され、擬似乱数生成装置から出力される乱数系列と、平文を構成するデータ系列とに対して、ビット毎または所定数のビット列毎に、所定の論理演算を実行して、暗号文を構成するデータ系列を生成するようにしたものである。
【００２５】
また、本願発明に係る擬似乱数生成方法は、第１の乱数を生成する工程と、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出する工程と、第１のアドレスおよび第２のアドレスを選定する工程と、第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶される配列において、第１のアドレスにより特定される記憶要素に記憶される数値と第２のアドレスにより特定される記憶要素に記憶される数値とを交換する工程と、第３のアドレスを選定する工程と、配列において第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する工程とを有し、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数の演算値として与えられ、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、前記剰余または前記剰余の演算値として与えられるようにしたものである。
【００２６】
また、本願発明に係る擬似乱数生成プログラムは、第１の乱数を生成するステップと、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出するステップと、  第１のアドレスおよび第２のアドレスを、それぞれ第１の乱数または第１の乱数に基づく演算値あるいは前記剰余または前記剰余に基づく演算値として与えるステップと、第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶される配列において、第１のアドレスにより特定される記憶要素に記憶される数値と第２のアドレスにより特定される記憶要素に記憶される数値とを交換するステップと、第３のアドレスを、第１の乱数または第１の乱数に基づく演算値あるいは前記剰余または前記剰余に基づく演算値として与えるステップと、配列において第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力するステップとを有するようにしたものである。
【発明の効果】
【００２７】
本願発明によれば、第１の乱数を生成する擬似乱数生成手段と、第２の乱数の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶される配列と、少なくとも選定された第１のアドレスおよび第２のアドレスにより特定される２以上の記憶要素を対象として配列を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を第２の乱数として出力する制御手段とを有し、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、第１の乱数または第１の乱数に基づく演算値として与えられるように構成したので、撹拌することにより順列として膨大なパターン数の数値系列を表現するのが可能である配列内の任意の記憶要素から第２の乱数を取り出すことにより、周期の長い乱数系列を得ることができるという効果を奏する。
【００２８】
本願発明によれば、第１の乱数の生成回数を第２の乱数の乱数パターンの種類数で除した剰余を算出し、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、前記剰余または前記剰余に基づく演算値として与えられるように構成したので、配列内のすべての記憶要素のアドレスを均等に選定することが保証されて、配列を全範囲にわたって偏りなく撹拌することが可能となるから、周期の長い乱数系列を得られる可能性を大きくすることができるという効果を奏する。また、カウンタ等の簡単な演算回路を使用しての単純な演算により前記剰余を算出することが可能であるから、擬似乱数生成装置の回路構成を簡略化することができるという効果を奏する。
【００２９】
本願発明によれば、擬似乱数生成手段が線形合同生成器または線形フィードバックシフトレジスタとして与えられるように構成したので、比較的簡単な演算回路を用いて第１の乱数を生成することが可能であるから、擬似乱数生成装置の回路構成を簡略化することができるという効果を奏する。
【００３０】
本願発明によれば、第１の乱数を生成する第１の擬似乱数生成手段と別個に設けられた第２の擬似乱数生成手段を用いて第３の乱数を生成し、第３の乱数を使用して配列を撹拌するように構成したので、第１の乱数の周期の影響を低減して配列の記憶内容を変化させることが可能となるから、撹拌することにより順列として膨大なパターン数の数値系列を表現できる配列をより有効に利用することができて、周期の長い乱数系列を得ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００３１】
最初に、本願発明に係る擬似乱数生成装置の動作原理を簡単なモデルを用いて説明する。図１は、本願発明に係る擬似乱数生成装置の動作原理を説明するためのモデルの構成を示す図である。図１において、１は周期の短い１次乱数Ｒ１を生成する擬似乱数生成器、２は０〜９のアドレスを有する１０個の記憶要素から構成されるレジスタ、３はレジスタ２を撹拌するとともにレジスタ２内のいずれかの記憶要素に記憶された数値を２次乱数Ｒ２として出力する制御部である。
【００３２】
擬似乱数生成器１は、０〜９の数値範囲の数値を乱数として出力する。レジスタ２の１０個の記憶要素には、０〜９の数値が１つずつ記憶される。すなわち、レジスタ２の異なる記憶要素には、同一の数値が記憶されることはない。これにより、レジスタ２内の任意の記憶要素に記憶された数値を２次乱数として取り出せば、２次乱数は０〜９の数値範囲のいずれかの数値をとることになる。
【００３３】
制御部３は、１次乱数Ｒ１の生成回数を計数して、２次乱数の生成順番を示す順序番号Ｉを設定する。制御部３は、式（２）に基づいて、循環順序番号Ｉｍを算出する。
Ｉｍ＝Ｉ  ｍｏｄ  １０          （２）
すなわち、循環順序番号Ｉｍは、順序番号Ｉを１０で除した剰余として与えられ、周期１０で循環する。順序番号Ｉを除する数値１０は、レジスタ２を構成する記憶要素の数と同数である。これにより、擬似乱数生成器１から出力される１次乱数Ｒ１および循環順序番号Ｉｍにより、レジスタ２を構成するすべての記憶要素のアドレスを選定することが可能となる。
【００３４】
【表１】
0004709685.tif 000002
【００３５】
表１は、擬似乱数を生成する過程を示す表である。ここでは、擬似乱数生成器１は、周期が４の乱数系列「０−１−４−３」を逐次的に出力するものとする。また、レジスタ２のアドレスが０から始まるのに対応して、順序番号Ｉも０から始まるものとする。レジスタ２を撹拌する際に対象となる２つの記憶要素を特定するアドレスについては、第１のアドレスが１次乱数Ｒ１として与えられ、第２のアドレスが循環順序番号Ｉｍとして与えられる。表１において、アドレスとして与えられるこれらの数値には斜線が付されている。また、２次乱数Ｒ２を取り出す記憶要素を特定する第３のアドレスは、１次乱数Ｒ１として与えられる。制御部３は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値と循環順序番号Ｉｍをアドレスとする記憶要素に記憶される数値とを交換する。その後、制御部３は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値を２次乱数Ｒ２として出力する。
【００３６】
例として、１次乱数Ｒ１として「０−１−４−３」の乱数系列が３周期生成された後、次の１次乱数Ｒ１として「０」が出力された際の２次乱数Ｒ２の生成について説明する。１次乱数Ｒ１として「０」が出力されると、順序番号Ｉは１増分されるから、Ｉとして１２が設定される。ｍｏｄ（１２，１０）は２となるので、循環順序番号Ｉｍとして２が設定される。前回までのレジスタの撹拌により、レジスタ２において、１次乱数Ｒ１として与えられるアドレス“０”の記憶要素には数値６が記憶され、循環順序番号Ｉｍとして与えられるアドレス“２”の記憶要素には数値４が記憶されている。制御部３は、これらの数値を交換する。すなわち、アドレス“０”の記憶要素には数値４を記憶させ、アドレス“２”の記憶要素には数値６を記憶させる。数値の交換が完了すれば、制御部３は、１次乱数Ｒ１として与えられるアドレス“０”の記憶要素に記憶される数値４を２次乱数Ｒ２として出力する。
【００３７】
表１に示されるように、１５回の乱数生成処理において、０〜９のすべての数値が２次乱数Ｒ２として出力されているとともに、周期は現れない。また、レジスタ２の記憶内容も初期値と全て異なっている。このように、擬似乱数生成器１から出力される周期４の１次乱数「０−１−４−３」を基礎として、周期の長い２次乱数を生成することが可能となる。なお、上記の乱数生成処理においては、レジスタを撹拌した後に２次乱数を取り出す構成としたが、２次乱数を取り出した後にレジスタを撹拌するような構成としてもよい。
【００３８】
以下、添付の図面を参照して本願発明に係る実施の形態を説明する。なお、以下の説明においては、実施の形態の各構成要素と、特許請求の範囲に記載された発明の各構成要素との対応関係を明らかにするために、実施の形態の各構成要素にそれぞれ対応する特許請求の範囲に記載された発明の各構成要素を、以下の説明文中において適宜かっこ書きにより示すものとする。
【００３９】
実施の形態１．
図２は、この発明の実施の形態１による擬似乱数生成装置の構成の一例を示す図である。ここでは、コンピュータで扱い易い１バイト（８ビット）の乱数を出力する擬似乱数生成装置について説明する。８ビットで与えられる乱数は、２５６種類の異なる乱数パターンを有する。図２において、１１は例えば線形合同生成器や線形フィードバックシフトレジスタ等として与えられ比較的周期の短い１次乱数（第１の乱数）Ｒ１を生成する擬似乱数生成器（擬似乱数生成手段）、１２は２次乱数（第２の乱数）Ｒ２の乱数パターンの種類数と同数の記憶要素から構成されてそれぞれの記憶要素には異なる乱数パターンが記憶されるレジスタ（配列）、１３は選定された第１のアドレスおよび第２のアドレスにより特定されるレジスタ１２内の２つの記憶要素を対象としてレジスタ１２を撹拌するとともに選定された第３のアドレスにより特定されるレジスタ１２内の記憶要素に記憶される数値を２次乱数Ｒ２として出力する制御部（制御手段）である。
【００４０】
この実施の形態では、擬似乱数生成器１１として、以下の式（３）に基づいて、０〜２５５の数値範囲の８ビットの乱数パターンを生成する線形合同生成器を採用するものとする。
Ｒｉ＋１＝（３＊Ｒｉ＋１）  ｍｏｄ  ２５６          （３）
生成された乱数Ｒｉを３倍して１を加えた数値を２５６で除した剰余を、新たに生成される乱数Ｒｉ＋１とする。式（３）に基づいて乱数を生成する線形合同生成器は、初期値Ｒ０＝０として乱数を生成すると、周期１２８の乱数系列を出力する。すなわち、この線形合同生成器は、８ビットで表される乱数の２５６種類の乱数パターンのなかで、半分の１２８種類の乱数パターンを出力する。
【００４１】
レジスタ１２としては、０〜２５５の数値範囲のアドレスを有する２５６個の記憶要素から構成されて、それぞれの記憶要素が８ビットの記憶容量を有するレジスタを採用する。制御部１３については、レジスタ１２内の任意の２つの記憶要素に記憶された数値を交換するために、いずれか一方または両方の数値を記憶する記憶部、および乱数の生成回数を計数するカウンタ等を内蔵する構成としてもよい。また、これらの構成要素については、制御部１３に独立に設けることも可能である。
【００４２】
図３は、この発明の実施の形態１による擬似乱数生成方法の一例を示すフローチャートである。擬似乱数生成器１１は、８ビットから成る１次乱数Ｒ１を生成して出力する（ステップ１）。制御部１３は、擬似乱数生成器１１から１次乱数Ｒ１が出力される毎に、順序番号Ｉを１増分する（ステップＳ２）。例えば、制御部１３に内蔵されたカウンタの計数値を順序番号Ｉに対応付けて、１次乱数Ｒ１が出力される毎にカウンタの計数値を１増分することで、当該処理を実現することができる。順序番号Ｉが設定されれば、制御部１３は、以下の式（４）に基づいて、循環順序番号Ｉｍを算出する（ステップＳ３）。
Ｉｍ＝Ｉ  ｍｏｄ  ２５６          （４）
２５６は２次乱数の乱数パターンの種類数を表すものである。これにより、Ｉｍは０〜２５５の数値範囲の数値を順番に与えるので、循環順序番号Ｉｍまたは循環順序番号Ｉｍを基にした演算値により、レジスタ１２内の記憶要素のアドレスを均等に選定することが可能になる。
【００４３】
循環順序番号Ｉｍが設定されれば、制御部１３は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値と循環順序番号Ｉｍをアドレスとする記憶要素に記憶される数値とを交換する（ステップＳ４）。例えば、制御部１３に内蔵される記憶部とレジスタ１２内の記憶要素との間で数値の受け渡しを実行することで、当該処理を実現することができる。レジスタの撹拌が完了すれば、制御部１３は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値を２次乱数Ｒ２として出力する（ステップＳ５）。２次乱数Ｒ２が出力されれば、所定数の乱数系列の出力が完了したか否かを判定する（ステップＳ６）。所定数の乱数系列の出力が完了していなければ、処理をステップＳ１に復帰させて、新たな２次乱数Ｒ２の生成処理を継続する。所定数の乱数系列の出力が完了していれば、乱数生成に係る処理を終了する。
【００４４】
【表２】
0004709685.tif 000003
【００４５】
表２は、実施の形態１による擬似乱数生成装置を用いて得られる乱数系列において出現する乱数パターンの出現傾向を示す表である。表２に示されるように、１次乱数が循環する周期の７倍の回数にわたって２次乱数を生成することで、２次乱数として出現する乱数系列における乱数パターンの種類数が上限の２５６となる。実際に検証してみると、２次乱数が、３２，７６８の周期を有することが判明した。１次乱数の周期が１２８であるから、２次乱数は１次乱数の２５６倍（３２，７６８／１２８＝２５６）の周期を有することになる。
【００４６】
【表３】
0004709685.tif 000004
【００４７】
表３は、実施の形態１による擬似乱数生成装置を用いて得られる乱数系列において出現する各乱数パターンの分布状況を示す表である。表３において、乱数パターン出現平均回数は、２次乱数の乱数パターン毎の出現回数の平均値を示す。乱数パターン出現最小回数は、２次乱数のすべての乱数パターンの出現回数のなかで最小の出現回数を示す。乱数パターン出現最大回数は、２次乱数のすべての乱数パターンの出現回数のなかで最大の出現回数を示す。出現回数最大偏差は、乱数パターン出現平均回数と乱数パターン最小出現回数との差の絶対値および乱数パターン出現平均回数と乱数パターン出現最大回数との差の絶対値について大きい方の数値を乱数パターン出現平均回数で除した数値を示す。出現回数平均偏差は、２次乱数の乱数パターン毎に出現回数と乱数パターン出現平均回数との差の絶対値を乱数パターン出現平均回数で除した数値を累積して得られる数値を乱数パターンの種類数（すなわち２５６）で除した数値を示す。偏差率は、出現回数平均偏差を百分率で表したものである。表３に示されるように、乱数生成回数が大きくなるほど、偏差率が小さくなり各乱数パターンの出現回数が平均化されることが分かる。偏差率が０．０１％であるとは、２５６＊１００００回の乱数生成において、それぞれの乱数パターンが平均して９９９９回〜１０００１回出現することを意味する。
【００４８】
擬似乱数生成器１１としては、式（３）に基づいて乱数生成を実行する線形合同生成器に限定されることがないのは言うまでもない。例えば、以下の式（５）に基づいて、０〜２５５の数値範囲の８ビットの乱数パターンを生成する線形合同生成器を採用してもよい。
Ｒｉ＋１＝３＊Ｒｉ  ｍｏｄ  ２５６          （５）
この線形合同生成器を用いても、乱数生成テストを実行した。式（５）に基づいて１次乱数を生成する線形合同生成器は、周期６４の乱数系列を出力する。この線形合同生成器を擬似乱数生成器１１として採用した擬似乱数生成装置から出力される２次乱数は、６５，５３６の周期を有することが判明した。１次乱数の周期が６４であるから、２次乱数は１次乱数の１，０２４倍（６５，５３６／６４）の周期を有することになる。
【００４９】
上記の実施の形態１においては、配列として与えられるレジスタ１２が２５６個の記憶要素を有するとともに、それぞれの記憶要素が８ビットの記憶容量を有する構成としたが、本願発明はこのような構成に限定されるものではない。例えば、コンピュータが２バイトを単位として動作する場合には、それぞれが２バイトの記憶容量を有する６５５３６個の記憶要素から成るレジスタが用意される。記憶要素がｎビットの記憶容量を有して、記憶要素に記憶された数値を２次乱数として出力する場合には、２次乱数の乱数パターンの種類数は２ｎとなる。したがって、２ｎ個の記憶要素から成るレジスタを用意することで、８ビットの場合と同様に周期の長いｎビットの２次乱数を生成することが可能となる。
【００５０】
上記の実施の形態１においては、１次乱数Ｒ１をアドレスとする記憶要素と循環順序番号Ｉｍをアドレスとする記憶要素とを対象としてレジスタ１２を撹拌し、１次乱数Ｒ１をアドレスとする記憶要素に記憶された数値を２次乱数Ｒ２として出力する構成としたが、本願発明はこのような構成に限定されるものではない。本願発明に係る擬似乱数生成装置においては、撹拌の対象となる２つの記憶要素のアドレス（第１アドレスおよび第２アドレス）および２次乱数を取り出す対象となる記憶要素のアドレス（第３アドレス）を選定する必要がある。撹拌される配列を用いて周期の短い１次乱数から周期の長い２次乱数を生成するという本願発明の趣旨を鑑みれば、第１アドレス、第２アドレスおよび第３アドレスのなかの少なくとも１つのアドレスが、１次乱数または１次乱数に基づく演算値として与えられることは必須の要件となる。１次乱数または１次乱数に基づく演算値として与えられるアドレスの数は１、２または３のいずれでもよい。また、第１のアドレス、第２のアドレスおよび第３のアドレスのいずれについても、１次乱数または１次乱数に基づく演算値として与えられる。例えば、第１のアドレスおよび第３のアドレスが１次乱数として与えられるとともに、第２のアドレスが１次乱数に基づく演算値として与えられる構成としてもよい。
【００５１】
循環順序番号Ｉｍについては、第１アドレス、第２アドレスおよび第３アドレスのなかの少なくとも１つのアドレスが、循環順序番号または循環順序番号に基づく演算値として与えられることは必須の要件ではない。但し、循環順序番号Ｉｍを使用することで、レジスタ１２内のすべての記憶要素のアドレスを均等に選定することができる。すなわち、循環順序番号Ｉｍを使用することで、レジスタ１２を偏りなく撹拌することが可能となる。循環順序番号のこのような特性を鑑みれば、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、循環順序番号または循環順序番号に基づく演算値として与えられるのが好適である。なお、第３のアドレスが、循環順序番号または循環順序番号に基づく演算値として与えられてもよい。
【００５２】
第１のアドレス、第２のアドレスおよび第３のアドレスのなかで、第１の乱数または第１の乱数に基づく演算値あるいは循環順序番号または循環順序番号に基づく演算値として与えられないアドレスについては、所定の規則に基づく他の演算方法を用いて選定する必要がある。
【００５３】
以下では、１次乱数Ｒ１に基づく演算処理について、幾つか説明する。例えば、関数を構成する変数に１次乱数Ｒ１を代入して関数値を算出することで、１次乱数Ｒ１に基づく演算値を算出する。ここで、実施の形態１において、擬似乱数生成器１１が９ビットを単位として１次乱数Ｒ１を生成するような装置構成を考える。１次乱数Ｒ１は０〜５１１の範囲の数値をとるから、１次乱数Ｒ１の乱数パターンの種類数は５１２となる。この場合、例えば式（６）を用いて１次乱数Ｒ１を変換する。
Ｒ１’＝｛Ｒ１−ｍｏｄ（Ｒ１，２）｝／２          （６）
この変換により得られる乱数Ｒ１’は、０から２５５の数値範囲の数値をとるから、この乱数Ｒ１’を用いてレジスタ１２内の記憶要素のアドレスを選定する。
【００５４】
所定の規則に基づいて１次乱数Ｒ１を表すビット列を分割することで、１次乱数Ｒ１に基づく１または複数の演算値を生成するようにしてもよい。例えば１次乱数Ｒ１として４バイト（３２ビット）の乱数パターンが生成される場合には、１次乱数Ｒ１を４分割して、８ビット毎に演算値を生成する。この演算値を用いて、レジスタ１２内の記憶要素のアドレスを選定する。また、１次乱数Ｒ１として１６ビットの乱数パターンが生成される場合には、乱数パターンを分割して前半の８ビットまたは後半の８ビットを演算値とする。この演算値を用いて、レジスタ１２内の記憶要素のアドレスを選定する。
【００５５】
所定の規則に基づいて１次乱数Ｒ１を表すビット列を結合することで、１次乱数Ｒ１に基づく演算値を生成するようにしてもよい。例えば１次乱数Ｒ１として４ビットの乱数パターンが生成される場合には、連続する２つの１次乱数Ｒ１のビットパターンを結合して得られる８ビットのビットパターンを演算値とする。この演算値を用いて、レジスタ１２内の記憶要素のアドレスを選定する。
【００５６】
バッファに１次乱数Ｒ１を入力して、出力として得られる数値を演算値とするようにしてもよい。例えば、擬似乱数生成器１１と制御部１３との間に、ＦＩＦＯを配置する。ＦＩＦＯは、擬似乱数生成器１１から１次乱数Ｒ１を入力して、１次乱数Ｒ１の入力に応じて最も先にＦＩＦＯに入力された数値を演算値として制御部１３に出力する。この演算値を用いて、レジスタ１２内の記憶要素のアドレスを選定する。
【００５７】
アドレス変換テーブル等のテーブルを参照して、１次乱数Ｒ１に対応する数値を演算値とするようにしてもよい。本願発明に係る配列は、上記の実施の形態において使用されるレジスタや、ＲＡＭ上の所定の記憶領域等として与えられる。このような記憶領域に存在する記憶要素のアドレスに対しては、必ずしも０〜２５５の数値範囲の数値が割り当てられるものではない。また、アドレスとして割り当てられる数値は、必ずしも連続する数値として与えられるものでもない。このような場合には、１次乱数Ｒ１が０〜２５５の数値範囲における連続的な数値として与えられるとしても、１次乱数毎に当該１次乱数をレジスタ内の記憶要素のそれぞれ異なるアドレスに対応付ける必要がある。アドレス変換テーブルを用いることにより、１次乱数Ｒ１とレジスタ内の記憶要素のアドレスとを１対１で対応付けることが可能になる。したがって、アドレス変換テーブルを参照して得られた数値を演算値とする。この演算値を用いて、レジスタ１２内の記憶要素のアドレスを選定する。
【００５８】
さらに、１次乱数Ｒ１に係る上記の演算処理を組合わせた演算処理を用いて、一次乱数Ｒ１に基づく演算値を算出する構成としてもよい。例えば、擬似乱数生成器１１と制御部１３との間に、バッファを配置する。擬似乱数生成器１１から出力される１次乱数Ｒ１を変数とする関数値をアドレスとして特定されるバッファ内の記憶要素に記憶される数値を出力する。そして、この記憶要素に１次乱数Ｒ１を記憶させる。
【００５９】
循環順序番号Ｉｍについても、上記の演算処理を適宜適用して演算値を求めることができる。さらに、１次乱数Ｒ１および循環順序番号Ｉｍの両方を基にして演算値を求める構成としてもよい。例えば、１次乱数Ｒ１および循環順序番号Ｉｍを共に変数とする関数ｆ（Ｒ１，Ｉｍ）を定義して、この関数値を演算値として記憶要素のアドレスを選定するようにしてもよい。
【００６０】
上記の実施の形態１においては、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値と循環順序番号Ｉｍをアドレスとする記憶要素に記憶される数値とを交換してレジスタ１２を撹拌した後に、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値を２次乱数Ｒ２として出力する構成としたが、本願発明はこのような構成に限定されるものではない。本願発明に係る擬似乱数生成方法（擬似乱数生成プログラム）においては、選定された第３のアドレスにより特定される記憶要素に記憶される数値を２次乱数Ｒ２として出力した後に、選定された第１のアドレスおよび第２のアドレスにより特定される２つの記憶要素に記憶される数値を対象としてレジスタ１２を撹拌するように構成してもよい。
【００６１】
また、レジスタ１２を撹拌する毎に、２次乱数Ｒ２を出力する構成としているが、本願発明はこのような構成に限定されるものではない。本願発明における擬似乱数生成方法（擬似乱数生成プログラム）においては、レジスタ１２を１回撹拌する毎に、複数の２次乱数Ｒ２を出力する構成としてもよい。また、２次乱数Ｒ２を１回出力する毎に、レジスタ１２を複数回撹拌する構成としてもよい。本願の特許請求の範囲に記載された擬似乱数生成方法および擬似乱数生成プログラムに係る発明を構成する各工程（ステップ）は、必ずしも記載された順に時系列に実行されるものではなく、順序が逆になる場合もあれば、ある工程（ステップ）を１回実行する間に他の工程（ステップ）を複数回実行する場合もあり得る。本願の特許請求の範囲に記載された擬似乱数生成方法および擬似乱数生成プログラムに係る発明の技術的範囲が、上記の種々の実施態様を全て包括するものとして与えられている点に留意されたい。
【００６２】
以上のように、この実施の形態１による擬似乱数生成装置によれば、１次乱数Ｒ１を生成する擬似乱数生成器１１と、２次乱数Ｒ２の乱数パターンの種類数と同数の記憶要素から構成されて、それぞれの記憶要素には異なる乱数パターンが記憶されるレジスタ１２と、選定された第１のアドレスおよび第２のアドレスにより特定される２つの記憶要素を対象としてレジスタ１２を撹拌するとともに、選定された第３のアドレスにより特定される記憶要素に記憶される数値を２次乱数Ｒ２として出力する制御部１３とを有し、第１のアドレス、第２のアドレスおよび第３のアドレスのなかの少なくとも１つのアドレスが、１次乱数Ｒ１または１次乱数Ｒ１に基づく演算値として与えられるように構成したので、撹拌することにより順列として膨大なパターン数の数値系列を表現するのが可能であるレジスタ１２内の任意の記憶要素から２次乱数Ｒ２を取り出すことにより、周期の長い乱数系列を得ることができる。
【００６３】
また、１次乱数Ｒ１の生成回数を２次乱数Ｒ２の乱数パターンの種類数で除した剰余として与えられる循環順序番号Ｉｍを算出し、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスが、循環順序番号Ｉｍまたは循環順序番号Ｉｍに基づく演算値として与えられるように構成したので、循環順序番号Ｉｍを用いることでレジスタ１２内のすべての記憶要素のアドレスを均等に選定することが保証されて、レジスタ１２を全範囲にわたって偏りなく撹拌することが可能となるから、周期の長い乱数系列を得られる可能性が大きくなる。さらに、循環順序番号Ｉｍはカウンタ等の簡単な演算回路を使用しての単純な演算により算出することが可能であるから、擬似乱数生成装置の回路構成を簡略化することができる。
【００６４】
また、１次乱数Ｒ１を生成する擬似乱数生成器１１が線形合同生成器または線形フィードバックシフトレジスタとして与えられるように構成したので、比較的簡単な演算回路を用いて１次乱数Ｒ１を生成することが可能となるから、擬似乱数生成装置の回路構成を簡略化することができる。
【００６５】
実施の形態２．
図４は、この発明の実施の形態２による擬似乱数生成装置の構成の一例を示す図である。図４において、２１は例えば線形合同生成器や線形フィードバックシフトレジスタ等として与えられ比較的周期の短い１次乱数Ｒ１（第１の乱数）を生成する擬似乱数生成器（第１の擬似乱数生成手段）、２２は例えば線形合同生成器や線形フィードバックシフトレジスタ等として与えられ比較的周期の短い撹拌用乱数ＲＳ（第３の乱数）を生成する擬似乱数生成器（第２の擬似乱数制御手段）、２３は２次乱数Ｒ２（第２の乱数）の乱数パターンの種類数と同数の記憶要素から構成されてそれぞれの記憶要素には異なる乱数パターンが記憶されるレジスタ（配列）、２４は選定された第１のアドレスおよび第２のアドレスにより特定されるレジスタ２３内の２つの記憶要素を対象としてレジスタ２３を撹拌するとともに選定された第３のアドレスにより特定されるレジスタ２３内の記憶要素に記憶される数値を２次乱数Ｒ２として出力する制御部（制御手段）である。
【００６６】
この実施の形態２では、擬似乱数生成器２１として、式（５）（Ｒｉ＋１＝３＊Ｒｉ  ｍｏｄ  ２５６）に基づいて０〜２５５の数値範囲の８ビットの乱数パターンを生成する線形合同生成器を採用するものとする。また、擬似乱数生成器２２として、以下の式（７）に基づいて０〜２５５の数値範囲の８ビットの乱数パターンを生成する線形合同生成器を採用するものとする。
Ｒｉ＋１＝（５＊Ｒｉ＋１）ｍｏｄ  ２５６          （７）
さらに、レジスタ２３として、０〜２５５の数値範囲のアドレスを有する２５６個の記憶要素から構成されて、それぞれの記憶要素が８ビットの記憶容量を有するレジスタを採用する。
【００６７】
図５は、この発明の実施の形態２による擬似乱数生成方法の一例を示すフローチャートである。擬似乱数生成器２１は、８ビットの１次乱数Ｒ１を生成して出力する（ステップＳ１１）。擬似乱数生成器２２は、８ビットの撹拌用乱数ＲＳを生成して出力する（ステップＳ１２）。
【００６８】
１次乱数Ｒ１および撹拌用乱数ＲＳが出力されれば、制御部２４は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値と、撹拌用乱数ＲＳをアドレスとする記憶要素に記憶される数値とを交換する（ステップＳ１３）。すなわち、１次乱数Ｒ１を第１のアドレスとするとともに撹拌用乱数ＲＳを第２のアドレスとして、レジスタ２３を撹拌する。レジスタ２３の撹拌が完了すれば、制御部２４は、１次乱数Ｒ１をアドレスとする記憶要素に記憶される数値を２次乱数Ｒ２として出力する（ステップＳ１４）。
【００６９】
２次乱数Ｒ２が出力されれば、所定数の乱数系列の出力が完了したか否かを判定する（ステップＳ１５）。所定数の乱数系列の出力が完了していなければ、処理をステップＳ１１に復帰させて、乱数生成処理を継続する。所定数の乱数系列の出力が完了していれば、乱数生成に係る処理を終了する。
【００７０】
式（５）に基づいて乱数を生成する線形合同生成器は、周期６４の乱数系列を出力する。式（７）に基づいて乱数を生成する線形合同生成器は、周期６４の乱数系列を出力する。擬似乱数生成器２１から出力される１次乱数Ｒ１により与えられる第１のアドレスおよび擬似乱数生成器２２から出力される撹拌用乱数ＲＳにより与えられる第２のアドレスにより特定される２つの記憶要素を対象としてレジスタ２３を撹拌し、擬似乱数生成器２１から出力される１次乱数Ｒ１により与えられる第３のアドレスにより特定される記憶要素に記憶される数値を２次乱数Ｒ２として出力する実施の形態２による擬似乱数生成装置は、４，１９４，０４８の周期を有することが判明した。１次乱数Ｒ１の周期が６４であるから、２次乱数Ｒ２は１次乱数Ｒ１の６５，５３２倍（４，１９４，０４８／６４）の周期を有することになる。
【００７１】
実施の形態１による擬似乱数生成装置について説明したのと同様に、１次乱数または１次乱数に基づく演算値、撹拌用乱数または撹拌用乱数に基づく演算値、あるいは実施の形態１で使用した循環順序番号または循環順序番号に基づく演算値を、第１のアドレス、第２のアドレスおよび第３のアドレスのなかのいずれのアドレスとしても与えることができる。なお、撹拌用乱数ＲＳは、レジスタ２３を撹拌するための乱数として与えられる。この役割を考慮すれば、撹拌用乱数または撹拌用乱数に基づく演算値を、第１のアドレスまたは第２のアドレスの少なくとも一方のアドレスとして与えるのが好適である。
【００７２】
また、１次乱数Ｒ１を生成する毎に、撹拌用乱数ＲＳを生成してレジスタ２３を撹拌する構成としているが、本願発明はこのような構成に限定されるものではない。撹拌用乱数ＲＳの生成を１次乱数Ｒ１の生成よりも先に実行するようにしてもよい。また、撹拌用乱数ＲＳを１回生成する間に１次乱数Ｒ１を複数回生成して、レジスタ２３の撹拌および２次乱数Ｒ２の出力を実行するように構成してもよい。
【００７３】
この実施の形態２による擬似乱数生成装置は、実施の形態１による擬似乱数生成装置と同様の効果を奏するものである。さらに、擬似乱数生成器２２を用いて撹拌用乱数ＲＳを１次乱数Ｒ１とは別個に生成するとともに撹拌用乱数ＲＳを使用してレジスタ２３を撹拌するように構成したので、１次乱数Ｒ１の周期の影響を低減してレジスタ２３の記憶内容を変化させることができるから、撹拌することにより順列として膨大なパターン数の数値系列を表現できるレジスタ２３をより有効に利用することができて、周期の長い乱数系列を得ることができる。
【００７４】
図３および図５に示されるフローチャートに記載された各工程を実行するプログラムコードから成る擬似乱数生成プログラムは、当該擬似乱数生成プログラムが記憶されたＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の情報記憶媒体を入手することで、あるいは当該擬似乱数生成プログラムが格納された外部のサーバからダウンロードすることで利用することができる。情報記憶媒体から読み出されるか、あるいは外部のサーバからダウンロードされた擬似乱数生成プログラムは、例えばパーソナルコンピュータとして与えられる端末装置内の記憶手段にインストールされる。記憶手段にインストールされた擬似乱数生成プログラムを、端末装置内のＣＰＵにより実行することで、実施の形態１および実施の形態２において説明した擬似乱数生成方法を実現することができる。
【００７５】
適用例１．
図６は、本願発明に係る擬似乱数生成装置を適用した暗号システムの構成の一例を示す図である。図６において、３１，３２は本願発明に係る擬似乱数生成装置、３３，３４は論理演算処理装置、３５は通信路である。擬似乱数生成装置３１と擬似乱数生成装置３２とは、同一に構成されるか、あるいは同一の論理構造を有するように構成される。論理演算処理装置３３と論理演算処理装置３４とは、同一に構成されるか、同一の論理構造を有するように構成される。論理演算処理装置３３，３４は、一般的には排他的論理和演算を実行する演算回路として与えられる。この暗号システムにおいて、擬似乱数生成装置３１，３２から出力される乱数系列は、ストリーム暗号を生成するためのキーストリームとして使用される。
【００７６】
擬似乱数生成装置３１と論理演算処理装置３３とを有して構成される暗号化装置では、送信側と受信側とで共有される共通鍵を用いて、擬似乱数生成装置３１を初期状態に設定する。具体的には、１次乱数（および撹拌用乱数）を生成する擬似乱数生成器の初期値を設定するとともにレジスタに初期の記憶内容を設定する。論理演算処理装置３３は、平文を構成するデータ系列と擬似乱数生成装置３１から出力される乱数系列とを入力して、ビット単位または所定数のビット列を単位として所定の論理演算を実行し、暗号文を構成するデータ系列を生成して通信路３５に出力する。
【００７７】
擬似乱数生成装置３２と論理演算処理装置３４とを有して構成される復号化装置では、共通鍵を用いて擬似乱数生成装置３２を初期状態に設定する。論理演算処理装置３４は、暗号文を構成するデータ系列と擬似乱数生成装置３２から出力される乱数系列とを入力して、ビット単位または所定数のビット列を単位として所定の論理演算を実行し、平文を構成するデータ系列を生成する。
【００７８】
なお、上記の実施の形態１および実施の形態２により説明される擬似乱数生成装置等は、本願発明を限定するものではなく、例示することを意図して開示されているものである。本願発明の技術的範囲は特許請求の範囲の記載により定められるものであり、特許請求の範囲に記載された発明の技術的範囲内において種々の設計的変更が可能である。例えば、上記の実施の形態では、第１のアドレスおよび第２のアドレスにより特定される２つの記憶要素を対象としてレジスタを撹拌する構成としているが、３以上の記憶要素を対象としてレジスタを撹拌する構成としてもよい。この場合にも、撹拌の対象となる記憶要素を特定する３以上のアドレスおよび２次乱数を取り出す記憶要素を特定するアドレスのなかの少なくとも１つのアドレスは、１次乱数または１次乱数に基づく演算値により与えられる。さらに、これらのアドレスのなかの少なくとも１つのアドレスが、循環順序番号または循環順序番号に基づく演算値により与えられるのが好適である。
【００７９】
また、本願発明に係る擬似乱数生成装置は、ストリーム暗号システムに適用できるのみではない。例えば、擬似乱数生成装置から出力される乱数系列をセッションキーとして使用することで、本願発明に係る擬似乱数生成装置をブロック暗号システムに適用することができる。さらに、擬似乱数生成装置から出力される乱数系列をモンテカルロシミュレーション用乱数等として使用することで、本願発明に係る擬似乱数生成装置をコンピュータシミュレーションシステムに適用することができる。
【産業上の利用可能性】
【００８０】
本願発明は、ストリーム暗号システム、ブロック暗号システムまたはコンピュータシミュレーションシステム等の種々のシステムで使用される擬似乱数生成装置に広く適用できるものである。
【図面の簡単な説明】
【００８１】
【図１】本願発明に係る擬似乱数生成装置の動作原理を説明するためのモデルの構成を示す図である。
【図２】この発明の実施の形態１による擬似乱数生成装置の構成の一例を示す図である。
【図３】実施の形態１による擬似乱数生成方法の一例を示すフローチャートである。
【図４】この発明の実施の形態２による擬似乱数生成装置の構成の一例を示す図である。
【図５】実施の形態２による擬似乱数生成方法の一例を示すフローチャートである。
【図６】本願発明に係る擬似乱数生成装置を適用した暗号システムの構成の一例を示す図である。
【図７】線形フィードバックシフトレジスタの構成の一例を示す図である。
【符号の説明】
【００８２】
１  擬似乱数生成器、２  レジスタ、３  制御部、１１  擬似乱数生成器（擬似乱数生成手段）、１２  レジスタ（配列）、１３  制御部（制御手段）、２１  擬似乱数生成器（第１の擬似乱数生成手段）、２２  擬似乱数生成器（第２の擬似乱数生成手段）、２３  レジスタ（配列）、２４  制御部（制御手段）、３１，３２  擬似乱数生成装置、３３，３４  論理演算処理装置、３５  通信路
【図１】
0004709685.tif 000005
【図２】
0004709685.tif 000006
【図３】
0004709685.tif 000007
【図４】
0004709685.tif 000008
【図５】
0004709685.tif 000009
【図６】
0004709685.tif 000010
【図７】
0004709685.tif 000011