(57)【要約】【課題】  小規模コンピュータシステムや携帯端末にて使用できる、効率の良い擬似乱数発生装置を提供することを課題とする。【解決手段】  ｎ個の要素を持つメモリテーブルを用意する。ｎ個の要素にはそれぞれ個別なユニークな値を設定する。このメモリテーブルの各要素の内容を交換することにより、メモリテーブルの状態を変化させ、この変化を乱数値として取り出す。これにより、理論上は最大ｎの階乗の周期の乱数表を得ることができる。【選択図】  図２
2008053936.tif 000002
【特許請求の範囲】
【請求項１】
情報の記憶装置と、この記憶装置に格納されn個の要素（nは自然数）を持つメモリテーブルAと、このメモリテーブルAの任意の要素に格納されている値を取り出して、当該値を乱数値として出力する乱数値出力手段と、前記メモリテーブルAの内部の要素を並べ替えるテーブル変更手段とを備えたことを特長とする擬似乱数発生装置。
【請求項２】
請求項１記載の擬似乱数発生装置において、
前記記憶装置にm個の要素（mは自然数）を持つメモリテーブルBを備え、前記テーブル変更手段は、このメモリテーブルBの要素が持つ数値に従い、前記メモリテーブルAの内部の要素を並べ替えることを特徴とする擬似乱数発生装置。
【請求項３】
前記メモリテーブルBの要素が持つ値として、任意の素数を持つようにしたことを特徴とする請求項２記載の擬似乱数発生装置。
【請求項４】
前記テーブル変更手段は、前記メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素と内容を入れ替える機能を有し、そのために数値pとして前記メモリテーブルBの要素の値を順次取得する機能を有することを特徴とした請求項２又は３記載の擬似乱数発生装置。
【請求項５】
前記テーブル変更手段は、前記メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素の持つ数値に従い現在選択している要素の値を変更する機能を有し、そのために数値pとして前記メモリテーブルBの要素の値を順次取得する機能を有することを特徴とする請求項２又は３記載の擬似乱数発生装置。
【請求項６】
請求項１記載の擬似乱数発生装置において、
前記記憶装置に、前記メモリテーブルAの任意の要素を指し示すためのインデックスメモリNを備え、前記テーブル変更手段は、このインデックスメモリNの値が指し示すメモリテーブルAの要素に対して内容の変更を行うことを特徴とした擬似乱数発生装置。
【請求項７】
前記テーブル変更手段は、前記インデックスメモリNにより、メモリテーブルAの内容を変更した後、インデックスメモリNの値を任意の定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリNの値が前記メモリテーブルA の終端以降を指し示す場合、インデックスメモリNの値を前記メモリテーブルAの先頭を指し示す値に変更することを特徴とした請求項６記載の擬似乱数発生装置。
【請求項８】
前記記憶装置は、前記メモリテーブルBの任意の要素を指し示すためのインデックスメモリMを備え、前記テーブル変更手段は、このインデックスメモリMの値が指し示す前記メモリテーブルBの要素を取り出して前記値pとして前記メモリテーブルAの操作を行うことを特徴とした請求項４又は５記載の擬似乱数発生装置。
【請求項９】
前記テーブル変更手段は、前記インデックスメモリMにより、前記メモリテーブルBより値pを取得した後、インデックスメモリMの値を任意の定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリMの値がメモリテーブルB の終端以降を指し示す場合、インデックスメモリMの値を前記メモリテーブルBの先頭を指し示す値に変更することを特徴とした請求項８記載の擬似乱数発生装置。
【請求項１０】
請求項６記載の擬似乱数発生装置において、
前記インデックスメモリNの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリNに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項１１】
請求項８記載の擬似乱数発生装置において、
前記インデックスメモリMの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリMに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項１２】
請求項１乃至１１のいずれかの擬似乱数発生装置において、前記各手段の動作を処理装置に実行させることを特徴とした擬似乱数発生プログラム。
【請求項１３】
請求項１２記載の擬似乱数発生プログラムを記録した媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、擬似乱数を発生するための装置およびプログラム並びにプログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。特に、少リソースな、組込機器、家電品、携帯機器、小型情報端末、小型ゲーム端末機器等に用いられる擬似乱数の生成に関するものである。
【背景技術】
【０００２】
従来、少ないリソースで乱数生成を実現しようとするもので、自装置内で乱数生成する手段が開示されている（特許文献１参照）。【０００３】
また、擬似乱数生成器としてメルセンヌ・ツイスタが知られている。メルセンヌ素数を利用したメルセンヌ・ツイスタ(Mersenne twister)は、1997年（論文発表は1998年1月）に松本眞と西村拓士によって開発された擬似乱数生成器である。周期が2の19937乗-1つまり６２３ワード（19937ビット、2492バイト）の表現力で、623次元超立方体の中に均等に分布することが証明されている（非特許文献１参照）。【０００４】
また、外務省により公開されている暗号の紹介のページが存在する。有限乱数式、無限乱数式暗号を判りやすく紹介している。ここでは無限乱数式暗号は論理的に解読できないという事実を述べている（非特許文献２参照）。
このように、暗号用に品質の良い乱数が必要とされ、研究されているが、より小さな機材で動き、より速く、周期が長く、論理的に予測困難な乱数生成器を求める要望が強い。メルセンヌ・ツイスタは周期という点で優れているが、一定の乱数列を出力するとその先が予測可能となるため、暗号には向かないなど短所もあり、新しい擬似乱数発生装置の要求は高い。
【特許文献１】特開平１０−２４７１４０号公報
【非特許文献１】M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. on Modeling and Computer Simulation Vol. 8, No. 1, January pp.3-30 (1998)http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/mt.html
【非特許文献２】外務省大臣官房情報通信課  非常勤講師  奥村定夫「外交と暗号」http: //www.mofa.go.jp/mofaj/annai/shocho/e_seifu/toukou2004.html
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述したように、データの暗号化においては、有限乱数式と無限乱数式が存在する。有限乱数式とは、同じ乱数表を繰り返し暗号化に使用する方式である。効率が良い反面一度乱数表を解読されると後は簡単に解読ができる。
一方、無限乱数式は一度使用した乱数表は２度と使わないという方式である。無限乱数式は同じ乱数を2度使わず1度限りの使用においては絶対に解読できないことが情報理論により証明されている暗号である。
電子計算機、小型携帯端末において強度の強い無限乱数式の暗号化を行うためには、高速で長周期の擬似乱数を生成する必要がある。本発明は、効率よく長周期の擬似乱数を発生し電子計算機、小型端末、電子機器に提供するためのものである。
【課題を解決するための手段】
【０００６】
当発明は、ｎ個の目を持つサイコロを模した、ｎ個の要素を持つ例えばリングバッファ状のメモリテーブルAを用意する。n個の要素に一つずつ異なる値を格納する。【０００７】
このメモリテーブルAから任意の２つの要素を選び入れ替える。この処理を繰り返すことによりメモリテーブルAの内容はシャッフルされ、n個の要素の値を乱数として取り出すとn個の乱数列を生成できる。【０００８】
この処理により得られる乱数列、つまりメモリテーブルの状態は、ｎの階乗の組み合わせを得られる。ｎを２５６とした時は、理論上は次の組み合わせを得る事ができる。【０００９】
２５６の階乗  ≒  ８．５７  ×  １０の５０６乗【００１０】
このように、メモリテーブルAを使用した場合、要素の数を増やす事により理論上の最大の組み合わせ値（組み合わせの数）を高くできる事がわかる。【００１１】
この組み合わせ値は、メモリテーブルAを乱数列とした場合は理論上の最大周期である。メモリテーブルAの２つの要素の交換が満遍なく最良に行われた時、乱数列の周期は理論上の最大値になる。交換が偏わって行われた時はそれが乱数の周期の形になって現れ周期は小さくなる。つまり、乱数列の品質の劣化になって現れる。【００１２】
好ましい交換とは、逆に悪い交換例を挙げる事により理解できる。悪い交換例としてメモリテーブルAの任意の要素をｎ個先の要素と交換する事を考慮する。ｎ個の要素を持つ例えばリングバッファのｎ個先の要素は循環して自分自身であるから結局テーブルは変化しない。これは極端に悪い例であるが、このように特定の２つの要素だけが入れ替わり全体としては変化しないというのが悪い交換である。【００１３】
このような事にならないように、交換する２つの要素の位置関係は同じ事の繰り返しにならないように常にテーブル内を満遍なく変化する工夫が必要である。【００１４】
ここに、素数、この割り切る事の出来ない特殊な値に着目し、メモリテーブルA中の一つの要素を素数の値だけ先の要素と交換するとよい。【００１５】
これを各要素に繰り返し行うと万遍のない要素の入れ替え、好ましいシャッフルが行われる。いまここでメモリテーブルAの要素数nとし、このメモリテーブルAに対して素数pによる要素の内容の交換を考えてみる。【００１６】
リングバッファを構成するメモリテーブルAに対して、現在指示する要素に対してp個先の要素と内容を交換する。交換が終わったらリングバッファを１要素回転させ一つずらす。この処理を繰り返し行った時にメモリバッファA全体の内容が一巡して元に戻る周期を計算する。【００１７】
素数とは最大公約数がそれ自身である数字のことである。これより、素数pはそれ自身が最大公約数であることから、周期は、メモリバッファAの要素数nと素数pとの公倍数であると言える。つまり、【００１８】
周期  ＝  n  ×  p
この数式に一致もしくは近似すると考える事ができる。さらに、素数p1,p2,,,pn-1と増やし（nは正の整数）、メモリテーブルAの要素を交換するごとに、p1,p2,,,pn-1を順繰りに使用した場合、
周期  ＝  n  ×  p1 × p2 × ... × pn-1（nは正の整数）
この数式に一致もしくは近似すると考える事ができる。本発明は、このようにして例えばリングバッファであるメモリテーブルAに対して素数を利用した要素の交換によりメモリテーブルAをシャッフルする事を特徴とするものである。【００１９】
乱数は、任意のタイミングでメモリテーブルAの内容全てもしくは要素を取り出すことにより得る事ができる。【００２０】
即ち、本願発明は、情報の記憶装置と、この記憶装置に格納されn個の要素（nは自然数）を持つメモリテーブルAとを備える。また、このメモリテーブルAの任意の要素に格納されている値を取り出して、当該値を乱数値として出力する乱数値出力手段を備える。更に、メモリテーブルAの内部の要素を並べ替えるテーブル変更手段を備える。【００２１】
記憶装置には、m個の要素（mは自然数）を持つメモリテーブルBを設けるとよい。この場合、テーブル変更手段は、このメモリテーブルBの要素が持つ数値に従い、メモリテーブルAの内部の要素を並べ替えることができる。メモリテーブルBの要素が持つ値としては、任意の素数を持つとよい。【００２２】
テーブル変更手段は、メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素と内容を入れ替えるとよい。この場合、数値pとしてメモリテーブルBの要素の値を順次取得する。【００２３】
又は、テーブル変更手段は、メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素の持つ数値に従い現在選択している要素の値を変更してもよい。この場合も、数値pとしてメモリテーブルBの要素の値を順次取得する。【００２４】
また、記憶装置に、メモリテーブルAの任意の要素を指し示すためのインデックスメモリNを備えるとよい。この場合、テーブル変更手段は、このインデックスメモリNの値が指し示すメモリテーブルAの要素に対して内容の変更を行う。【００２５】
また、テーブル変更手段は、インデックスメモリNにより、メモリテーブルAの内容を変更した後、インデックスメモリNの値を任意の定数Kの値だけ加算するとよい。当該加算の結果、インデックスメモリNの値がメモリテーブルA の終端以降を指し示す場合、インデックスメモリNの値をメモリテーブルAの先頭を指し示す値に変更する。【００２６】
また、記憶装置は、メモリテーブルBの任意の要素を指し示すためのインデックスメモリMを備えるとよい。この場合、テーブル変更手段は、このインデックスメモリMの値が指し示すメモリテーブルBの要素を取り出して値pとしてメモリテーブルAの操作を行う。【００２７】
テーブル変更手段は、インデックスメモリMにより、メモリテーブルBより値pを取得した後、インデックスメモリMの値を任意の定数Kの値だけ加算するとよい。当該加算の結果、インデックスメモリMの値がメモリテーブルB の終端以降を指し示す場合、インデックスメモリMの値をメモリテーブルBの先頭を指し示す値に変更する。【００２８】
また、インデックスメモリNの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリNに設定する手段とを備えてもよい。【００２９】
同様に、インデックスメモリMの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリMに設定する手段とを備えてもよい。【００３０】
以上において、各手段は、実際には処理装置が所定のプログラムを実行することによって実現されるものである。また、記憶装置は、一時記憶、大容量記憶およびリムーバブル媒体を含む包括的概念である。
【発明を実施するための最良の形態】
【００３１】
本発明の実施例について図面を用いて説明する。
［実施例１］
この実施例１では、擬似乱数の発生を行うプログラムおよび装置を開示する。図１は、実施例１及び後述する各実施例で使用するコンピュータシステム又は電子機器の全体構成図である。【００３２】
図１のコンピュータシステムは、情報処理装置S1011を備えている。この情報処理装置S1011は、計算機の全体制御および各種プログラムを実行する中央処理装置（以下ＣＰＵ）である。また、図１のコンピュータシステムは、ＲＯＭＢＩＯＳのS1012と、アダプタS1015およびS1016と、各種プログラムやデータがロードされるメモリ装置S1013とを備え、それらはシステムバスS1014によって接続されている。また、図１のコンピュータシステムは、ユーザがデータを入力するための入力装置と、ユーザに情報を表示するための表示装置とを備えている（図示略）。【００３３】
アダプタS1015は、HDD-S1030のホストインタフェースS1020に接続されている。また、アダプタS1016には、リーダライタS1019が接続されている。このリーダライタS1019には、着脱可能なストレージデバイスが接続される。【００３４】
本願では、ストレージデバイスとして、USB装置S1040を用いる。USB装置S1040は、ストレージデバイスの機能を備える。以下、本願ではUSB装置S1040がメモリディスク装置であるとして説明するが、USB装置S1040は、本願発明の効果を奏するものであれば任意の装置でよい。【００３５】
ＲＯＭＢＩＯＳ-S1012には、HDD-S1030あるいはストレージデバイスであるUSB装置S1040などのシステムブート可能デバイスから一つのデバイスを選択するステップと、当該デバイスからシステムブートローダをメモリ装置S1013に読出すステップと、当該読み出したシステムブートローダに分岐するステップ（いわゆるシステムブート機能）とを備える。【００３６】
HDD-S1030あるいは任意のストレージデバイスから読み出されたOSプログラムは、メモリ装置S1013に格納され、ＣＰＵ-S1011により実行される。【００３７】
またＣＰＵ-S1011は、各種のプログラムを実行することによって、後述する各実施例の動作を実現する。各実施例の動作は流れ図に沿って説明する。本出願において、ＣＰＵ-S1011が実行する処理の流れ図の特殊記号および各種表記は、コンピュータ言語であるC言語に従う。文中、特に宣言のない変数においてメモリのアドレスを参照する変数の型はＣ言語のポインタ型とし、そうでない変数はint型変数とする。
％・・・剰余計算を示す記号である。
＾  ・・・排他的論理輪を示す記号である。
++ ・・・インクリメント、値を一つ増加を意味する記号である。
[n ] ・・・配列を意味する記号である。ｎは配列の添字である。
* ・・・アドレス型変数の前に記す場合は、変数の示すアドレス上の値を示す。
0x・・・１６進法の数値であることを示す。【００３８】
図２は、本発明の第1実施例における初期化処理プログラムinz()が利用する記憶領域の構成を表している。ＣＰＵ-S1011は、初期化処理プログラムinz()を実行する際に、図２に示す記憶領域をメモリ装置S1013に確保する。【００３９】
図２において、Ｓ１２００は、メモリテーブルＡである。メモリテーブルＡは、ｎ個（ｎ＝1,2,3,・・・）の要素を持つ。【００４０】
定数ｎは、後述のメモリ変数Ｓ１２０１の表現力の許す範囲内であれば、コンピュータシステムのメモリの許す値を定めることができる。【００４１】
本実施例では、１６進の乱数値を生成することから、ｎは２５６の倍数値を取るものとして全体を設計している。本実施例ではｎは２５６とする。【００４２】
また、各要素の大きさは本来任意である。得たい乱数の大きさに応じて大きくできるものである。実施例１において各要素の大きさは１バイトである。【００４３】
Ｓ１２０１はメモリ変数である。内容としてＳ１２００の要素の位置情報を格納するものである。このメモリ変数の大きさはＳ１２００の全要素数を表現できる大きさであれば任意である。ここではゼロ〜６５５３５の表現力を持つ２バイト型とする。【００４４】
Ｓ１２０２はメモリテーブルＢである。メモリテーブルＢはｍ個の要素を持つ。定数ｍは任意の値である。コンピュータシステムのメモリの許す値を設定できる。本実施例では動作を分かりやすくするためにｍを７と定める。【００４５】
また、メモリテーブルＢの各要素の大きさも任意であるが、この実施例では２バイトとする。【００４６】
Ｓ１２０３はメモリ変数である。内容としてＳ１２０２の要素の位置情報を格納するものである。本実施例では２バイトのサイズを持つ。【００４７】
図３は実施例１における初期化処理プログラムinz()の処理の流れを表している。【００４８】
Ｓ１３００Ａにて本処理の初期化を行う。２バイト型のメモリ変数iを確保している。変数iは、図２のメモリテーブルＡ-Ｓ１２００の要素数を表現できるサイズであれば他のサイズでもよい。【００４９】
Ｓ１３０１Ａでは、ｍ個の要素を持つ図２のメモリテーブルＢ-Ｓ１２０２の初期化を行う。具体的には、各要素に２，３，５，７...とｍ個の素数を登録する。本実施例ではｍは７であるから、２，３，５，７，１１，１３，１７の値をＳ１２０２の７つの各要素に格納する。【００５０】
Ｓ１３０２Ａでは、図２のＳ１２０１にゼロを設定している。【００５１】
Ｓ１３０３Ａでは、図２のＳ１２０３にゼロを設定している。【００５２】
Ｓ１３０４Ａはループ処理である。変数iをゼロに初期化し、一回ループするごとにiの値を一つ増加してｎ回ループする。ｎ回ループした後は終了するものである。【００５３】
Ｓ１３０５Ａでは、Ｓ１２００に値を格納している。Ｓ１２００の先頭からi個目の要素に対して、iの値に１６進数ｆｆでアンドをかけた値を格納している。【００５４】
このアンド処理は、Ｓ１２００の各要素に１６進のゼロ〜ｆｆの数値だけを格納する仕掛けである。【００５５】
図４は、実施例１における乱数発生プログラムｒｎｄ()の処理の流れを表している。ｒｎｄ（）は乱数を発生し帰り値として１バイトの乱数を持つものである。本実施例の本体処理である。【００５６】
Ｓ１３００は初期化処理を行っている。変数sts,wk,wk1,tbl1,tbl2をここで確保している。【００５７】
Ｓ１３０１は、変数ｔｂｌ１に、メモリテーブルＡ-Ｓ１２００からＳ１２０１が示す値を要素番号とした要素の開始アドレスを格納している。いま仮にＳ１２０１をゼロとした場合、Ｓ１２００のゼロ個めつまり最初の要素の開始アドレスを格納する。【００５８】
Ｓ１３０２は、メモリテーブルＢ-Ｓ１２０２からＳ１２０３が示す値番目の要素の値にＳ１２０１の値を加算した結果を変数ｗｋに格納している。【００５９】
Ｓ１３０３では、ｗｋの値がＳ１２００の要素の数以上の値を示さないように制限を加えている。定数_BUF_SIZE_MASKはＳ１２００の要素数ｎ−１の値を持つものである。【００６０】
本実施例では、要素数ｎが２５６（１６進数１００）の整数倍のとき、本プログラムは正常に動くようにできている。【００６１】
本実施例では、ｎを２５６としているので定数_BUF_SIZE_MASKの値として２５５（１６進数ｆｆ）とする。そして、ｗｋの値と定数_BUF_SIZE_MASKのビットパターンとのアンドをとり、その結果をｗｋに格納している。【００６２】
つまり、ｗｋは常にＳ１２００のゼロ番目の要素から最後の要素までの間のいずれかの要素を示す。【００６３】
Ｓ１３０４では、メモリテーブルＡ-Ｓ１２００のうちｗｋが示す値を要素番号とした要素の開始アドレスを変数ｔｂｌ２に格納している。いま仮にｗｋをゼロとした場合、Ｓ１２００のゼロ個めつまり最初の要素の開始アドレスを格納する。【００６４】
Ｓ１３０５では、変数ｔｂｌ１の示すアドレスの値を読み取り、変数ｗｋ１に格納している。変数ｔｂｌ１はＳ１２００の要素のどれかのアドレスを示しているから、結果Ｓ１２００のうちの一つの要素の開始アドレスをｗｋ１に格納する。【００６５】
Ｓ１３０６では、変数ｔｂｌ２の示すアドレスの値を読み取り、変数ｔｂｌ１の示すアドレスに格納している。変数ｔｂｌ１、ｔｂｌ２はそれぞれＳ１２００の要素のどれかのアドレスを示しているから、結果Ｓ１２００の要素の一つの値を他の要素に格納している。【００６６】
Ｓ１３０７では、変数ｔｂｌ２の示すアドレスにｗｋ１の値を格納する。変数ｔｂｌ２はＳ１２００の要素のどれかのアドレスを示しているから、結果Ｓ１２００の要素の一つにｗｋ１の値を格納する。【００６７】
Ｓ１３０８では、変数ｓｔｓに変数ｔｂｌ１の示すアドレスの内容を格納する。【００６８】
変数ｔｂｌ１はＳ１２００の要素のどれかのアドレスを示しているから、結果Ｓ１２００の要素の一つの値をｓｔｓに格納する。【００６９】
Ｓ１３０９では、Ｓ１２０１が格納している値を一つ増加する。【００７０】
Ｓ１３１０では、Ｓ１２０１の値に定数_BUF_SIZE_MASKでアンドをとり、その結果をＳ１２０１に格納している。これは、Ｓ１２０１の示す値が常にＳ１２００の要素を指すようにする仕掛けである。【００７１】
Ｓ１２０１はＳ１２００のゼロ番目からｎ−１番目までの要素を順繰りに参照する。即ち、Ｓ１２０１はＳ１２００をリングバッファとして使用するためのポインタである。【００７２】
Ｓ１３１１は、Ｓ１２０３が格納している値を一つ増加する。【００７３】
Ｓ１３１２では、Ｓ１２０３の値が定数Ｓ＿ＴＢＬの値以上であるか比較し判定している。Ｓ＿ＴＢＬはメモリテーブルＳ１２０２の要素数ｍと同じ値である。この処理はＳ１２０３の値がメモリテーブルＳ１２０２の要素を示しているかの判定を行っている。【００７４】
Ｎｏの時は、Ｓ１２０２の任意の要素を示しているので何もしない。【００７５】
Ｙｅｓの時は、Ｓ１３１３の処理を行う。Ｓ１３１３では、Ｓ１２０３の値にゼロを格納している。【００７６】
Ｓ１２０３はＳ１２０２のゼロ番目からｍ−１番目までの要素を順繰りに参照する。即ち、Ｓ１２０３はＳ１２０２をリングバッファとして使用するためのポインタである。【００７７】
本プログラムは終了する時に、ｓｔｓの内容をサブルーチンの戻り値として呼び出し側に返す。ｓｔｓの内容が乱数の値である。【００７８】
以上説明したように、ＣＰＵがプログラムinz()およびｒｎｄ（）を実行することにより乱数発生装置が実現される。この２つのプログラムもしくは装置を合わせたものが本実施例の発明である。本実施例は、ソフトウェアライブラリと呼ばれるサブルーチン群として、本願発明を実現したものである。【００７９】
本発明は、従来ＣＰＵの負荷の高い複雑な計算により生成していた乱数をこのように簡易な手法により実現している。
従来の方式の問題点をあげると、最も一般的な合同二乗法という乱数の生成方式は３２ビットの数値の二乗を計算し、特定の定数にて剰余をとり乱数とする。この場合、掛け算というもっともＣＰＵの苦手な速度の遅い処理を行う。さらに３２ビット（４バイト）未満のＣＰＵの場合には素直にはこの３２ビットの数値を直接行えため劇的に処理が遅くなるという欠点がある。
また、合同二乗法は数値の二乗により乱数を生成する。周期の長い乱数を生成するためには、桁数を増やせば良い。しかし、桁数を増やすほどＣＰＵの処理は幾何級数的に増加しどんどん処理が遅くなっていく。
本発明はこのように、従来の方式に比べメモリ交換というＣＰＵの基本機能のみにより実現している。さらに、乱数の周期を長くするためには内部のテーブルを大きくするだけで直線的に増加するという性質を示している。
これより、計算機において効率よく長周期の乱数を生成することに成功している。【００８０】
［実施例２］【００８１】
実施例２も、擬似乱数の発生を行うプログラムおよび装置である。【００８２】
本実施例は、実施例１を利用して擬似乱数発生プログラムとして、よりまとまった完結した機能を提供するものである。【００８３】
図５は、実施例２において乱数発生プログラムrndmk()が利用する記憶領域の構成を表している。ＣＰＵ-S1011は、乱数発生プログラムrndmk()を実行する際に、図５に示す記憶領域をメモリ装置S1013に確保する。【００８４】
Ｓ１５００は乱数列のシードを指定するメモリ変数である。このメモリ変数には、ゼロからＳ１２００の要素数ｎ−１までの数値を指定する。Ｓ１５００は４バイトのメモリである。【００８５】
Ｓ１５０１は乱数列のシードを指定するものである。ここには、ゼロからＳ１２０２の要素数ｍ−１までの数値を指定する。Ｓ１５０１は４バイトのメモリである。【００８６】
Ｓ１５０２は、生成した乱数を格納するメモリ上のアドレスを保存するポインタ型のメモリ変数である。【００８７】
Ｓ１５０３は、Ｓ１５０２の値を開始アドレスとして確保するメモリの長さを値として持つ。【００８８】
本実施例は乱数を格納するメモリテーブルを確保しＳ１５００，Ｓ１５０１，Ｓ１５０２，Ｓ１５０３に所定の値を設定して実行すれば乱数を自動的に生成する。乱数はメモリテーブルに生成される。【００８９】
本実施例における乱数発生処理の流れは図６により行われる。【００９０】
Ｓ１６００は初期化処理である。４バイト型変数iを確保している。サイズは４バイトである。【００９１】
Ｓ１６０１は実施例１のプログラムinz()をサブルーチンとして実行している。【００９２】
Ｓ１６０２はＳ１２０１にＳ１５００の内容を設定している。Ｓ１２０１のメモリサイズが小さい時はＳ１５００の上位ビットは捨て下位ビットのみを設定する。【００９３】
Ｓ１６０３はＳ１２０３にＳ１５０１の内容を設定している。Ｓ１２０３のメモリサイズが小さい時はＳ１５０１の上位ビットは捨て下位ビットのみを設定する。【００９４】
Ｓ１６０４はループ処理である。iは最初ゼロに初期化されており、一回ループするごとにiの値を一つ増加してｎ回ループする。ｎ回ループした後は終了するものである。【００９５】
Ｓ１６０５は実施例１の乱数発生プログラムｒｎｄ（）をサブルーチンコールしている。帰り値として乱数値を得る。この乱数値をＳ１５０２の示すアドレスを先頭とし変数 iをインデックスとして示す値番目の要素に格納する。つまり、当該乱数値を、Ｓ１５０２の示すアドレスからi個目のメモリ領域に格納している。【００９６】
以上説明した本実施例によれば、図６の処理を他のプログラムからサブルーチンとして呼び出すだけで任意の乱数を発生させることができる。本実施例は完結したサブルーチンとして本発明を実現したものである。【００９７】
［実施例３］【００９８】
実施例３も、擬似乱数の発生を行うプログラムおよび装置である。【００９９】
通常、擬似乱数発生プログラムは一般的には実施例１のごとく提供されるものである。これは汎用性を高めるために、小さな部品単位で提供する思想からである。【０１００】
本実施例は、実施例１を使用してＯＳの上で乱数列をファイルとして保存するアプリケーションプログラムの形式にしたものである。【０１０１】
本実施例の処理の流れは図７により行われる。CPU-S1011が図７の処理を実行することによって、乱数発生装置として機能する。【０１０２】
Ｓ１７００は初期化処理である。４バイト型変数lenと１バイト型の変数ｃを確保している。【０１０３】
Ｓ１７０１は実施例１のプログラムinz()をサブルーチンとして実行している。【０１０４】
Ｓ１７０２はコンソールより乱数表を保存するファイル名を指定する。【０１０５】
Ｓ１７０３はコンソールよりシードとなる数字を入力し、Ｓ１２０１に格納する。【０１０６】
入力できる数値はゼロからＳ１２００の要素数ｎ−１の間である。【０１０７】
Ｓ１７０４はコンソールよりシードとなる数字を入力し、Ｓ１２０３に格納する。入力できる数値はゼロからＳ１２０２の要素数ｍ−１の間である。【０１０８】
Ｓ１７０５はコンソールより乱数表の大きさ、つまり乱数の長さを入力して変数lenに格納する。【０１０９】
Ｓ１７０６は、Ｓ１７０２で入力したファイル名に従いファイルをクリエートしオープンする。【０１１０】
Ｓ１７０７はループ処理である。iは最初ゼロに初期化されており、一回ループするごとにiの値を一つ増加して変数lenの値だけループする。lenの値だけループした後は終了するものである。【０１１１】
Ｓ１７０８は実施例１の乱数発生プログラムｒｎｄ（）をサブルーチンコールしている。帰り値として乱数値を得る。この乱数値を変数ｃに格納する。【０１１２】
Ｓ１７０９は変数ｃの値をＳ１７０６でオープンしたファイルに書き込む。ファイルはHDD-S1030又はUSB装置S1040等の記憶手段に保持される。ファイルへの書き込み位置はループごとに１バイトずつ先頭より後ろにずれる。【０１１３】
Ｓ１７１０はＳ１７０６でオープンしたファイルをクローズする。【０１１４】
以上より本実施例をアプリケーションとして実行しディスクに乱数表をファイルとして保存するものである。【０１１５】
［実施例４］【０１１６】
実施例４も、擬似乱数の発生を行うプログラムおよび装置である。実施例１の一部を変更し、Ｓ１２００の各要素の交換ではなく、各要素の演算により乱数を生成するものである。【０１１７】
構成は実施例１と大半が同一である。ここでは、変更箇所のみを記述する。【０１１８】
図４の関数rnd()の構成において、Ｓ１３０６の処理を変更する。このＳ１３０６において、本実施例では、変数tbl１の示すアドレスの値と、変数tbl2の示すアドレスの値との排他的論理和をとり、変数ｔｂｌ１の示すアドレスのメモリの値として格納するものである。【０１１９】
Ｓ１３０７は削除する。【０１２０】
以上により擬似乱数発生プログラムおよび装置として動作する。【０１２１】
［実施例５］【０１２２】
実施例５も、擬似乱数発生プログラムおよび装置である。本実施例は、実施例２に変更を加えたものである。実施例２では、図６のＳ１６０５において実施例１の関数rnd()を実行している。本実施例では、ここで実行する関数rnd()として、実施例４で開示した変形したrnd()を実行する。【０１２３】
［実施例６］【０１２４】
実施例６も、擬似乱数発生プログラムおよび装置である。実施例６は、実施例３の変形例である。実施例３では、図７のＳ１７０８において、実施例１の関数rnd()を実行している。本実施例では、このＳ１７０８において実行するrnd()として、実施例４で開示した変形したrnd()を実行する。【０１２５】
最後に、以上説明した各実施例のプログラムによるプロセスは、ファームウェアやハードウェアロジックによって実現することも可能である。
【図面の簡単な説明】
【０１２６】
【図１】ホストとなる装置を示した構成図である。
【図２】実施例１における入出力を表した説明図である。
【図３】実施例１における初期化処理の流れを表した流れ図である。
【図４】実施例１における乱数発生処理の流れを表した流れ図である。
【図５】実施例２における入出力を表した説明図である。
【図６】実施例２における乱数発生処理の流れを表した流れ図である。
【図７】実施例３における乱数発生処理の流れを表した流れ図である。
【符号の説明】
【０１２７】
S1011  中央処理装置（ＣＰＵ、処理手段）
S1012  ＲＯＭＢＩＯＳ（記憶手段）
S1013  メモリ装置（記憶手段）
S1014,S10017,S10018  システムバス
S1015,S10016  アダプタ
S1020  ホストＩ／Ｆ
S1030  HDD（記憶手段）
S1019  リーダライタ
S1040  USB装置（記憶手段）
【図１】
2008053936.tif 000003
【図２】
2008053936.tif 000004
【図３】
2008053936.tif 000005
【図４】
2008053936.tif 000006
【図５】
2008053936.tif 000007
【図６】
2008053936.tif 000008
【図７】
2008053936.tif 000009
【手続補正書】
【提出日】平成20年12月5日(2008.12.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
情報の記憶装置と、この記憶装置に格納されn個の要素（nは自然数）を持つメモリテーブルAと、このメモリテーブルAの任意の要素に格納されている値を取り出して、当該値を乱数値として出力する乱数値出力手段と、前記メモリテーブルAの内部の要素を並べ替えるテーブル変更手段とを備えた擬似乱数発生装置において、
前記記憶装置にm個の要素（mは自然数）を持つメモリテーブルBを備え、前記テーブル変更手段は、このメモリテーブルBの要素が持つ数値に従い、前記メモリテーブルAの内部の要素を並べ替える機能を有し、
前記メモリテーブルBの要素が持つ値として、任意の素数を持つようにしたことを特徴とする擬似乱数発生装置。
【請求項２】
前記テーブル変更手段は、前記メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素と内容を入れ替える機能を有し、そのために数値pとして前記メモリテーブルBの素数の値を順次取得する機能を有することを特徴とした請求項１記載の擬似乱数発生装置。
【請求項３】
前記テーブル変更手段は、前記メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先（pは自然数）の要素の持つ数値に従い現在選択している要素の値を変更する機能を有し、そのために数値pとして前記メモリテーブルBの素数の値を順次取得する機能を有することを特徴とする請求項１記載の擬似乱数発生装置。
【請求項４】
請求項１記載の擬似乱数発生装置において、
前記記憶装置に、前記メモリテーブルAの任意の要素を指し示すためのインデックスメモリNを備え、前記テーブル変更手段は、このインデックスメモリNの値が指し示すメモリテーブルAの要素に対して内容の変更を行うことを特徴とした擬似乱数発生装置。
【請求項５】
前記テーブル変更手段は、前記インデックスメモリNにより、メモリテーブルAの内容を変更した後、インデックスメモリNの値を任意の定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリNの値が前記メモリテーブルA の終端以降を指し示す場合、インデックスメモリNの値を前記メモリテーブルAの先頭を指し示す値に変更することを特徴とした請求項４記載の擬似乱数発生装置。
【請求項６】
前記記憶装置は、前記メモリテーブルBの任意の要素を指し示すためのインデックスメモリMを備え、前記テーブル変更手段は、このインデックスメモリMの値が指し示す前記メモリテーブルBの要素を取り出して前記値pとして前記メモリテーブルAの操作を行うことを特徴とした請求項２又は３記載の擬似乱数発生装置。
【請求項７】
前記テーブル変更手段は、前記インデックスメモリMにより、前記メモリテーブルBより値pを取得した後、インデックスメモリMの値を任意の定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリMの値がメモリテーブルB の終端以降を指し示す場合、インデックスメモリMの値を前記メモリテーブルBの先頭を指し示す値に変更することを特徴とした請求項６記載の擬似乱数発生装置。
【請求項８】
請求項４記載の擬似乱数発生装置において、
前記インデックスメモリNの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリNに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項９】
請求項６記載の擬似乱数発生装置において、
前記インデックスメモリMの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリMに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項１０】
請求項１乃至９のいずれかの擬似乱数発生装置において、前記各手段の動作を処理装置に実行させることを特徴とした擬似乱数発生プログラム。
【請求項１１】
請求項１０記載の擬似乱数発生プログラムを記録した媒体。
【手続補正書】
【提出日】平成21年4月28日(2009.4.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
情報の記憶装置と、この記憶装置に格納され複数の要素を持つメモリテーブルAと、このメモリテーブルAの要素に格納されている値を取り出して、当該値を乱数値として出力する乱数値出力手段と、前記メモリテーブルAの内部の要素を並べ替えるテーブル変更手段とを備えると共に、前記記憶装置に複数の要素を持つメモリテーブルBを備え、
前記テーブル変更手段が、このメモリテーブルBの要素が持つ数値に従い、前記メモリテーブルAの内部の要素を並べ替える機能を有する擬似乱数発生装置において、
前記メモリテーブルBの前記複数の各要素が、素数を持つようにし、
かつ、前記テーブル変更手段は、前記メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先の要素と内容を入れ替える機能を有し、そのために数値pとして前記メモリテーブルBの素数の値を順次取得する機能を有することを特徴とした擬似乱数発生装置。
【請求項２】
請求項１記載の擬似乱数発生装置において、
前記記憶装置に、前記メモリテーブルAの任意の要素を指し示すためのインデックスメモリNを備え、前記テーブル変更手段は、このインデックスメモリNの値が指し示すメモリテーブルAの要素に対して内容の変更を行うことを特徴とした擬似乱数発生装置。
【請求項３】
前記テーブル変更手段は、前記インデックスメモリNにより、メモリテーブルAの内容を変更した後、インデックスメモリNの値を定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリNの値が前記メモリテーブルA の終端以降を指し示す場合、インデックスメモリNの値を前記メモリテーブルAの先頭を指し示す値に変更することを特徴とした請求項２記載の擬似乱数発生装置。
【請求項４】
前記記憶装置は、前記メモリテーブルBの任意の要素を指し示すためのインデックスメモリMを備え、前記テーブル変更手段は、このインデックスメモリMの値が指し示す前記メモリテーブルBの要素を取り出して前記値pとして前記メモリテーブルAの操作を行うことを特徴とした請求項１記載の擬似乱数発生装置。
【請求項５】
前記テーブル変更手段は、前記インデックスメモリMにより、前記メモリテーブルBより値pを取得した後、インデックスメモリMの値を定数Kの値だけ加算する機能を備え、当該加算の結果、インデックスメモリMの値がメモリテーブルB の終端以降を指し示す場合、インデックスメモリMの値を前記メモリテーブルBの先頭を指し示す値に変更することを特徴とした請求項４記載の擬似乱数発生装置。
【請求項６】
請求項２記載の擬似乱数発生装置において、
前記インデックスメモリNの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリNに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項７】
請求項４記載の擬似乱数発生装置において、
前記インデックスメモリMの値を本装置の外部より受け付ける手段と、当該受け付けた値をインデックスメモリMに設定する手段とを備えたことを特徴とする擬似乱数発生装置。
【請求項８】
請求項１乃至７のいずれかの擬似乱数発生装置において、前記各手段の動作を処理装置に実行させることを特徴とした擬似乱数発生プログラム。
【請求項９】
請求項８記載の擬似乱数発生プログラムを記録した媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
これを各要素に繰り返し行うと万遍のない要素の入れ替え、好ましいシャッフルが行われる。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】削除
【補正の内容】
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】削除
【補正の内容】
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
本発明は、このようにして例えばリングバッファであるメモリテーブルAに対して素数を利用した要素の交換によりメモリテーブルAをシャッフルする事を特徴とするものである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
即ち、本願発明は、情報の記憶装置と、この記憶装置に格納され複数の要素を持つメモリテーブルAとを備える。また、このメモリテーブルAの要素に格納されている値を取り出して、当該値を乱数値として出力する乱数値出力手段を備える。更に、メモリテーブルAの内部の要素を並べ替えるテーブル変更手段を備える。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
記憶装置には、複数の要素を持つメモリテーブルBを設ける。テーブル変更手段は、このメモリテーブルBの要素が持つ数値に従い、メモリテーブルAの内部の要素を並べ替える。メモリテーブルBの各要素が持つ値としては、任意の素数を持つ。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２２
【補正方法】変更
【補正の内容】
【００２２】
テーブル変更手段は、メモリテーブルAの要素を順番に逐次選択し、現在選択している要素に対してp要素先の要素と内容を入れ替える。この場合、数値pとしてメモリテーブルBの要素の値、即ち素数を順次取得する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２３
【補正方法】削除
【補正の内容】
【国際調査報告】
2008053936.tif 000010
2008053936.tif 000011