(57)【要約】      （修正有）【課題】十分な長周期と高精度とを持ち、出力数の連の与える点列は統計的に棄却すべき対称性を免れ、かつ検定による性能保障を伴う一様独立乱数列の新しい生成方法を提供する。【解決手段】奇素数ｐ１とｐ２をｑ１＝（ｐ１−１）／２およびｑ２＝（ｐ２−１）／２が互いに素で異なる偶奇性を持つように取り、法ｐ１でのすべての原始根を掃過する６次スペクトル検定での最良の原始根ｚ１、および法ｐ２での同様のスペクトル検定での最良の原始根ｚ２を選ぶ。連立合同式ｚ≡ｚ１ｍｏｄ（ｐ１）、ｚ≡ｚ２ｍｏｄ（ｐ２）で中国剰余定理が定めるｚを乗数として、合成数の法ｄ＝ｐ１×ｐ２の単独スペクトル検定を望む次数Ｌ（３≦Ｌ≦６）まで行い、合格ならば法ｄ、乗数ｚ、周期Ｔ＝２ｑ１ｑ２、そして生成される数の任意個数の連の作る点が対称性を持たない乗算合同法を、Ｌ次スペクトル検定の性能保証と共に得る。【選択図】なし【特許請求の範囲】
【請求項１】
正の整数の法ｄ、正の整数の乗数ｚで法ｄとは素なもの、そして正の整数ｎ１で法ｄとは素な初期値、で与えられる乗算合同法乱数生成方法、即ちｋ＝１、２、・・・に対してｎｋから次のｎｋ＋１を線形漸化合同式
【数１】
2010040021.tif 000005
で０＜ｎｋ＋１＜ｄとなるように定めて得られる整数列ｎ１、ｎ２、・・・から一様独立乱数列ｕ１、ｕ２、・・・を除法
【数２】
2010040021.tif 000006
によって与える方法であり、かつ上記法ｄが２つの異なる奇素数ｐ１、ｐ２の積ｄ＝ｐ１×ｐ２である方法。
【請求項２】
請求項１の奇素数ｐ１およびｐ２は整数ｑ１＝（ｐ１−１）／２およびｑ２＝（ｐ２−１）／２が互いに素で、１つが偶数、他が奇数となるもの。
【請求項３】
請求項１の乗数ｚは、請求項１の奇素数ｐ１を法とする原始根ｚ１、及び請求項１の奇素数ｐ２を法とする原始根ｚ２から連立合同式
【数３】
2010040021.tif 000007
を満たすものとして中国剰余定理が法ｄの意味で一意の存在を保証する解ｚであるもの。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は一様独立乱数生成方法に係る。さらに詳しくは自然数の法ｄ、前記ｄとは素な、すなわちｄとは共通素因数２、３、５、・・・を持たない自然数の乗数ｚ≧２、そして前記法ｄとは素な自然数の初期項ｎ１に基づいて自然数の列｛ｎ１、ｎ２、・・・｝を生成する乗算合同法、すなわちｎｋのｚ倍をｄで割った余りを次の整数ｎｋ＋１とし、ｋ＝１、２、・・・に対して実数列｛ｕｋ＝ｎｋ／ｄ｝を一様独立乱数列の出力とする乱数生成方法、に関する。
【背景技術】
【０００２】コンピュータ上の一様独立乱数生成方法は再現性と移植可能性を求められる。再現性とはユーザの求めに応じ同一の乱数列を必要な回数だけ再発生し得る性質である。また移植可能性は生成方式を他のコンピュータに移し或いは他のプログラム言語に移植しても、全く同一の乱数列を発生する事を言う。これらはシミュレーションなど乱数列を用いるプログラムの作成、デバッグに必須である。【０００３】前項０００２の要件はコンピュータ上の乱数生成方式に、下位の桁の切り捨てによる打切り誤差や、四捨五入による丸めの誤差などの扱いに統一した規格のない実数演算ではなく、それら誤差の存在しない整数演算のみを用いて次々に整数列を生成する事、実数演算は整数列の正規化に限る事、を求める。そのような方式の１つである乗算合同法は非特許文献１（１９５１）で始められた。それは整数列ｎ１、ｎ２、・・・を漸化合同式
【数４】
2010040021.tif 000002
で生成する。ここでｄは正の整数で法、ｚは２以上の整数で乗数、とそれぞれ呼ばれ、数４の合同式は前段の整数ｎｋと整数ｚとの積ｚｎｋを法の整数ｄで割った余りをｎｋ＋１とする事を意味する。ｎ１とｚはともにｄとは素に選ばれ、すべての番号ｋ＝１、２、・・・でｎｚｋは分母ｄで割り切れることはなく、常に０＜ｎｋ＜ｄが成り立つ。一様独立乱数列としては０＜ｕｋ＜１と正規化された実数ｕｋ＝ｎｋ／ｄがｋ＝１、２、・・・に対して用いられる。【０００４】従来の乗算合同法は２つの形の法を用いる。１つは大きい素数の法ｄ＝ｐを取り、素数ｐに対する原始根ｚを乗数に選ぶ。すなわちｚのベキの列を法ｄ＝ｐで（言い換えるとｄ＝ｐで割った余りの意味で１、２、・・・に）値を定めた巡回列と呼ばれる数列＜ｚ＞≡｛１、ｚ、ｚ２、・・・｝ｍｏｄ（ｐ）が理論上最大の周期ｐ−１を持つ、すなわち素数の法ｄ＝ｐと素な整数｛１、２、・・・、ｐ−１｝を１度ずつすべて巡る構造のものである。このとき法ｄ＝ｐと素な任意の初期値ｎ１に対して、巡回列＜ｚ＞のｎ１に関する剰余類、と呼ばれる列ｎ１＜ｚ＞≡｛ｎ１、ｎ１ｚ、ｎ１ｚ２、・・・｝ｍｏｄ（ｐ）は巡回列＜ｚ＞の出発点の取り方の違いに相当するだけのものとなり、乗算合同法乱数列は初期値ｎ１に関係しない同一で最長の周期ｐ−１を持つ。今１つは法をｄ＝２ｉ（ｉ≧４）とし、ある整数ｍでｚ＝８ｍ＋５と表される奇数ｚ、すなわち法８で５に合同なｚ、を乗数とする構成である。この後者の法ｄと乗数ｚの場合も、ｚの作る乗算合同法乱数列は法と素な（すなわち奇数の）初期値ｎ１の選択に関係しない理論的に可能な最大値である周期２ｉ／４＝２ｉ−２を持つ。すなわちｎ１が法８で１あるいは５と合同な場合には剰余類の列ｎ１＜ｚ＞は法８で１および５と合同な総数２ｉ／４の奇数すべてを１度ずつ巡り、残るｎ１が法８で３あるいは７と合同な場合には同数２ｉ／４の法８で３および７と合同な奇数のすべてを１度ずつ巡る構造を実現する。【０００５】段落０００４のどちらの法ｄと対応する乗数ｚの選択でも、生成される列の相続く数の分布、すなわち目指す相続く数の独立性の実現度、は乗数ｚの取り方によって非常に大きく性質を変える。その中から優れた乗数ｚを選ぶ最も信頼できる技術としてスペクトル検定が案出され、非特許文献２（１９８６）の掃過的スペクトル検定、すなわち素数の法ｄ＝ｐ＝２３１−１でのあらゆる原始根ｚを掃過比較する性能テスト、による最優秀乗数の選定でその頂点を見た。また非特許文献３（１９９０）では法ｄ＝２３２でのすべての可能な乗数ｚ≡５ｍｏｄ（８）の掃過的なスペクトル検定と、法２４８での部分掃過的なスペクトル検定が実施された。発見された優れた乗数の割合は法２３１−１では７．５×１０−５％、他の法でも同程度以下であった。これらの結果は個別的な検定を経ずに乗数ｚを決定してよい生成方式を得る確率は大変小さいこと、検定を経ない乗数では信頼に足る乱数生成方法は実現できないことを示した。これはまた、乗算合同法一様独立乱数の周期の実用的上限は掃過的スペクトル検定が計算可能なｄの最大値以下である、という工学技術的限界の存在を明らかにした。なお１９９０年当時と現在のコンピュータ速度を比べて、現在���は法ｄ＝２４８での掃過的スペクトル検定は可能、と見積もられている。【０００６】乗算合同法のスペクトル検定の法ｄ＝２ｉの場合は少し異なる方式となり、また合成数の法の成分としては実用に不適合な障害を持つので除く。奇素数の法ｄ＝ｐの場合、および本発明の法ｄが奇素数の積である場合には、行うべき計算は次の簡単な形に要約される。法ｄおよび乗数ｚに対してＬ次元行ベクトルのＬ個の組を考える：
【数５】
2010040021.tif 000003
これらのベクトルの任意整数係数倍の和で作られるベクトルの中で、０ではない最小の正の長さを持つものを発見し、その長さκｄ（Ｌ）（ｚ）を求める事が乗数ｚの法ｄでのＬ次スペクトル検定である。得られる数κｄ（Ｌ）（ｚ）が大きいほど、乗数ｚの性能は高いと評価される。この簡明な探索が素数の法ｄ＝ｐでの原始根乗数ｚの場合ばかりでなく、本発明の関わるより一般の、例えば奇素数の積の法ｄ＝ｐ１ｐ２の場合でも有効であること、それが素数の法の場合とは少し異なる検定内容を持つことは発明の開示の文献１で、そしてｄによって定まる検定に必要な計算量の比較は発明の開示の文献２において明らかにされた。これらの発見によって、現在ではスペクトル検定が、合成数の法の場合も含めて、どのような検定内容と結果を与えるか、検定に要する計算量はどれほどか、の理解は得られている。【０００７】現在ー様独立乱数として利用可能な最も長い周期は、形は異なるが数理的には素数の法での原始根の巡回列に近い構造に基づく非特許文献４（１９９４）で与えられたメルセンヌツイスターの２１９９３７±３２＞１０５９９１である。メルセンヌツイスターはその周期の巨大さのためあらゆる検定が困難であり、生成される乱数列の性質について、特にパソコンから現在のスーパーコンピュータ上で重要と思われる１０２２程度の長さでの出力乱数の分布について、理論的な保障が存在しない。何らかの検定を確立する事は急務であるが、それは極めて難しい問題で未だ解決を見る事ができない。【０００８】段落０００７の状況の大きな転換は非特許文献５、６（２００４）において発見された。発明の開示の文献１、２にも述べられたとおり、０からｚ−１までの値を取る整数の作る任意の列の十分な長さＴの部分について、その各数は（素数ｐや２ｉの形とは限らない）一般の自然数の法ｄ、そしてｄと素な適当な乗数ｚに基づく乗算合同法数列の対応する数で一様な誤差１／ｚで近似される、という認識から得られた。この発見は、一様独立乱数列が自然物理現象に基づくものであろうと、或いはどのような計算方式に基づいて生成されたものであろうとすべて、素数と限らない合成数ｄを法とする乗算合同法の数列として近似表現される、という事実を示すものである。認識は乗算合同法乱数発生方法の法の合成数への一般化に対応する数理構造の再考と、乗数の新しい選択基準の発見とを迫るものとなった。本特許に関わる研究は、この動機から誘発された。
【非特許文献１】Ｄ．Ｈ．Ｌｅｈｍｅｒ，“Ｍａｔｈｅｍｔｉｃａｌ  ｍｅｔｈｏｄｓ  ｉｎ  ｌａｒｇｅ  ｓｃａｌｅ  ｃｏｍｐｕｔｉｎｇ  ｕｎｉｔｓ．”Ａｎｎａｌｓ  Ｃｏｍｐ．Ｌａｂ．Ｈａｒｖａｒｄ，Ｖｏｌ．２６（１９５１），ｐｐ．１４１−１４６．
【非特許文献２】Ｇ．Ｓ．Ｆｉｓｈｍａｎ  ａｎｄ  Ｌ．Ｒ．Ｍｏｏｒｅ，“Ａｎ  ｅｘｈａｕｓｔｉｖｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａ−ｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓ  ２▲３１▼−１．”ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｃｉｅｎｔｉｆｉｃ  ａｎｄ  Ｓｔａｔｉｓｔｉｃａｌ  Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．７（１９８６），ｐｐ．２４−４５．
【非特許文献３】Ｇ．Ｓ．Ｆｉｓｈｍａｎ，“Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓ  ２▲β▼：Ａｎ  ｅｘｈａｕｓｔｉｖｅ  ａｎａｌｙｓｉｓ  ｆｏｒ  β＝３２  ａｎｄ  ａ  ｐａｒｔｉａｌ  ａｎａｌｙｓｉｓ  ｆｏｒ  β＝４８．”Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎ，Ｖｏｌ．５４（１９９０），ｐｐ．３３１−３３４．
【非特許文献４】Ｍ．Ｍａｔｓｕｍｏｔｏ  ａｎｄ  Ｔ．Ｎｉｓｈｉｍｕｒａ，“Ｍｅｒｓｅｎｎｅ  Ｔｗｉｓｔｅｒ；Ａ  ６２３−ｄｉｍｅｎｓｉｏｎａｌｌｙ  ｅｑｕｉｄｉｓｔｒｉｂｕｔｅｄ  ｕｎｉｆｏｒｍ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒ．”ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｓｉｍｕｌａｔｉｏｎ，Ｖｏｌ．４（１９９４），２５４−２６６．
【非特許文献５】Ｈ．Ｎａｋａｚａｗａ，“Ｃｏｓｅｔ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ｕｎｉｒｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｓｅｑｕｅｎｃｅｓ  Ｉ．Ｃｏｓｅｔｓ  ａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ  ｐｅｒｉｏｄｉｃ  ｓｅｑｕｅｎｃｅｓ，”（Ａｕｇｕｓｔ，２００４，インターネット発表），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
【発明の開示】
［１］中澤  宏，中澤直也，“長周期で高精度の一様独立乱数の設計：数の連が作る点列幾何の直積群構造及び格子構造に基づく制御．”（Ｍａｒｃｈ  ９，２００８，インターネット発表），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
［２］Ｈ．Ｎａｋａｚａｗａ  ａｎｄ  Ｎ．Ｎａｋａｚａｗａ，“Ｄｅｓｉｇｎｓ  ｏｆ  Ｕｎｉｆｏｒｍ  ａｎｄ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｒａｎｄｏｍ  Ｎｕｍｂｅｒｓ  ｗｉｔｈ  Ｌｏｎｇ  Ｐｅｒｉｏｄ  ａｎｄ  Ｈｉｇｈ  Ｐｒｅｃｉｓｉｏｎ．”（Ｍａｒｃｈ  ９−Ｊｕｌｙ  ８，２００８，インターネット発表），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
【発明が解決しようとする課題】
【０００９】この発明は上記段落０００８の発見に基づき、段落０００７の状況の改善を目指してなされた。目標は乗算合同法の法ｄを一般の合成数に拡張して、検定を伴う一様独立乱数列をコンピュータとシミュレーションの現状から望まれる１０２２以上の周期に対して実現可能とすることである。それは同時に、考え得る乱数生成方式の中で計算負荷が最小限の四則算法の利用によって、実装上最も計算の負荷が軽くかつ高速に演算を行う乱数生成方式を得る事も意味する。
【００１０】段落０００９の示唆によって乗算合同法の法ｄをこれまでの制限、ｄが素数であるかあるいは２の高次べきｄ＝２ｉであるか、を越えて一般化することは、ｄと素な整数全体が構成する既約剰余群やその部分群と呼ばれる構造の中で出力乱数の一様分布を実現する簡明な機構、すなわち乗数ｚが生成する巡回列＜ｚ＞≡｛１、ｚ、ｚ２、・・・、ｚｋ、・・・｝が法ｄの整数の全体（から無視できる少数を除いたもの）を１周期に１度ずつ必ず巡る、という意味の巡回性から離れなければならないことを意味する。言い換えれば解決されるべき課題は、この一様性、独立性を合成数の法ｄで得る新しい乗算合同法の数理構造の発見とその利用方法の発明である。
【００１１】段落００１０の一様性などの確保の問題とは別に、乱数の相続く連を座標とする空間の点と対応させるとき、生成される点の全体が空間で持つ分布について、段落０００４で説明された在来の乗算合同法にはなかった新しい問題が合成数の法では生じる。在来の乗算合同法での出力乱数列の合い続くＬ個の連をＬ次元空間の点の座標と考えれば、生成される点列は分布の一様性、独立性からは極めて低い確率でしか起き得ない対称性を持つ場合が多い。しかし単独奇素数の法の場合には問題を避けた出力乱数の簡明な利用方法、すなわち周期の小部分、高々１／２以下、の利用への制限、が対策として機能し、この対称性の問題は余り考慮の必要がなかった。しかし法ｄが合成数となると、このような簡便な対策では出力乱数列一様性の確保やスペクトル検定の効力と絡む性能の劣化が不可避となる。法の合成数への拡張を出力乱数の分布統計が在来の乗算合同法と同等以上の精度を持つように得るには、新しい構造理解を見出すこと、非蓋然的な対称性を制御し排除する工学技術設計の発見、が必須の課題である。
【課題を解決するための手段】
【００１２】２つの異なる奇素数ｐ１、ｐ２をあまり値が近接せず、それらが作る整数ｑ１＝（ｐ１−１）／２、ｑ２＝（ｐ２−１）／２が偶数と奇数の組でかつ互いに素となる、すなわち共通素因数を持たない、ように選び、積ｄ＝ｐ１ｐ２を法と定める。
【００１３】奇素数の法ｐ１ですべての原始根を掃過するスペクトル検定を行い、最上の性能の原始根乗数ｚ１を数個選ぶ。同様に奇素数の法ｐ２ですべての原始根を掃過するスペクトル検定を行い、最良の性能の原始根乗数ｚ２を数個選ぶ。
【００１４】合成数の法ｄ＝ｐ１ｐ２の乗算合同法の乗数ｚとして、連立合同式
【数６】
2010040021.tif 000004
を満たすｚを中国剰余定理で求める。具体的にはｐ１とｐ２が互いに素である事に基づき１＝Ｑ１ｐ１＋Ｑ２ｐ２を満たす整数の任意の組Ｑ１、Ｑ２をユークリッドの互除法等で求め、整数Ｑ２ｐ２ｚ１＋Ｑ１ｐ１ｚ２から２≦ｚ＜ｄの範囲で唯一の整数ｚ≡Ｑ２ｐ２ｚ１＋Ｑ１ｐ１ｚ２を法ｄで（割った余りとして）得る。
【００１５】段落００１４で構成された乗数ｚのベキの値を法ｄ＝ｐ１ｐ２で０からｄ−１までに定めた巡回列＜ｚ＞≡｛１、ｚ、ｚ２、・・・、ｚｋ、・・・｝ｍｏｄ（ｄ）の周期は、２成分ベクトルの列｛（１、１）、（ｚ１、ｚ２）、（ｚ１２、ｚ２２）、・・・、（ｚ１ｋ、ｚ２ｋ）、・・・｝と同じ周期であり、それは段落００１２のｐ１、ｐ２の定め方によってｐ１−１＝２ｑ１とｐ２−１＝２ｑ２の最小公倍数のＴ＝２ｑ１ｑ２となる。この単独乗数ｚに対する合成数の法ｄ＝ｐ１ｐ２でのスペクトル検定は、計算時間の問題は別にして、発明の開示の文献１、２で示された所により単一の素数の法での原始根乗数の性能評価と完全に同じ意味の評価を与え、その手続きは段落０００６に記された通りである。ｚに施すべき検定次数Ｌを検定計算が許容時間内に可能となるようにＬ＝３、４、５、６の中から選ぶ。ｚ単独に対して合成数の法ｄ＝ｐ１ｐ２でのＬ次スペクトル検定を行い、得られた評価κｄ（Ｌ）（ｚ）が十分大きければ（非特許文献２での採択基準はκｄ（Ｌ）（ｚ）の逆数が理想値の１２５％以内）ｚを乗数として採択し、法ｄ＝ｐ１ｐ２、乗数ｚ、周期Ｔ＝２ｑ１ｑ２＝（ｐ１−１）（ｐ２−１）／２の乗算合同法一様独立乱数生成方法を得る。検定結果κｄ（Ｌ）（ｚ）が望む範囲内ではなければ棄却し、ｚ１の法ｐ１での逆数とｚ２との組み合わせ、異なるｚ１やｚ２の組み合わせ、あるいは異なるｐ１やｐ２の積の法、を試みる。
【００１６】上記段落００１２−００１５の手順は、実際は００１５での検定次数Ｌを第１に決定して始める。もしＬ＝４、５、６を望むなら、まず法ｄをＬ次の単独スペクトル検定が計算可能な大きさに定める。ｄはＬの減少と共に増大する。次にｐ＝ｄ１／２の程度の大きさの奇素数ｐ１およびｐ２を段落００１２の選択として行う。これらそれぞれを法とする６次の掃過的スペクトル検定は、計算量から一般的に計算可能性が予測（特にｐ＝ｄ１／２が２４８以下であれば掃過的スペクトル検定の可能性は実際保障）され、段落００１３−００１５の手続きがすべて遂行される。こうして、段落００１２−００１５の計算手順は法ｄ＝ｐ１ｐ２での掃過的スペクトル検定で必要となる計算量を大幅に軽減する計算上経済的な手段を与える。
【００１７】上記段落００１５の検定次数ＬがＬ＝３でよいなら、段落００１３での６次掃過的スペクトル検定が計算可能な素数の最大値をｐと定めて、奇素数ｐ１、ｐ２をこのｐの程度の大きさで余り近接しない値に取る。その後段落００１３−００１５の手順を行えば、段落００１５での法ｄ＝ｐ１ｐ２、乗数ｚの単独Ｌ次スペクトル検定の計算量は段落００１３の掃過的スペクトル検定よりも計算量は小さく、検定次数Ｌを３と小さく取る限定ともあいまって計算手順は大幅に平易化され、遂行される。現在のコンピュータでは段落００１２での奇素数ｐ１、ｐ２のそれぞれを大きさで２４８＝１０１４．４５程度までに取れば、掃過的スペクトル検定の計算可能性は保障される。また合成された法ｄ＝ｐ１ｐ２、乗数ｚの乗算合同法は、段落００１５に述べられた通り、周期としてＴ＝２ｑ１ｑ２＝（ｐ１−１）（ｐ２−１）／２を持つ。従って段落００１４での単独スペクトル検定次数をＬ＝３でよいとすれば、得られる周期の大きさは十分に大きくなる。
【００１８】奇素数ｐ１とｐ２をｑ１＝（ｐ１−１）／２とｑ２＝（ｐ２−１）／２が互いに素になるように段落００１２で選ぶ事によって、合成数の法ｄ＝ｐ１ｐ２と段落００１３−００１４で定められた乗数ｚによる乗算合同法乱数は理論限界内最大の周期Ｔ＝（ｐ１−１）（ｐ２−１）／２＝２ｑ１ｑ２を得る。この周期は巡回列＜ｚ＞≡｛１、ｚ、ｚ２、・・・、ｚｋ、・・・｝ｍｏｄ（ｄ）とその剰余類とが法ｄ＝ｐ１ｐ２と素な整数の作る群を正確に２分する構造を与える。
【００１９】さらに段落００１２で選ばれた異なる奇素数ｐ１とｐ２が同じ段落のｑ１とｑ２を一方は偶数、他方は奇数と定める事は、発明の開示１、２で示されたとおり、積の法ｄ＝ｐ１ｐ２で生成される乱数列の相続く任意個数Ｌ≧２の連をＬ次元ユークリッド空間の点の座標と見るとき、これら点の集合が初期値ｎ１やＬの選択に関係なく、統計的に不自然な対称性を持たない事を保障する。これは単一の素数ｐを法とする原始根の乗数ｚの巡回列が、発明の開示１、２で示されたように、その任意の相続くＬ連を座標とする点列が持つ対称性のために、全周期（１、２、・・・、ｐ−１と合同な数のすべて）ではなくその正確な１／２のみ乱数として用いる事ができる、残る１／２は使う事ができない、という状況と完全に同等の構造を現出する。すなわち、数５のベクトルの整数係数１次結合で作られる最短ベクトルを求めて得られるスペクトル検定が、従来の単一素数の法の原始根乗数の乗算合同法に対するスペクトル検定と完全に同じ効力を発揮して、生成される数の分布の一様性や相続く数の統計的独立性についての判定を与える。
【発明を実施するための最良の形態】
【００２０】段落００１９に記された本特許で請求する合成数の法の簡単な結果例を図１に示す。これは法ｄ＝２８６７＝４７×６１、乗数としてｚ＝６７８（法４７でｚ≡２０、法６１ではｚ≡７）、初期値ｎ１＝１の乗算合同法乱数列の数の２連を２次元平面でのｘｙ座標（ｎｋ＋１／ｄ、ｎｋ／ｄ）とする点の１周期Ｔ＝１３８０にわたるプロットを示す。ｑ１＝（ｐ１−１）／２＝２３、ｑ２＝（ｐ２−１）／２＝３０が偶奇性を異にするので、図は発明の開示１、２で示されたように正方形の中心に関して対称性を持たず、乱数として出現確率の低さを疑わせないものが実現し、全周期の使用を妨げる非蓋然性は見られない。外枠はたて、横軸とも−０．０５から１．０５までを表す。巡回列＜ｚ＞およびそれと同数で共通な数のない剰余類からの２連の作る点を共に示した図２では１からｐ１ｐ２−１までの中にあるｐ１あるいはｐ２の倍数、総数でｐ１＋ｐ２−２＝１０６個、の欠損が見える。スペクトル検定はこれらの欠損と０も含めたｄ＝ｐ１ｐ２個の点の全体配置を評価する。＜ｚ＞あるいはその剰余類は評価される点全体のほぼ１／２であり、単一の奇素数を法とする原始根の作る巡回列で可能な使用法と完全に同じでスペクトル検定の効力も高く、図２のほぼ完全な一様分布状況の１／２の点を用いるものとして一様性の不安はない。請求項１−３が与える構成、すなわちｑ１、ｑ２が異なる偶奇性を持つように奇素数ｐ１とｐ２を選ぶことは最良の乗算合同法の形態を与える。【００２１】段落００１９の指摘を外れた状況、すなわち２つの奇素数ｐ１、ｐ２が共に奇数のｑ１＝（ｐ１−１）／２、ｑ２＝（ｐ２−１）／２を与える場合の例は図３−５に見られる。これらは合成数の法ｄ＝２５３７＝４３×５９、乗数ｚ＝４８５、即ち法４３でｚ≡１２、法５９でｚ≡１３の場合で、共にそれぞれの法で優れた原始根乗数である。ｑ１＝（ｐ１−１）／２＝２１、ｑ２＝（ｐ２−１）／２＝２９が共に奇数なので、図は発明の開示１、２が示すように正方形の中心に関して対称になり、一様独立乱数と考えると蓋然性の低いものが実現している。初期値はｎ１＝１（法４３でも法５９でもｎ１≡１）である。図３−５は一様独立乱数列出力の２連を平面の点の座標（ｎｋ＋１／ｄ、ｎｋ／ｄ）とするプロットで、外枠はたて横軸とも−０．０５から１．０５を表す。図３は巡回列＜ｚ＞の周期Ｔ＝２ｑ１ｑ２＝１２１８の１／２まで取った点列を示す。図４は１周期の点列の姿である。巡回列＜ｚ＞とそれに入らない数ｎ１に対する剰余類ｎ１＜ｚ＞からの数の２連が与える点をすべて記したものが図５である。図５の点全体は、ｐ１とｐ２の倍数、総数ｐ１＋ｐ２−２＝１００、に相当する空席以外は正方形を均等に埋め尽くす。乗算合同法巡回列＜ｚ＞で実現される図４の点分布がその半分である事は段落００２１と同様で、これが乱数列として採択できれば空間を一様に満たす点列の１／２として一様性の観点からは問題はなくなる。しかし図４の点集合の正方形の中心に関する対称性は非蓋然的な相関を示すものであり、乱数列としての仮説は却下され採択できない。そのさらに１／２に限った図３の点は、一様とは言えない分布を持つ図４の点集合の１／２であるから、一様性に信頼が置けな��。一様独立乱数列として、この図３の点列を生成する乱数列を用いることは好ましくない。明らかに、請求項１−３の構成は２つの奇素数の積の法での最良の形態を与えている。【００２２】段落００１２の異なる奇素数ｐ１、ｐ２は、例えば双子素数のように近接したものは避けて選ぶ。これによって段落００１４で構成される乗数ｚの性能の悪化、成分乗数ｚ１とｚ２のベキのそれぞれの法での周期の近接による唸りあるいはモワレ縞の様な現象、をスペクトル検定を経ずに予知して、計算量の増大を避ける事ができる。【００２３】段落００１２−００１５の手順は段落００１２において異なる奇素数ｐ１とｐ２の１つ、例えばｐ２を２ｉの形で置き換えても遂行可能である。しかし発明の開示の文献１、２で初めて指摘したように、この選択は残る奇素数ｐ１のベキのすべての偶数乗の間、すべての奇数乗の間に相関を惹き起こし、ｚが生成する乗算合同法数列の独立性を大きく毀損する。特にこの悪い性質はスペクトル検定では検知できないので、この様な選択は決して行ってはならない。【００２４】段落００１２−００１５の手順は段落００１２において３以上のｓ個の異なる奇素数ｐ１、ｐ２、・・・、ｐｓを、ｑｊ＝（ｐｊ−１）／２がｊ＝１、２、・・・、ｓのすべてについて互いに素でその中の１つは偶数であり他はすべて奇数、を満たすように選んで作られる合成数の法ｄ＝ｐ１ｐ２・・・ｐｓでも考え得る。実際ｊ＝１、２、・・・、ｓのそれぞれについて、法ｐｊでの掃過的スペクトル検定で得られる優れた原始根乗数ｚｊを採り、乗数ｚをｊ＝１、２、・・・、ｓのそれぞれについてｚ≡ｚｊｍｏｄ（ｐｊ）によって中国剰余定理で定まるものとすれば、法ｄ＝ｐ１ｐ２・・・ｐｓで乗数をｚとする乗算合同法は周期Ｔ＝２ｑ１ｑ２・・・ｑ２を獲得し、巡回列＜ｚ＞やその剰余類のＬ連が作る点はＬ次元空間で非蓋然的な対称性を持たないものとなる事が特許の開示１、２で示されている。しかしこの場合巡回列＜ｚ＞は法ｄとは素な数全体の１／２ｓ−１の部分しか占めず、一方段落０００６の数５と同じベクトルが与える最短長さの探索で得られるスペクトル検定はｄと素な数の全体を含む座標を持つ点の配置を評価する。ゆえにｓ≧３の増大と共に検定の有効性は小さくなり、一方周期Ｔを増大させる事はスペクトル検定の計算可能性で限界を与えられていて実利は薄い。この意味からも請求項１−３のように２つの異なる奇素数の積の法を用いる構成は最良の技術的選択である。
【産業上の利用可能性】
【００２５】構成された乗算合同法は、すべての乱数生成方法の中で最も高速な四則演算の最小回数の利用で構成されるため、コンピュータに与える計算負荷は乱数のすべての生成方式の中で最小で、従って最高速での乱数生成を保障する。任意の乱数列を近似する能力とこの計算上の最良性は、本発明の産業上科学技術上の大きな利用可能性、必要性を意味する。【００２６】目的とする法ｄに対し段落００１６での検定次数Ｌの選択を６とする場合、段落００１２で選ぶ奇素数ｐ１、ｐ２をｄ１／２の大きさとする事によって法ｄ＝ｐ１ｐ２でのよい乗算合同法乱数生成方法を準備するための計算量は従来の法ｄでの掃過的検定の計算量に比べて大幅に縮小される。この計算上の経済的効果は大きく、本発明の産業科学技術上の利用可能性は大きい。【００２７】目的とする法ｄに対して段落００１６での検定次数Ｌを３と選ぶ場合、段落００１３で掃過的検定が計算可能な最大の奇素数ｐ１とｐ２を、例えば２４８程度の大きさ、に選ぶ事によって、得られる法ｄ＝ｐ１ｐ２の下で達成される周期は極めて大きくなる。このような長周期で検定を経た一様独立乱数列の使用可能性は計算上の大きな進歩であり、本発明の産業科学技術上の利用可能性は極めて大きい。
【図面の簡単な説明】
【図１】本特許で請求する合成数の法で乗算合同法乱数列が生成する２連の平面の点としての全周期Ｔ＝１３８０のプロット。法ｄ＝２８６７＝４７×６１、乗数ｚ＝６７８、周期Ｔ＝１３８０、初期値１。正方形の中心に関して非対称。
【図２】図１の乱数列上に、これらに属さない剰余類からの乱数列の２連の点列を加えた全体。空席１０６個は４７および６１の倍数の座標に相当。
【図３】本特許の請求項から外れる合成数の法ｄ＝２５３７＝４３×５９、乗数ｚ＝４８５、初期値１の乗算合同法乱数列の２連の半周期の平面図。
【図４】図３と同じ法ｄ＝２５３７、乗数ｚ＝４８５での乱数列の２連の点の全周期Ｔ＝１２１８にわたるプロット。正方形の中心に関して対称。
【図５】図４の上に乱数列に属さない剰余類からの２連が作る点列を加えた全体４３および５９の倍数を座標とする１００個の点が空席。
【図１】
2010040021.tif 000008
【図２】
2010040021.tif 000009
【図３】
2010040021.tif 000010
【図４】
2010040021.tif 000011
【図５】
2010040021.tif 000012
【手続補正書】
【提出日】平成20年11月29日(2008.11.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２つの異なる奇素数ｐ１、ｐ２の積である正の整数ｄ＝ｐ１×ｐ２を法とし、正の整数ｚで法ｄとは素な乗数、および正の整数ｎ１で法ｄとは素な初期値、で定められる乗算合同法乱数生成方法であって、さらに下記の［要件１］および［要件２］を共に満たす一様独立乱数生成方式。即ちｋ＝１、２、・・・のｎｋから順次に次のｎｋ＋１を線形漸化合同式
【数１】
2010040021.tif 000013
を満たし、かつ０＜ｎｋ＋１＜ｄとなるように定め、得られる整数列ｎ１、ｎ２、・・・に対して一様独立乱数列ｕ１、ｕ２、・・・を除法等式
【数２】
2010040021.tif 000014
を満たすように与えるものであって、さらに下記の［要件１］及び［要件２］を共に満たす一様独立乱数生成方式。
［要件１］請求項１の奇素数ｐ１およびｐ２は整数ｑ１＝（ｐ１−１）／２およびｑ２＝（ｐ２−１）／２が互いに素で、１つが偶数、他が奇数となるもの。
［要件２］請求項１の乗数ｚは、請求項１の奇素数ｐ１を法とする原始根ｚ１、及び請求項１の奇素数ｐ２を法とする原始根ｚ２から連立合同式
【数３】
2010040021.tif 000015
を満たすものとして中国剰余定理が法ｄの意味で一意の存在を保証する解ｚであるもの。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００８
【補正方法】変更
【補正の内容】
【０００８】
段落０００７の状況の大きな転換は非特許文献５、６（２００４）において発見された。発明の開示の文献１、２にも述べられたとおり、０からｚ−１までの値を取る整数の作る任意の列の十分な長さＴの部分について、その各数は（素数ｐや２ｉの形とは限らない）一般の自然数の法ｄ、そしてｄと素な適当な乗数ｚに基づく乗算合同法数列の対応する数で一様な誤差１／ｚで近似される区間［０、１）の数列を与える、という認識から得られた。この発見は、一様独立乱数列が自然物理現象に基づくものであろうと、或いはどのような計算方式に基づいて生成されたものであろうとすべて、素数と限らない合成数ｄを法とする乗算合同法の数列によって近似表現される、という事実を示すものである。認識は乗算合同法乱数発生方法の合成数への一般化に対応する数理構造の再考と、乗数の新しい選択基準の発見とを迫るものとなった。本特許に関わる研究は、この動機から誘発された。
【非特許文献１】Ｄ．Ｈ．Ｌｅｈｍｅｒ，“Ｍａｔｈｅｍｔｉｃａｌ  ｍｅｔｈｏｄｓ  ｉｎ  ｌａｒｇｅ  ｓｃａｌｅ  ｃｏｍｐｕｔｉｎｇ  ｕｎｉｔｓ．”Ａｎｎａｌｓ  Ｃｏｍｐ．Ｌａｂ．Ｈａｒｖａｒｄ，Ｖｏｌ．２６（１９５１），ｐｐ．１４１−１４６．
【非特許文献２】
2010040021.tif 000016
【非特許文献３】
2010040021.tif 000017
【非特許文献４】Ｍ．Ｍａｔｓｕｍｏｔｏ  ａｎｄ  Ｔ．Ｎｉｓｈｉｍｕｒａ，“Ｍｅｒｓｅｎｎｅ  Ｔｗｉｓｔｅｒ；Ａ  ６２３−ｄｉｍｅｎｓｉｏｎａｌｌｙ  ｅｑｕｉｄｉｓｔｒｉｂｕｔｅｄ  ｕｎｉｆｏｒｍ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒ，”ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍｏｄｅｌｉｎｇ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ｓｉｍｕｌａｔｉｏｎ，Ｖｏｌ，４（１９９４），２５４−２６６．
【非特許文献５】Ｈ．Ｎａｋａｚａｗａ，“Ｃｏｓｅｔ  ｒｅｐｒｅｓｅｎｔａｔｉｏｎ  ｏｆ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｓｅｑｕｅｎｃｅｓ  Ｉ．Ｃｏｓｅｔｓ  ａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ  ｐｅｒｉｏｄｉｃ  ｓｅｑｕｅｎｃｅｓ，”（Ａｕｇｕｓｔ，２００４，インターネット発表），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
【発明の開示】
［１］中澤宏，中澤直也，“長周期で高精度の一様独立乱数の設計：数の連が作る点列幾何の直積群構造及び格子構造に基づく制御．”
（Ｍａｒｃｈ  ９，２００８，インターネット発表，０３０９．ｐｄｆ），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
［２］中澤宏，中澤直也，“長周期で高精度の一様独立乱数の設計：数の連が作る点列幾何の直積群構造及び格子構造に基づく制御．”
（Ｍａｒｃｈ  ９−Ｊｕｌｙ  ４，２００８，インターネット発表，３０９７０４ｊ．ｐｄｆ），（ＵＲＬ）ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／．
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】段落００１９に記された本特許で請求する合成数の法の簡単な結果例を図１に示す。これは法ｄ＝２８６７＝４７×６１、乗数としてｚ＝６７８（法４７でｚ≡２０、法６１ではｚ≡７）、初期値ｎ１＝１の乗算合同法乱数列の数の２連を２次元平面でのｘｙ座標（ｎｋ＋１／ｄ、ｎｋ／ｄ）とする点の１周期Ｔ＝１３８０にわたるプロットを示す。ｑ１＝（ｐ１−１）／２＝２３、ｑ２＝（ｐ２−１）／２＝３０が偶奇性を異にするので、図は発明の開示１、２で示されたように正方形の中心に関して対称性を持たず、乱数として出現確率の低さを疑わせないものが実現し、全周期の使用を妨げる非蓋然性は見られない。外枠はたて、横軸とも−０．０５から１．０５までを表す。巡回列＜ｚ＞およびそれと同数で共通な数のない剰余類からの２連の作る点を共に示した図２では１からｐ１ｐ２−１までの中にあるｐ１あるいはｐ２の倍数、総数でｐ１＋ｐ２−２＝１０６個、の欠損が見える。スペクトル検定はこれらの欠損と０も含めたｄ＝ｐ１ｐ２個の点の全体配置を評価する。＜ｚ＞あるいはその剰余類は評価される点全体のほぼ１／２であり、単一の奇素数を法とする原始根の作る巡回列で可能な使用法と完全に同じでスペクトル検定の効力も高く、図２のほぼ完全な一様分布状況の１／２の点を用いるものとして一様性の不安はない。請求項１が与える構成、すなわちｑ１、ｑ２が異なる偶奇性を持つように奇素数ｐ１とｐ２を選ぶことは最良の乗算合同法の形態を与える。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】段落００１９の指摘を外れた状況、すなわち２つの奇素数ｐ１、ｐ２が共に奇数のｑ１＝（ｐ１−１）／２、ｑ２＝（ｐ２−１）／２を与える場合の例は図３−５に見られる。これらは合成数の法ｄ＝２５３７＝４３×５９、乗数ｚ＝４８５、即ち法４３でｚ≡１２、法５９でｚ≡１３の場合で、共にそれぞれの法で優れた原始根乗数である。ｑ１＝（ｐ１−１）／２＝２１、ｑ２＝（ｐ２−１）／２＝２９が共に奇数なので、図は発明の開示１、２が示すように正方形の中心に関して対称になり、一様独立乱数と考えると蓋然性の低いものが実現している。初期値はｎ１＝１（法４３でも法５９でもｎ１≡１）である。図３−５は一様独立乱数列出力の２連を平面の点の座標（ｎｋ＋１／ｄ、ｎｋ／ｄ）とするプロットで、外枠はたて横軸とも−０．０５から１．０５を表す。図３は巡回列＜ｚ＞の周期Ｔ＝２ｑ１ｑ２＝１２１８の１／２まで取った点列を示す。図４は１周期の点列の姿である。巡回列＜ｚ＞とそれに入らない数ｎ１に対する剰余類ｎ１＜ｚ＞からの数の２連が与える点をすべて記したものが図５である。図５の点全体は、ｐ１とｐ２の倍数、総数ｐ１＋ｐ２−２＝１００、に相当する空席以外は正方形を均等に埋め尽くす。乗算合同法巡回列＜ｚ＞で実現される図４の点分布がその半分である事は段落００２１と同様で、これが乱数列として採択できれば空間を一様に満たす点列の１／２として一様性の観点からは問題はなくなる。しかし図４の点集合の正方形の中心に関する対称性は非蓋然的な相関を示すものであり、乱数列としての仮説は却下され採択できない。そのさらに１／２に限った図３の点は、一様とは言えない分布を持つ図４の点集合の１／２であるから、一様性に信頼が置けない。一様独立乱数列として、この図３の点列を生成する乱数列を用いることは好ましくない。明らかに、請求項１の構成は２つの奇素数の積の法での最良の形態を与えている。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２４
【補正方法】変更
【補正の内容】
【００２４】段落００１２−００１５の手順は段落００１２において３以上のｓ個の異なる奇素数ｐ１、ｐ２、・・・、ｐｓを、ｑｊ＝（ｐｊ−１）／２がｊ＝１、２、・・・、ｓのすべてについて互いに素でその中の１つは偶数であり他はすべて奇数、を満たすように選んで作られる合成数の法ｄ＝ｐ１ｐ２・・・ｐｓでも考え得る。実際ｊ＝１、２、・・・、ｓのそれぞれについて、法ｐｊでの掃過的スペクトル検定で得られる優れた原始根乗数ｚｊを採り、乗数ｚをｊ＝１、２、・・・、ｓのそれぞれについてｚ≡ｚｊｍｏｄ（ｐｊ）によって中国剰余定理で定まるものとすれば、法ｄ＝ｐ１ｐ２・・・ｐｓで乗数をｚとする乗算合同法は周期Ｔ＝２ｑ１ｑ２・・・ｑｓを獲得し、巡回列＜ｚ＞やその剰余類のＬ連が作る点はＬ次元空間で非蓋然的な対称性を持たないものとなる事が特許の開示１、２で示されている。しかしこの場合巡回列＜ｚ＞は法ｄとは素な数全体の１／２ｓ−１の部分しか占めず、一方段落０００６の数５と同じベクトルが与える最短長さの探索で得られるスペクトル検定はｄと素な数の全体を含む座標を持つ点の配置を評価する。ゆえにｓ≧３の増大と共に検定の有効性は小さくなり、一方周期Ｔを増大させる事はスペクトル検定の計算可能性で限界を与えられていて実利は薄い。この意味からも請求項１のように２つの異なる奇素数の積の法を用いる構成は最良の技術的選択である。