(57)【特許請求の範囲】
【請求項１】
乱数生成装置であって、
Ｎ（Ｎは２以上の整数）ビットの２進数列を初期値として受付ける初期値入力部と、
前記Ｎビットの２進数列を［（（Ｎ−１）／ｍ）］＋１桁のｍ（ｍは１以上の整数、［  ］は小数点以下を切り捨て）ビットの整数に変換して、非線形写像関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に対する固定小数点演算を整数の演算による実現に備える初期値変換部と、
前記初期値変換部の出力及び計算精度Ｎビットの「カオス計算器」が（繰り返し）計算するための入力（ａ（ａ０ａ１．．．ａＮ−１））を格納する格納レジスタと、
前記格納レジスタに格納されている［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数を入力とし、関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に対し整数（分割）演算により実行し、２Ｎビットの計算結果ｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）を有する「カオス計算器」と、
前記「カオス計算器」の２Ｎビットの計算結果ｄに対し、上位Ｎビット（ｄ０ｄ１．．．ｄＮ−１）を関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を繰り返し計算するための入力として格納レジスタに格納し、また、２Ｎビットの計算結果ｄの特定のビットの間に論理演算をして得たＮビットの結果を乱数ｒ（ｒ０ｒ１．．．ｒＮ−１）として出力する抽出・撹拌部と、
前記抽出・撹拌部の出力するＮビットの乱数ｒを格納する乱数格納レジスタと、
前記初期値入力部、初期値変換部、「カオス計算器」、抽出・撹拌部による乱数の生成を行わせる乱数生成制御部と、
を備え、
前記入力ａに対する計算結果である２Ｎビットのｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の各ビットが「カオス計算器」の計算過程において、計算によって影響を受けた入力ａ（ａ０ａ１．．．ａＮ−１）のビット数が異なり、ｄが一様分布でない統計的特性を示し、
前記ｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の各ビットがそれぞれ入力ａ（ａ０ａ１．．．ａＮ−１）から影響を受けているビットの数をそれぞれのビットが持つ複雑度とし、
前記入力ａ（ａ０ａ１．．．ａＮ−１）との関連するビット数（複雑度）の異なる２Ｎビットの片寄りのある分布を持つｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）に対し、
前記抽出・撹拌部で行われるｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間の論理演算で生成される乱数ｒｉ（ｉ＝０，１，．．．Ｎ−１）が入力ａ（ａ０ａ１．．．ａＮ−１）から異なる形で影響を受けるビットの数をｒｉが持つ複雑度として、それをｓｒｉであらわし、
前記ｄの特定のビットの間の論理演算はその演算で生成される乱数ｒの各ビットｒｉ（ｉ＝０，１，．．．Ｎ−１）が持つｓｒｉがすべてのｉ値において、最大（ｓｒｉ＝Ｎ、即ち入力ａ（ａ０ａ１．．．ａＮ−１）のすべてのビットから異なる形で影響を受けること）となることを条件し、（ｒを一様分布の乱数にして出力する）撹拌手段を構成することを特徴とする乱数生成装置。
【請求項２】
前記（請求項１）に記載されるすべてのｉ値において、ｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間の論理演算はｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の１対１の論理演算であることを特徴とする請求項１記載の乱数生成装置。
【請求項３】
前記（請求項１及び請求項２）に記載されるすべてのｉ値において、ｓｒｉ＝Ｎとなる条件を満たすｄの特定のビット間即ち、ｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の１対１の論理演算は
0004308293.tif 000012
【請求項４】
乱数生成方法であって、
非線形写像関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に従い、
与えられたＮ（Ｎは２以上の整数）ビットの２進数列を初期値として受け取り、
受け取った前記Ｎビットの初期値を［（（Ｎ−１）／ｍ）］＋１桁のｍ（ｍは１以上の整数、［  ］は小数点以下を切り捨て）ビットの整数に変換して、関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を計算する計算精度Ｎビット、２Ｎビットの計算結果を有する「カオス計算器」に入力し、
前記「カオス計算器」を用いて、Ｎビットの入力（ａ（ａ０ａ１．．．ａＮ−１））に対し、整数演算による固定小数点演算を実行し、２Ｎビットの２進数列ｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）を生成し、
前記「カオス計算器」の計算は２ｍ（ｍは１以上の整数）ビットの計算能力（ここにいう計算能力は整数の加算、乗算、ビットシフト、ビットごとの論理演算などの計算ができることを指す）を有する計算器により、Ｎビットの整数演算を［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数に分割して計算され、
前記「カオス計算器」の２Ｎビットの計算結果ｄに対し、上位Ｎビット（ｄ０ｄ１．．．ｄＮ−１）を関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を繰り返し計算するための入力（ａ）とし、
前記ｄに対し、特定のビットの間に論理演算を行い、Ｎビットの結果を乱数ｒ（ｒ０ｒ１．．．ｒＮ−１）として出力し、
前記入力ａに対する計算結果である２Ｎビットのｄの各ビットが「カオス計算器」の計算過程において、計算によって影響を受けた入力ａのビット数が異なり、一様分布でない統計的な特性を示し、
前記ｄの各ビットがそれぞれ入力ａから影響を受けているビットの数をそれぞれのビットが持つ複雑度とし、
前記入力ａとの関連するビット数（複雑度）の異なる２Ｎビットの片寄りのある統計的分布特性を持つｄに対し、
前記ｄの特定のビットの間の論理演算で生成される乱数ｒの各ビットｒｉ（ｉ＝０，１，．．．Ｎ−１）が入力ａから、異なる形で影響を受けるビットの数をｒｉが持つ複雑度として、それをｓｒｉであらわし、
前記ｄの特定のビットの間の論理演算はその演算で生成される乱数ｒｉが持つｓｒｉがすべてのｉ値において、最大（ｓｒｉ＝Ｎ、即ち入力ａ（ａ０ａ１．．．ａＮ−１）のすべてのビットから異なる形で影響を受けること）となることを条件とし、（ｒを一様分布の乱数にして出力する）撹拌方法を構成することを特徴とする乱数生成方法。
【請求項５】
前記（請求項４）に記載されるすべてのｉ値において、ｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間の論理演算はｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の１対１の論理演算であることを特徴とする請求項４記載の乱数生成方法。
【請求項６】
前記（請求項４及び請求項５）に記載されるすべてのｉ値において、ｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間（即ち、ｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間）の
0004308293.tif 000013
記載の乱数生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、乱数生成装置及びその方法に関する。
【背景技術】
【０００２】  さまざまな応用分野で乱数が役立つ。例えば：シミュレーション、サンプリング、数値解析、コンピュータプログラミング、意思決定、暗号、美術、レクリエーションなど。そのため、多くの乱数生成法が考案された。コンピュータが高速になることにつれ、今までより多くの乱数を消費することになり、乱数生成器に更にこれを応えるように要請する。【０００３】  一方、簡単な構成で複雑な数列を生成することでカオスによる乱数の生成が期待される。フォンノイマン（Ｖｏｎ  Ｎｅｕｍａｎｎ）らが式（１）による乱数生成を提案した以来、式（１）による乱数生成の考察が数多く報告された。【０００４】
【数１】
0004308293.tif 000002
【０００５】
【非特許文献１】  Ｕｌａｍ，Ｓ．Ｍ．ａｎｄ  Ｖｏｎ  Ｎｅｕｍａｎｎ，Ｊ．，‘‘Ｏｎ  Ｃｏｍｂｉｎａｔｉｏｎ  ｏｆ  Ｓｔｏｃａｓｔｉｃ  Ｄｅｔｅｒｍｉｓｔｉｃ  Ｐｒｏｃｅｓｓｅｓ’’，Ｂｕｌｌ．ＡＭＳ．，Ｖｏｌ．５３，ｐ．１１２０（１９４７））この文献で、式（１）による乱数生成が提案された。【０００６】
【非特許文献２】  香田徹・柿本厚志，‘‘擬似乱数とカオス’’，情報処理学会論文誌Ａ，Ｖｏｌ．２７Ｎｏ．３ｐｐ．２８９−２９６（１９８６）。この文献において、式（１）を用いて、閾値を０．５としたときに生成した乱数が良質であることを示したが、一回の写像で１ビットしか出力しないため、生成速度が遅い欠点がある。【０００７】
【非特許文献３】  Ｐｈａｔａｋ，Ｓ．Ｃ．ａｎｄ  Ｒａｏ，Ｓ．Ｓ．，‘‘ｌｏｇｉｓｔｉｃｍａｐ：Ａ  Ｐｏｓｓｉｂｌｅ  Ｒａｎｄｏｍ−ｎｕｍｂｅｒ  ｅｎｅｒａｔｏｒ’’，Ｐｈｙｓ．Ｒｅｖ．Ｅ，Ｖｏｌ．５１  Ｎｏ．４，ｐｐ．３６７０−３６７８（１９９５）。この文献において、式（１）が生成した数列に対し、変換式を用いて、Ｕ字型の分布を持つｘｔの系列を一様分布の数列に変換することができた。しかし、変換された数列に強い相関が存在している。そのため、シフトという手段使って、数列に存在する相関を弱めることができるが、統計的検定に耐えるようにするにはシフト数を大きくする必要があるとの結果を示した。【０００８】
【非特許文献４】  庄野克房，‘‘カオスエンジニアリング’’，シュプリンガーフェアラーリ東京，東京，２００２。この文献は、式（１）を用いて乱数生成を高速にするには固定小数点演算を用いたハードウェア化が有効と述べている。【０００９】
【特許文献５】  特開２００５−２２８１６９この文献は計算精度を拡張して、固定小数点演算による式（１）の計算方法を提案した。【００１０】  以上の代表的な文献を含む今までの式（１）による乱数生成法に存在する共通の問題点は、乱数の周期長、品質（統計的乱数性）と生成速度をすべて（同時に）実用的に満足できるような高いレベルに達することが出来なかった点である。
【発明の開示】
【発明が解決としようとする課題】
【００１１】  本発明は汎用計算器と専用ハードウェアの両方において、式（１）を計算して、乱数の生成速度と生成される乱数の周期長、品質（統計的乱数性）が共に実用的な高いレベルに達するような乱数生成装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】  本発明（請求項１）に係る乱数生成装置はＮ（Ｎは２以上の整数）ビットの２進数列を初期値として受付ける初期値入力部と、前記Ｎビットの２進数列を［（（Ｎ−１）／ｍ）］＋１桁のｍ（ｍは１以上の整数、［  ］は小数点以下を切り捨て）ビットの整数に変換して、非線形写像関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に対する固定小数点演算を整数の演算による実現に備える初期値変換部と、前記初期値変換部の出力及び計算精度Ｎビットの「カオス計算器」が（繰り返し）計算するための入力（ａ（ａ０ａ１．．．ａＮ−１））を格納する格納レジスタと、前記格納レジスタに格納されている［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数を入力とし、関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に対し整数（分割）演算により実行し、２Ｎビットの計算結果ｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）を有する「カオス計算器」と、前記「カオス計算器」の２Ｎビットの計算結果ｄに対し、上位Ｎビット（ｄ０ｄ１．．．ｄＮ−１）を関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を繰り返し計算するための入力として格納レジスタに格納し、また、２Ｎビットの計算結果ｄの特定のビットの間に論理演算をして得たＮビットの結果を乱数ｒ（ｒ０ｒ１．．．ｒＮ−１）として出力する抽出・撹拌部と、前記抽出・撹拌部の出力するＮビットの乱数を格納する乱数格納レジスタと、前記初期値入力部、初期値変換部、「カオス計算器」、抽出・撹拌部による乱数の生成を行わせる乱数生成制御部とを備え、前記入力ａに対する計算結果である２Ｎビットのｄの各ビットが「カオス計算器」の計算過程において、計算によって影響を受けた入力ａのビット数が異なり、ｄが一様分布でない統計的特性を示し、前記ｄの各ビットがそれぞれ入力ａから影響を受けているビットの数をそれぞれのビットが持つ複雑度とし、前記入力ａとの関連するビット数（複雑度）の異なる２Ｎビットの片寄りのある分布を持つｄに対し、前記抽出・撹拌部で行われるｄの特定のビット間の論理演算で生成される乱数ｒｉ（ｉ＝０，１，．．．Ｎ−１）が入力ａから異なる形で影響を受けるビットの数をｒｉが持つ複雑度として、それをｓｒｉであらわし、前記ｄの特定のビットの間の論理演算はその演算で生成される乱数ｒの各ビットｒｉ（ｉ＝０，１，．．．Ｎ−１）か持つｓｒｉがすべてのｉ値において、最大（ｓｒｉ＝Ｎ、即ち入力ａのすべてのビットから異なる形で影響を受けること）となることを条件とする（ｒを一様分布の乱数にして出力する）撹拌手段であることを特徴とする。
【００１３】  本発明（請求項２）に係る請求項１記載の乱数生成装置は前記（請求項１）に記載されるｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間の論理演算はｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の１対１の論理演算であることを特徴とする。
【００１４】  本発明（請求項３）に係る請求項１記載の乱数生成装置は前記（請求項１及び請求項２）に記載されるｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間即ち、ｄｉと
0004308293.tif 000003
ることを特徴とする。
【００１５】  本発明（請求項４）に係る乱数生成方法は、非線形写像関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）に従い、与えられたＮ（Ｎは２以上の整数）ビットの２進数列を初期値として受け取り、受け取った前記Ｎビットの初期値を［（（Ｎ−１）／ｍ）］＋１桁のｍ（ｍは１以上の整数、［  ］は小数点以下を切り捨て）ビットの整数に変換して、関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を計算する計算精度Ｎビット、２Ｎビットの計算結果を有する「カオス計算器」に入力し、前記「カオス計算器」を用いて、Ｎビットの入力（ａ（ａ０ａ１．．．ａＮ−１））に対し、整数演算による固定小数点演算を実行し、２Ｎビットの２進数列ｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）を生成し、前記「カオス計算器」の計算は２ｍ（ｍは１以上の整数）ビットの計算能力（ここにいう計算能力は整数の加算、乗算、ビットシフト、ビットごとの論理演算などの計算ができることを指す）を有する計算器により、Ｎビットの整数演算を［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数に分割して計算され、前記「カオス計算器」の２Ｎビットの計算結果ｄに対し、上位Ｎビット（ｄ０ｄ１．．．ｄＮ−１）を関数ｘｔ＋１＝４ｘｔ（１−ｘｔ）を繰り返し計算するための入力（ａ）とし、前記ｄに対し特定のビットの間に論理演算を行い、Ｎビットの結果を乱数ｒ（ｒ０ｒ１．．．ｒＮ−１）として出力し、前記入力ａに対する計算結果である２Ｎビットのｄの各ビットが「カオス計算器」の計算過程において、計算によって影響を受けた入力ａのビット数が異なり、一様分布でない統計的な特性を示し、前記ｄの各ビットがそれぞれ入力ａから影響を受けているビットの数をそれぞれのビットが持つ複雑度とし、前記入力ａとの関連するビット数（複雑度）の異なる２Ｎビットの片寄りのある統計的分布特性を持つｄに対し、前記ｄの特定のビットの間の論理演算で生成される乱数ｒｉ（ｉ＝０，１，．．．Ｎ−１）が入力ａから、異なる形で影響を受けるビットの数をｒｉが持つ複雑度として、それをｓｒｉであらわし、前記ｄの特定のビットの間の論理演算はその演算で生成される乱数ｒの各ビットｒｉが持つｓｒｉがすべてのｉ値において、最大（ｓｒｉ＝Ｎ、即ち入力ａ（ａ０ａ１．．．ａＮ−１）のすべてのビットから異なる形で影響を受けること）となることを条件とする（ｒを一様分布の乱数にして出力する）撹拌方法を特徴とする。
【００１６】  本発明（請求項５）に係る請求項４記載の乱数生成方法は前記（請求項４）に記載されるｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間の論理演算はｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の１対１の論理演算であることを特徴とする。
【００１７】  本発明（請求項６）に係る請求項４記載の乱数生成方法は前記（請求項４及び請求項５）に記載されるｓｒｉ＝Ｎとなる条件を満たすｄ（ｄ０ｄ１．．．ｄ２Ｎ−１）の特定のビット間（即ち、ｄｉ
0004308293.tif 000004
であることを特徴とする。
【発明の効果】
【００１８】  本発明が式（１）の計算に固定小数点演算を用いることで、計算精度（ビット幅）において、浮動小数点演算よりも効率のよい形態と高速化を実現した。
【００１９】  本発明が式（１）を固定小数点演算で演算するときに、整数を用いて、そして利用可能な演算システムの計算能力に最も適した分割計算による「カオス計算器」を用いて計算することで、計算精度の拡張を容易にし、生成されるカオスの振る舞いをする時系列の長周期化を実現した、
【００２０】  本発明の特徴とする撹拌手段は式（１）を一回計算する度に計算精度と同じビット数の２進乱数列を出力することができ、且つ、Ｕ字形の分布を持つカオスの振る舞いをする時系列から、一様分布の２進乱数列に変換することができた。
【００２１】  以上の３つの基本、単純の操作により、様々な規模のシステムに対応できる、計算精度を容易に拡張できる、周期性と生成速度と統計的性質が同時に実用的な高いレベルに達する乱数を生成する乱数生成装置を実現した。このような単純操作による目的実現の形態は乱数生成器の性能を保証した上、低価格化を可能にし産業技術として望ましい形態である。
【発明を実施するための最良の形態】
【００２２】  以下、図面を参照しながら、発明の実施の形態を説明し、その効果を示す。本実施形態は本発明が式（１）の計算において、最も有効な計算方法を採用し、その上、最も有効な撹拌手段を用いた乱数生成装置及び方法であることを説明する。【００２３】  図１は本発明の一実施形態である乱数生成装置１００の構成図を示す。本実施形態の乱数生成装置１００はＮビットの２進数列に対し、２ｍ（ｍは１以上の整数）ビットの計算能力を有する「カオス計算器」を用いて繰り返し計算し、「カオス計算器」の計算結果である２Ｎビット２進数列に対し、上位Ｎビットと下位Ｎビットとの間にビットごとの排他的論理和演算により長周期、良質な２進乱数列を高速に生成する。乱数生成装置１００は初期値入力部１０２、初期値変換部１０４、格納レジスタ１０６、「カオス計算器」１０８、データ抽出・撹拌部１１０、乱数格納レジスタ１１２、乱数生成制御部１１４を備える。【００２４】  初期値入力部１０２はＮビットの２進数列を固定小数点演算を行うための初期値の小数点以下の部分として受付ける。式（１）の計算を固定小数点演算にすることで、計算器のビット幅の利用効率を浮動小数点演算よりも高くした。一般に、高い計算精度を必要とする科学計算は浮動小数点演算が使われる。しかし、浮動小数点倍精度（仮数部５２ビット、指数１１ビット、符号１ビット）で式（１）の計算を観察すると、使われる指数部は最大６ビットであることがわかる。このように、式（１）の計算はハードウェアにしてもＯＳ上で計算しても、固定小数点演算のほうが合理的で有効であることが明らかである。【００２５】  初期値変換部１０４はＮビットの２進数列を［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数に変換して、式（１）の固定小数点演算を整数の演算による実現に備える。式（１）の固定小数点演算を整数の計算にしたことで、計算はより高速となり、計算精度の拡張も容易となった。２進計算機の上で式（１）を計算精度Ｎビットの固定小数点演算をするとき、ｘｔが１／２Ｎに離散化され、区間（１／２Ｎ，１−１／２Ｎ）の中で振舞いをする。そのため、２ｍ（例えば６４）ビット整数をサポートするシステムでは計算精度ｍ（例えば３２）ビット以下の式（１）の計算に整数を用いて容易にできる。整数の乗算、加算などは分割計算により計算精度が容易に拡張できることから、式（１）に対し、整数演算を用いた固定小数点演算の計算精度を容易に拡張できる。【００２６】  格納レジスタ１０６は計算精度Ｎビットの「カオス計算器」が（繰り返し）計算するための入力としての［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数を格納する。【００２７】  しかし、計算精度を拡張すると、図２に示したように写像速度が急速に低下する。そのため、一回の写像でより多いビットの数列の出力が必要となる。一方、一定の長さの数列に対し、ビット操作（移動、置換、論理演算）を繰り返すことにより複雑な数列が得られることが知られている。しかし、操作の繰り返す回数をより多くすることでよりランダムに見える数列が得られるが、操作回数を多くすると処理に要する時間も長くなるという問題がある。【００２８】  「カオス計算器」１０８は格納レジスタ１０６に格納され���いる［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数を入力とし、式（１）に対し整数演算により実行する。［（（Ｎ−１）／ｍ）］＋１桁のｍビットの整数における式（１）の演算（乗算、減算，加算）の原理は小学校で学んだ多桁１０進数の演算と同じであるため、説明を省略する。【００２９】  抽出・撹拌部１１０は「カオス計算器」１０８の２Ｎビットの計算結果（ｄ）に対し、上位Ｎビット（ｄ１）を式（１）を繰り返し計算するための入力として、格納レジスタ１０６に格納する。また、ビットｄｉとｄｉ＋Ｎ（ｉ＝０，１．．．Ｎ−１）との間の排他的論理和演算（ｒｉ
0004308293.tif 000005
が提案する撹拌手段及び撹拌方法は著しい偏りの分布を持つ２Ｎビットの数列（ｄ）に対し、特定のビット間に１対１の排他的論理和の演算を施すだけで、一様分布の計算精度のビット幅長（Ｎビット）の乱数の生成ができた。【００３０】  整数を用いる式（１）の計算を２進数の計算に展開して観察すると本発明の特徴とする撹拌方法が導かれる。Ｎビットの小数ｘｔの小数点以下の部分をＮビットの整数ａとすると、ｘｔ＝０．ａが成立する。１−ｘｔの小数点以下の部分をＮビットの整数ｂとすると、
0004308293.tif 000006
となっている。ここにｃ＝ａｂ、ｄ＝４ｃとすると（ｃ、ｄは２Ｎビットの整数）、ｄ＝４ａｂは式（１）の整数演算形態となる。ただし、ｄは２Ｎビットの整数であり、その上位Ｎビットはｘｔ＋１の小数点以下の部分になる。【００３１】  ここでｄの上位Ｎビットからなる整数をｄ１とし、下位Ｎビットからなる整数をｄ２とするとｘｔ＋１＝０．ｄ１が成り立つ。整数ａ、ｂ、ｃ、ｄを２進数に展開し、それぞれの各ビットを（ａ０ａ１．．．ａＮ−１）、（ｂ０ｂ１．．．ｂＮ−１）、（ｃ０ｃ１．．．ｃ２Ｎ−１）、（ｄ０ｄ１．．．ｄ２Ｎ−１）とし、式ｃ＝ａｂ、ｄ＝４ｃの演算過程とその結果を考察する。式ｄ＝４ｃの整数４の乗算は左へ２ビットシフトで実現されるため、まず、式ｃ＝ａｂ（２つのＮビットの２進整数ａとｂ）の乗算の過程とその結果ｃを考察する。【００３２】  ｃ＝ａｂの演算を２進数に展開すると、図３のようになる。図３からｃの各ビットｃｉとａ、ｂの各ビットの間に式（２）の関係が存在することが分かる。【００３３】
【数２】
0004308293.tif 000007
（ｋｃｉはｃｉ＋１からの桁上げ、ｉ＝２Ｎ−１のとき、ｋｃｉ＝０）【００３４】ここに、ｃｉを入力ａの各ビットの関数であらわすと、式（３）が得られる。【００３５】
【数３】
0004308293.tif 000008
【００３６】  ここにｃの各ビットｃｉが含む入力ａの各ビットの数をそのビットが持つ複雑度とし、それをｓｃｉとすると、ｃの各ビットの複雑度は式（４）となる。【００３７】
【数４】
0004308293.tif 000009
【００３８】  ｄの各ビットはｄ＝４ｃにより、式（５）となる。ただし、左ビットシフト演算で上位に押し出されたビットはその順番で下位に入れる。【００３９】
【数５】
0004308293.tif 000010
【００４０】  以上の考察に基づき、生成される２進数列の各ビットが最大な複雑度を有することを目標とした本発明が提案する撹拌方法である式（６）が生成する２進乱数列ｒの各ビットが有する複雑度ｓｒｉはすべてＮ（計算精度ビット長）であることが明らかとなる。【００４１】
【数６】
0004308293.tif 000011
【００４２】  式（６）を手段とする撹拌の３つの効果を図４，５，６，７を用いて説明する。【００４３】  図４は固定小数点演算計算精度１２８ビットで計算されたｄ１とｒの軌道である（整数値ｄ１とｒをそれぞれ固定小数点表示の小数点以下の部分とし、０〜１の間の値に変換して表示した）。ｄ１の軌道は式（１）によるカオスの振る舞いをする軌道であり（固定小数点演算１２８ビット）、ｄ１の値が０に近付いたときには数回の単調増加の規則が確認できる。それに対しｒの軌道にはこのような規則は見当たらない。また、ｄ１とｒの間にそれ以外の規則のあるような関連も見られない。【００４４】  図５は計算精度１２８ビットで計算されたｄ１の先頭８ビットの値の度数分布で、図６はｒの先頭８ビットの値の度数分布である。データ数はそれぞれ６５５３６である。ｄ１の分布はＵ字形に近い形になっている。それに対し、ｒの分布はほぼ一様分布になっていることが確認できる。なお、ｒに対する統計的検定の結果は後に示す。【００４５】  出力されるＮビットの乱数ｒは式（６）により生成されることから、ｒとｄ１の間に何らかの相関関係を持つ可能性があると考えられる。両者の間に線形的な相関関係をもつのであれば、ｒからｄ１即ちｘｔを推測することが可能となる。それは、あるｒの２進数列から他のｒの２進数列を推測できるという意味でもある。ここに、両者の対応関係をビットマップ上で確認する。高い計算精度（例えば１２８ビット）でのｄ１とｒのすべての対応関係を計算、表示することができないため、ここに計算精度１６ビットでの対応関係を出力して観察する。図７はｄ１を横軸に、対応するｒを縦軸にして計算精度１６ビットのときのとり得るすべてのｄ１を計算し、それとｒの対応関係をプロットしたビットマップである。式（１）が対称性を有するため、計算は入力ａを１〜３２７６７の３２７６７個の値にして行った。その結果、計算精度１６ビットのとき、ａのとり得る６５５３４（１６ビットの２進整数０．．．０と１０．．．０を除く）の値に対し、得られたｄ１の値は２８６７１個であり、ｒの値の数は３２７６７である、図７から、入力ａの値１〜３２７６７に対し、ｄ１の分布は偏っているが、偏っているｄ１の分布に対し、ｒは１〜６５５３５の間に均一に分散されていることが観察される。出力ｒの分布が式（６）の撹拌により、偏りのあるｄ１をとり得る値の全域に均一に分散されていることを図７でわかる。またｒとｄ１の間に線形的な相関関係を持たないことも確認された。以上の結果から、式（１）で計算される偏りのあるｘｔ（ｄ１）の系列に対し、式（６）による撹拌がその偏りを拡散し、一様分布のｒの系列を出力する効果があることを確認できた。【００４６】  以上式（６）の撹拌手段の効果を考察した結果、本発明が提案する撹拌手段が有効であることを示している。【００４７】  乱数格納レジスタ１１２は抽出・撹拌部が生成したＮビットの乱数を２進数列で格納する。【００４８】  乱数生成制御部１１４は乱数生成のための各部の動作と繰り返し作業の制御を行う。【００４９】  図８は乱数生成装置１００の動作の一例を示すフローチャートである。乱数生成命令により本フローチャートに示す乱数生成装置１００の動��はスタートする。【００５０】  初期値入力部１０２に入力されたＮビット２進数列を初期値として受け取る（ｓ１０２）。そして、初期値変換部１０４は受け取ったＮビットの２進数列を［（（Ｎ−１）／ｍ）＋１］桁の２ｍ進数の整数に変換し（ｓ１０４）、格納レジスタ１０６に格納する（ｓ１０６）。次は１０６に格納されている整数を「カオス計算器」１０８が入力として写像する（ｓ１０８）。そして、抽出・撹拌部は写像結果である２Ｎビット長の整数（ｄ）の上位Ｎビットの整数（ｄ１）を格納レジスタ１０６に格納し、上位Ｎビットの整数（ｄ１）と下位Ｎビットの整数（ｄ２）との間にビットごとの排他的論理和を演算する（ｓ１１０）。続いて、乱数格納レジスタ１１２はＮビットの乱数ｒを格納し（ｓ１１２）、本フローチャートに示す乱数生成装置１００の動作は終了する。【００５１】  乱数を継続して生成する場合、前記（ｓ１０８）から（ｓ１１２）を繰り返すことで乱数が生成される。【００５２】  前記乱数生成装置を用いて計算精度Ｎ＝１２８ビットで生成した乱数列を７項目の統計的検定を行った。本発明が提案する乱数生成器の出力が２進ビット列であるため、統計的検定はχ２検定を採用した。χ２分布はサンプル数が十分大きいときだけ有効な近似値であるが局所的にランダムではない挙動を平滑化してしまう可能性を考慮して、複数のサンプル数において、χ２検定を行った。【００５３】  また、計算精度１２８ビットの生成器は一回の計算（写像）で出力される２進数列ｒはｒ０ｒ１．．．ｒ１２７の１２８ビットであるため、検定は出力されるすべてのビットに対し行った。しかし、この検定方法では、一回の写像で複数の２進ブロック（サンプル）を出力するため、写像ごとに生成される１２８ビットの乱数の間に存在するランダムでない挙動を平滑化してしまう可能性がある。ここに同じ検定を「一回の写像に１つの２進ブロック（サンプル）しか出力しない場合」に対しても行った。【００５４】  χ２検定は等分布検定、シリアル検定、ポーカー検定、クーポン券収集検定、上昇連検定、誕生日間隔検定の６項目を行った。各検定においてのサンプル数はそれぞれの検定のカテゴリ数に応じて決定するが、すべての項目の検定は１０００回行った。χ２検定は得られる１０００個のχ２値に対し、Ｐ＜１％，５％，２５％，５０％，７５％，９５％，９９％の７のカテゴリに分類して、その理論値との比較を行う。それらの検定に加え、シリアル相関検定の計７各項の検定をした。シリアル相関検定は９５％の信頼区間に入る数を計数する。【００５５】  それぞれの１２８ビットの数列ｒのすべてのビットに対する検定の４種類のサンプル数をｎ１、ｎ２、ｎ３、ｎ４としたときの結果と、１２８ビットの数列ｒの先頭１つの２進ブロック（サンプル）しか出力しない場合に対する検定の４週類のサンプル数をｎＡ１、ｎＡ２、ｎＡ３、ｎＡ４としたときの結果を図９〜１５に示す。図９は８ビットの整数数列（０〜２５５）を生成し、等分布検定を行った結果である。サンプル数はｎ１（ｎＡ１）＝２１６、ｎ２（ｎＡ２）＝２１６×１０、ｎ３（ｎＡ３）＝２１６×１００、ｎ４（ｎＡ４）＝２１６×１０００の４通りとした。検定結果は理論値の近傍にあり，良好な��果を示している。図１０は８ビットの整数数列を生成し、シリアル検定（２次元の等分布検定）を行った結果である。サンプル数はｎ１（ｎＡ１）＝２２０、ｎ２（ｎＡ２）＝２２０×１０、ｎ３（ｎＡ３）＝２２０×１００、ｎ４（ｎＡ４）＝２２０×１０００の４通りとした。検定結果が理論値の近傍に点在し、良好な結果を示している。図１１は３ビットの整数数列を生成し、５週類のカテゴリ、自由度４のポーカー検定を行った結果である。サンプル数はｎ１（ｎＡ１）＝２１０、ｎ２（ｎＡ２）＝２１０×１０、ｎ３（ｎＡ３）＝２１０×１００、ｎ４（ｎＡ４）＝２１０×１０００の４通りとした。ｎ１（ｎＡ１）の場合のχ２値の上側の１％に入る数が２％を超え、やや多いが、サンプル数を増やしたその他の場合は何れも良好な結果となっている。ｎ１（ｎＡ１）の検定結果はデータ数が少な過ぎることが原因といえる。図１２は自由度３０のクーポン券収集検定を行った結果である。サンプル数はｎ１（ｎＡ１）＝２１０、ｎ２（ｎＡ２）＝２１０×１０、ｎ３（ｎＡ３）＝２１０×１００、ｎ４（ｎＡ４）＝２１０×１０００の４通りとした。良好な結果を示している。図１３は３２ビットの整数の数列を生成し、上昇連の検定を行った結果である、サンプル数はｎ１（ｎＡ１）＝２１６、ｎ２（ｎＡ２）＝２１６×１０、ｎ３（ｎＡ３）＝２１６×１００、ｎ４（ｎＡ４）＝２１６×１０００の４通りとした。何れも良好な結果を示している。図１４は２５ビットの整数数列を生成し，パラメータｍ＝２２５、ｎ＝２９自由度３の誕生日間隔検定を行った結果である。試行回数はｎ１（ｎＡ１）＝１０３、ｎ２（ｎＡ２）＝１０４、ｎ３（ｎＡ３）＝１０５、ｎ４（ｎＡ４）＝１０６の４通りとした。良好な結果を示している。図１５は４ビットの整数（０〜１５）の数列を生成し、シリアル相関検定を行った結果である。サンプル数はｎ１（ｎＡ１）＝２１０、ｎ２（ｎＡ２）＝２１０×１０、ｎ３（ｎＡ３）＝２１０×１００、ｎ４（ｎＡ４）＝２１０×１０００の４通りとした。９５％の信頼区間では１０００回の検定で、相関係数Ｃがμ−２σ≦Ｃ≦μ＋２σに入る数はほとんど９５０以上になっている。良好な結果と言える、厳しい検定の結果が何れも検定対象はランダムといえる結果を示している。なお、検定の具体的な手順は文献｛ＤＯＮＡＬＤ  Ｅ．Ｋｎｕｔｈ，  “Ｔｈｅ  Ａｒｔ  ｏｆ  Ｃｏｍｐｕｔｅｒ  Ｐｒｏｇｒａｍｍｉｎｇ，  Ｖｏｌ．２，  Ｓｅｍｉｎｕｍｅｒｉｃａｌ  Ａｌｇｏｒｉｔｈｍｓ  Ｔｈｉｒｄ  Ｅｄｉｔｉｏｎ‘’，株式会社アスキー（２００４））｝に示されている。
【産業上の利用可能性】
【００５６】  本発明によれば、非線形関数から生成するカオスの振る舞いをする長周期、厳しい統計的検定に耐える乱数を高速に生成できる、それはさまざまな応用分野：シミュレーション、サンプリング、数値解析、コンピュータプログラミング、意思決定、暗号、美術、レクリエーションなどで利用できる。【００５７】  本発明は乱数の生成において、整数を用いた計算（加算、乗算、ビットシフト、論理演算）だけで実行されるため、整数の分割計算が容易であるから、異なるシステム（汎用計算機（各種のＯＳ）、専用ハードウェア、マイクロコンピュータなど）であっても、最も基本的な整数演算（加算、乗算、ビットシフト、ビットごとの論理演算）ができるのであれば、同じ入力による同じ出力が得られる。【００５８】  本発明は計算精度Ｎビットのとき、一回の写像につき、最小の撹拌回数（一回）で最大の複雑度（Ｎ）を有するビットを最多（Ｎビット）に出力ができ、計算精度の拡張による乱数生成速度の低下を抑え、より高速な乱数生成を実現した。計算精度と乱数生成速度の関係の例を図１６に示す。十分に実用的な高いレベルに達した数値である。加算、乗算、ビットシフト、論理演算などのコンピュータが最も得意とした計算しか行わないため、集積回路化も容易に実現でき、更なる高速化も容易である。【００５９】  本発明はセキュリティー用に不向きな伝統的乱数生成法である線形合同法と違い、カオスの振る舞いをする時系列を生成する非線形写像を計算することにより、乱数を生成する上、撹拌方法に一方向性を有する排他的論理和の演算を施したことで、出力された乱数から内部状態ｘｔを予測することができない。また、出力された一部の乱数から他の乱数を推測することもできない。【００６０】  従って、本発明の乱数生成装置は様々なニーズに対応できる「性能−コスト」の組合せを持ち、拡張性も富み、科学研究、セキュリティー分野を含む幅広い産業の分野での応用が可能である。【００６１】  以上、実施形態を用いて本発明を説明したが、本発明の技術手段は上記実施形態に記載の範囲に限定されることではない。上記実施形態に変更または改良を加えることができる。また、上記発明は計算式がシンプルなカオスを生成する式（１）に対し、一回の写像につき、最小の撹拌回数（一回）で最大の複雑度（Ｎ）を有するビットを最多（Ｎビット）に出力する撹拌手段であるが、乱数の生成効率及び品質の低下を代償に上記実施形態に変更を加えることも可能である。そのような変更、改良を加えた形態も本発明の技術の範囲に含まれることは明らかである。
【図面の簡単な説明】
【００６２】
【図１】  本発明の一実施形態である乱数生成装置の構成図
【図２】  ｍ＝３２のときの計算精度と写像速度の間の関係を示す表。
【図３】  Ｎビットの整数の乗算（ｃ＝ａｂ）を２進数に展開した計算式。
【図４】  ｄ１とｒの軌道の比較の図。
【図５】  ｄ１の上位８ビットコードの分布を示す図。
【図６】  ｒの上位８ビットコードの分布を示す図。
【図７】  ｄ１とｒの対応関係を示す図。
【図８】  乱数生成装置１００の動作の一実施例を示すフローチャート。
【図９】  乱数に対する等分布検定の結果を示す図。
【図１０】  乱数に対するシリアル検定の結果を示す図。
【図１１】  乱数に対するポーカー検定の結果を示す図。
【図１２】  乱数に対するクーポン券収集検定の結果を示す図。
【図１３】  乱数に対する上昇連検定の結果を示す図。
【図１４】  乱数に対する誕生日間隔検定の結果を示す図。
【図１５】  乱数に対するシリアル相関検定の結果を示す図。
【図１６】  ｍ＝３２のときの計算精度と乱数生成速度の間の関係を示す表。
【符号の説明】
【００６３】１００  乱数生成装置
１０２  初期値入力部
１０４  初期値変換部
１０６  格納レジスタ
１０８  「カオス計算器」
１１０  抽出・撹拌処理部
１１２  乱数格納レジスタ
１１４  乱数生成制御部
〔手数料に関する特記事項〕特許法第１９５条の２の規定による審査請求料の免除
【図１】
0004308293.tif 000014
【図２】
0004308293.tif 000015
【図３】
0004308293.tif 000016
【図４】
0004308293.tif 000017
【図５】
0004308293.tif 000018
【図６】
0004308293.tif 000019
【図７】
0004308293.tif 000020
【図８】
0004308293.tif 000021
【図９】
0004308293.tif 000022
【図１０】
0004308293.tif 000023
【図１１】
0004308293.tif 000024
【図１２】
0004308293.tif 000025
【図１３】
0004308293.tif 000026
【図１４】
0004308293.tif 000027
【図１５】
0004308293.tif 000028
【図１６】
0004308293.tif 000029