(57)【要約】      （修正有）【課題】十分に長い周期と高い精度とを持ち、出力数の連はそれらの統計的に独立な出現を統計的に支持するスペクトル検定による性能保障を伴う一様独立乱数列の生成方法。【解決手段】異なる奇素数ｐ１とｐ２を２つのオイラーの関数2014139762.tif 0000382014139762.tif 000039が互いに素でｑ１は奇数、ｑ２は偶数となるように取り、冪ｄ１＝ｐ１＾ｉ１及びｄ２＝ｐ２＾ｉ２、但し整数の指数ｉ１≧１及びｉ２≧１は共に１ではない、を作ってそれらの積ｄ＝ｄ１ｄ２を法と定める。法ｄ１での原始根ｚ１を掃過する２次から６迄のスペクトル検定で原始根ｚ１を十分多数選び、法ｄ２での原始根ｚ２を掃過する２次から６迄のスペクトル検定での原始根ｚ２を十分多数選んで、連立合同式ｚ≡ｚ１ｍｏｄ（ｄ１）、ｚ≡ｚ２ｍｏｄ（ｄ２）によって孫子の定理が法ｄで一意に定めるｚを乗数とする。【選択図】なし【特許請求の範囲】
【請求項００１】
数ｘのｙ乗をｘｙ＝ｘ＾ｙとも記して、２つの異なる奇素数ｐ１、ｐ２の冪の積である正の整数ｄ＝（ｐ１＾ｉ１）×（ｐ２＾ｉ２）を法とし、正の整数で法ｄとは素な乗数ｚ、及び正の整数で法ｄとは素な初期値ｎ１で不等式０＜ｎ１＜ｄを満たすもの、で定められる乗算合同法乱数生成方法であり、且つ下記の要件００１、要件００２、及び要件００３をすべて満たす一様独立乱数生成方式、即ちｋ＝１、２、・・・に対して整数ｎｋからｎｋ＋１を漸化合同式
【数００１】
2014139762.tif 000034
を満たしつつ０＜ｎｋ＋１＜ｄとなるよう定めて得られる整数列ｎ１、ｎ２、・・・から一様独立乱数列ｕ１、ｕ２、・・・を除法の等式
【数００２】
2014139762.tif 000035
を満たすように与える方式であって、且つ下記の要件００１、要件００２、及び要件００３をすべて満たす一様独立乱数生成方式。
［要件００１］上記「請求項１」の整数指数ｉ１及びｉ２はｉ１＝ｉ２＝１の場合を除外してｉ１≧１、ｉ２≧１を満たす。
［要件００２］上記請求項１の奇素数の冪ｐ１＾ｉ１及びｐ２＾ｉ２は、整数ｑ１＝（ｐ１−１）／２から作られるｐ＾（ｉ１−１）ｑ１と整数ｑ２＝（ｐ２−１）／２から作られるｐ２＾（ｉ２−１）ｑ２とが互いに素で、かつｑ１が奇数、ｑ２が偶数となるものである。
［要件００３］請求項１の乗数ｚは、奇素数ｐ１の冪ｐ１＾ｉ１を法とする原始根ｚ１及び奇素数ｐ２の冪ｐ２＾ｉ２を法とする原始根ｚ２で定められる連立合同式
【数００３】
2014139762.tif 000036
が孫子の定理により法ｄ＝（ｐ１＾ｉ１）×（ｐ２＾ｉ２）の意味で一意の存在を保証する解ｚであるもの、或いは要件００１の奇素数ｐ１の冪ｐ１＾ｉ１を法とする原始根ｚ１及びｐ２の冪ｐ２＾ｉ２を法とする原始根ｚ２から連立合同式
【数００４】
2014139762.tif 000037
が孫子の定理により法ｄ＝（ｐ１＾ｉ１）×（ｐ２＾ｉ２）の意味で一意の存在を保証する解ｚであるもの、である。
【発明の詳細な説明】
【技術分野】
【００１】本発明はコンピュータ上の一様独立乱数生成方法に係る。  さらに詳しくは自然数の法ｄ、前記ｄとは素な、すなわちｄとは共通素因数を持たない自然数の乗数ｚ≧２、そして前記法ｄとは素な自然数の初期項ｎ１でかつ０＜ｎ１＜ｄを満たすもの、に基づいて自然数の列｛ｎｋ｜０＜ｎｋ＜ｄ、ｋ＝１、２、・・・｝を生成する乗算合同法、すなわち整数ｎｋのｚ倍を法ｄで割った余りを次の整数ｎｋ＋１と定め、番号ｋ＝１、２、・・・に対して有理数列｛ｕｋ＝ｎｋ／ｄ｝を一様独立乱数列の出力とする乱数生成方法である乗算合同法、に関する。
【背景技術】
【００２】前記請求項００１における指数ｉ１＝ｉ２＝１の場合であって乗数ｚが連立合同式数００３で定まる方法は特許番号４６６９９７９で認可された。また同じ指数ｉ１＝ｉ２＝１の場合であって、乗数ｚが連立合同式数００４で定まる方法は特願２０１１−８９５７８で御審査を頂いている。ここに新しく御審査頂く方法はこれらの場合を除いてｉ１≧１、かつｉ２≧１となる場合の技術である。この発明は報告非特許文献００１において発見された興味ある事実、即ち奇素数ｐの冪ｐｉ（ｉ＞１）を法とする既約剰余類群の生成元（以下慣習に倣い法ｐｉの原始根と呼ぶ）にもｉ＝１の素数を法とする場合の原始根と同様に乗算合同法乱数の乗数として優れた性能を示すものが潤沢に存在する事、の詳しい考察から得られた。
【非特許文献００１】Ｎａｏｙａ  Ｎａｋａｚａｗａ，“Ｓｐｅｃｔｒａｌ  ｔｅｓｔｓ  ｏｖｅｒ  ｇｅｎｅｒａｔｏｒｓ  ｏｆ  ｒｅｄｕｃｅｄ  ｒｅｓｉｄｕｅ  ｃｌａｓｓ  ｇｒｏｕｐｓ  ｍｏｄｕｌｏ  ｓｑｕａｒｅｓ  ｏｆ  ｏｄｄ  ｐｒｉｍｅｓ．”（Ｊｕｌｙ  ２３−Ｓｅｐｔｅｍｂｅｒ  ９，２０１１．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ  ”ｓｑｕａｒｅｐｒｉｍｅ９８ｃｏｒｚ．ｐｄｆ．
【００３】乱数の乗算合同法が工学技術として有用であるためには、まず一様独立乱数として生成された列の使用可能な周期Ｔが法ｄに対して十分に大きくなければならない。乗算合同法乱数発生の計算負荷はｄと共に増大する。一方乗数ｚをどのように工夫しても、「使い得る周期Ｔ」はｄ／２を越える事ができない。この事実は次の考察から理解される。特許番号４６６９９７９、或いは特願２０１１−８９５７８で詳述された様に、奇素数の法ｄ＝ｐとその原始根ｚを用いる時、法ｐでの巡回列｛１、ｚ、ｚ２、ｚ３・・・｝の周期はｐ−１であり、この周期の間に巡回列には法ｐで同一のものは現れないが、このすべてを独立乱数列として用いる事ができない。実際、ｐ−１は偶数であり、整数ｑ＝（ｐ−１）／２に対してｚｑ≡ｐ−１≡−１  ｍｏｄ（ｐ）が必ず成り立ち、巡回列の後半は本質的に前半と同じものとならざるを得ないから、である。この事実は、奇素数の法ｄ＝ｐでの原始根ｚが作る乱数列の計算的な効率は
【数００５】
2014139762.tif 000002
である、τは１／２末満である、と述べれば明快であろう。素数の法ｄ＝ｐとその原始根ｚでさえ計算効率τが１／２を越えられない事実は、逆に合成数の法ｄでも乗数ｚの工夫によってそれに匹敵する効率τの達成を可能にする。実際、特許番号４６６９９７９、及び特願２０１１−８９５７８で利用されたのはこの可能性である。本出願は、第一に、２つの異なる素数の冪の積が与える法ｄ＝（ｐ１＾ｉ１）×（ｐ２＾ｉ２）でｉ１≧１，ｉ２≧１のもの、但し特許番号４６６９９７９及び特願２０１１−８９５７８でのｉ１＝ｉ２＝１の場合を除く、においても請求項で特徴付けられた形の乗数ｚを取ればこの効率τ≒１／２が実現される、という事実の発見に基づく。この事実の証明は次の段落に記す。なお上記効率τは、法ｄや乗数ｚについて触れられた以外のすべての他の取り方に対して１／３以下になる。この証明は平易だが可能な場合を順次調べ上げる長大なものとなり、上に述べられたτ＝１／２の実現状況と比べて興味は薄いので、ここでは立ち入らない。【００４】前段落００３に述べられた事柄を証明する。ｐ１とｐ２は異なる奇素数、指数ｉ１≧１及びｉ２≧１は整数、乗数ｚが前出の連立合同式数００３、再記して
【数００３】
2014139762.tif 000003
を満たす場合を仮定する。ｚ１は法ｐ１＾ｉ１での原始根、ｚ２は法ｐ２＾ｉ２での原始根、そしてｐ１＾（ｉ１−１）ｑ１が奇数、ｐ２＾（ｉ２−１）ｑ２が偶数であって且つこれらが互いに素である。このときｚ１の作る巡回列或いはその任意の剰余類の列が持つ周期はＴ１＝２ｐ１＾（ｉ１−１）ｑ１で、ｚ２の作る巡回列又はその任意の剰余類の列が持つ周期はＴ２＝２ｐ２＾（ｉ２−１）ｑ２である。対応して数００３で定められるｚが法ｄ＝（ｐ１＾ｉ１）×（ｐ２＾ｉ２）で作る巡回列は「最小公倍数周期」Ｔ＝Ｔ１×Ｔ２／２を持つ。巡回列の中点Ｔ／２＝Ｔ１Ｔ２／４で成分巡回列は
【数００６】
2014139762.tif 000004
の値を取る。ここでＴ１、Ｔ２は偶数だがＴ１／２は奇数、かつＴ２／２は偶数である仮定を用いた。もしｚ＾（Ｔ１Ｔ２／２）≡−１  ｍｏｄ（ｄ）ならこれらは共に−１でなければならない。それに反するから、述べられた通り法ｄでのｚの巡回列はその中点で−１の値を取らない。−１を巡回列が取り得るのはこの中点以外にはないから、このｚの巡回列の最小公倍数周期Ｔ＝Ｔ１Ｔ２／２全体を独立乱数として用いてよい。従って
【数００７】
2014139762.tif 000005
2014139762.tif 000006
が成り立つ。乗数ｚが数００４、再記して
【数００４】
2014139762.tif 000007
によって定められる場合の機構は少し異なる。既に特願２０１１−８９５７８でも述べた通り、ｚ１は法ｄ１＝ｐ１＾ｉ１での原始根で周期或いは位数Ｔ１：＝２ｐ１＾（ｉ１−１）ｑ１を持ち，Ｔ１’：＝Ｔ１／２に対して
【数００８】
2014139762.tif 000008
が成り立つ。故に請求項の要件００２の仮定、ｑ１が奇数、によりＴ１’＝Ｔ１／２＝ｐ１＾（ｉ１−１）ｑ１も奇数であり、
【数００９】
2014139762.tif 000009
となる。即ち−ｚ１の位数はＴ１’＝Ｔ１／２である（−ｚ１は法ｄ１での原始根ではない）。数００４で定められる乗数ｚの法ｄ＝ｄ１ｄ２での最小公倍数位数はＴ’＝Ｔ１’Ｔ２である。Ｔ２は偶数でＴ２／２は整数、位数Ｔ’の半分のＴ’／２では法ｄ１で
【数０１０】
2014139762.tif 000010
が成り立つ。勿論Ｔ１’が奇数であるから法ｄ２では
【数０１１】
2014139762.tif 000011
である。故に法ｄ＝ｄ１ｄ２ではｚ＾（Ｔ’／２）≡−１ではあり得ず、
【数０１２】
2014139762.tif 000012
となる。こうして背理法で数００４で定められる乗数ｚも法ｄでのその巡廻列に−１を含まず、全周期Ｔ’を独立乱数として用い得る事が分った。故に組（ｄ、ｚ）に基づく乗算合同法乱数の計算効率はτ＝Ｔ’／ｄ＝Ｔ１’Ｔ２／ｄ＝（Ｔ１Ｔ２／２）／ｄ≒１／２である。（証明終り）【００５】乗算合同法乱数生成で重要なもう一つの事は、段落００３の周期に関する効率の要件とは別に、優れた乗数を選び出すためのスペクトル検定の計算可能性である。非特許文献００２でＦｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅが示した事は、素数の法ｄ＝ｐでの原始根ｚは非常に多いが、一様独立乱数の生成にどれが優れてるかは予断なしにすべての原始根を検定しないとわからない、という厳しい一般的事実であった。この事実は直ちに、他の形の法ｄでの乗数ｚの選択にも敷衍され、さらにすべての乱数生成方式にまで及ぶ。ここでは、こうして理解された乗算合同法に必須のｅｘｈａｕｓｔｉｖｅなスペクトル検定の計算量について述べる。現在の興味の二つの異なる素数の冪の積を法ｄとする場合のスペクトル検定の計算量は発明の開示００１及び発明の開示００２によって幾つかの明解な理解が示された。詳細な論点はこれらの報告に委ねるが、当該計算量に関するより具体的な一般事実を以下に説明する。
【非特許文献００２】Ｇ．Ｓ．Ｆｉｓｈｍａｎ  ａｎｄ  Ｌ．Ｒ．Ｍｏｏｒｅ，“Ａｎ  ｅｘｈａｕｓｔｉｖｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓ  ２▲３１▼−１．”ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｃｉｅｎｔｉｆｉｃ  ａｎｄ  Ｓｔａｔｉｓｔｉｃａｌ  Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．７（１９８６），ｐｐ．２４−４５．
【発明の開示００１】
Ｎａｏｙａ  Ｎａｋａｚａｗａ  ａｎｄ  Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ：Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓｅｓ  ｆｏｒｍｅｄ  ｂｙ  ｔｗｏ  ｏｄｄ−ｐｒｉｍｅ−ｆａｃｔｏｒｓ  ｆｏｒ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒｓ  Ｉ．Ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｓｔｒｕｃｔｕｒｅｓ．（Ｓｅｐｔｅｍｂｅｒ  １５−１７，ｃｏｒｒｅｃｔｅｄ  ｏｎ  Ｊａｎｕａｒｙ  １９，２０１３）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ”ｒｅｖｐｏｐｅｓｑｌ．ｐｄｆ．”
【発明の開示００２】
Ｎａｏｙａ  Ｎａｋａｚａｗａ  ａｎｄ  Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ：  Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓｅｓ  ｆｏｒｍｅｄ  ｂｙ  ｔｗｏ  ｏｄｄ−ｐｒｉｍｅ−ｆａｃｔｏｒｓ  ｆｏｒ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒｓ  ＩＩ．Ｓｔｒｕｃｔｕｒｅｓａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ  ｓｐｅｃｔｒａｌ  ｔｅｓｔｓ．（Ｏｃｔｏｂｅｒ  １５，２０１２）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ”ｐｏｐｅｓｑ２．ｐｄｆ．”
【００６】以下法ｄ、乗数ｚの乗算合同法一様独立乱数生成機構を（ｄ、ｚ）と略記する。また（ｄ、ｚ）が生成する乗算合同法の整数巡回列を｛ｒ１、ｒ２、ｒ３、・・・｝と記す：
【数０１３】
2014139762.tif 000013
この巡回列のｍ番目からのＬ連Ｐｍ＝（ｒｍ、ｒｍ＋１、・・・ｒｍ＋Ｌ−１）をＬ次元空間の点と見做し、それに法ｄで合同な座標を持つすべての点を付け加えて考えると、これらの点列｛Ｐ１、Ｐ２、Ｐ３、・・・｝はこのＬ次元空間のある格子の上に載る格子点である事がわかる。これら諸事実については周知であり、発明の開示００１及び発明の開示００２に詳しいので言及を省く。だから格子点の幾何学的配置を知れば、乗算合同法乱数列の全周期について、あるＬ連が出た時に次のＬ連がそれまでとは無関係、独立に値を取ると言えるか、について情報が得られる。ただ、格子点のすべてをＬ連とそれに合同な座標の点が覆うわけではないので、できるだけ多くの格子点を使い得る１周期内に覆う様な（ｄ、ｚ）を取る事が技術的に有利である、この覆う割合はまさに計算効率τであって、どのような（ｄ、ｚ）を選んでも１／２を超える事はできない。従ってスペクトル検定が最大の効力を発揮するのは、（ａ）法ｄが奇素数か或いはその冪で乗数ｚが原始根の場合、或いは（ｂ）請求項００１のようにｄが奇素数の冪二つの積であり、要件００１から要件００３を満たし、乗数ｚが数００３或いは数００４で定められる場合に限る。問題はこれらの場合それぞれでスペクトル検定が要する計算量である。
【００７】  法ｄでの乗数ｚの巡回列のＬ連のスペクトル検定は次数Ｌを持つと呼ばれて、通常２≦Ｌ≦６の次数が検定対象に取られる。Ｌ次のスペクトル検定の計算構造は（ｄ、ｚ）の値だけで定まり、法ｄでｚをどの様な位数のものに取るか関係しない。この事柄の詳細は込み入った議論を要するから発明の開示００２に委ね、ここではまず、それらを手続きとして要約して出発する。Ｌ次スペクトル検定はＬ個の整数の組（ｊ１、ｊ２、・・・、ｊＬ）で次の条件数０１４を満たすもの
【数０１４】
2014139762.tif 000014
の全体について、その長さ‖（ｊ１、ｊ２、・・・、ｊＬ）‖：＝（ｊ１２＋ｊ２２＋・・＋ｊＬ２）１／２の正の最小値ｂ（Ｌ、ｄ、ｚ）を求める問題である。幸いな事に、現下のこのｂ（Ｌ、ｄ、ｚ）には構造的な上限値Ｂ（Ｌ、ｄ）があって、必ず不等式
【数０１５】
2014139762.tif 000015
が成り立つ。上限Ｂ（Ｌ、ｄ）は格子がＬ次元空間の中にあるという幾何学的な制限を表すもので、Ｌの各値に対し次の形を持つ。
【数０１６】
2014139762.tif 000016
無理数を用いたこれらの正確な値は発明の開示００１のＴａｂｌｅ  Ｉ（Ｂ）に与えられている。数０１５と数０１６の制限によってこの最短ベクトルを探索しなければならない整数の組の総数Ｎ（Ｌ、ｄ）は有限である。まず数０１４の条件に注目する。最短ベクトルに対応する数０１４の中の各成分整数ｊｋは数０１６からｃＬｄ１／Ｌよりは必ず小さい；ｃ１からｃ６は上の数０１６に与えられた定数である。従ってＬ次検定では組（ｊ１、ｊ２、・・・、ｊＬ）は
【数０１７】
2014139762.tif 000017
の範囲で探索すればよい。乗算合同法の法ｄは１より遥かに大きくｃＬｄ１／Ｌ≪ｄだから、特に数０１４はｊ１の合同式として
【数０ｌ８】
2014139762.tif 000018
と解き、その無数にある整数解の中から（例えば法ｄでの代表を−ｄ／２からｄ／２の範囲で考えて）条件−ｃＬｄ１／Ｌ＜ｊ１＜ｃＬｄ１／Ｌを満たすもの（高々２個）だけを取ればよく、満たさない組（ｊ１、ｊ２、・・・、ｊＬ）は捨ててよい。棄却されない条件はさらに０≦ｊ１＜ｃＬｄ１／Ｌだけに取って十分である；整数ベクトルｂと−ｂとは同じ長さであり、負のｊ１’を持つ組ｂ’＝（ｊ１’、ｊ２’、・・・、ｊＬ’）は−ｊ１’、０＜−ｊ１’＜ｃＬｄ１／Ｌを与える組で同じ長さの−ｂ’と必ず対になっているからである。こうして、探索されるべき組（ｊ２、ｊ３、・・・、ｊＬ）の総数Ｎ（Ｌ、ｄ）は次の上限を持つ事がわかる：
【数０１９】
2014139762.tif 000019
法ｄを固定しその下での乗数ｚを１つ取ればこの様に、スペクトル検定手続で掃過検索すべき場合の総数は法ｄの形、即ち奇素数の何乗であるか、に関係せず、また乗数ｚが原始根であるかどうかにも関係しないで、法ｄと乗数ｚの大きさだけで定まる。即ち、同じ検定計算量で得られる最大の乱数周期を与える乗算合同法（ｄ、ｚ）の技術的選択肢として最良のものは、（１）法ｄとして奇素数か奇素数の冪かに選びで乗数ｚがその法の原始根であるか、或いは（２）ｄが奇素数の冪２つの積で乗数ｚは特許番号４６６９９７９、特願２０１１−８９５７８、或いはここ、での各請求項の形か、に限られ、これらはすべて同じスペクトル検定計算の負荷量を持つ。但し検定計算ではすべての有資格乗数ｚの場合をもれなく、且つ先入観なく、検定することが必要なので、この「調べるべき乗数ｚの総数」がある意味で検定計算量の多寡を与える。これを段落を替えて説明する。
【００８】スペクトル検定計算量で発明の開示００１に与えられ議論を実際計算にさらに合わせて、別の見方から精密化する。検定は段落００７で述べられた整数が作るベクトル（これは逆格子と呼ばれる格子のベクトルである）の最小の正の長さｂ（Ｌ，ｄ，ｚ）を求めて、幾何学的最大値Ｂ（Ｌ、ｄ）に近いほど乗数ｚが一様独立に近いと判断する。或いは近いほど乗数ｚが一様独立でない分布を与えるという判断が棄却される根拠となる、と言ってもよい。近さは次で定義される比
【数０２０】
2014139762.tif 000020
で数量化される。非特許文献００２でＦｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅ（１９８６）が採用したのは２≦Ｌ≦６すべてについてμ（Ｌ、ｄ、ｚ）＜１．２５、というｚに対する合格基準であった。μ（Ｌ、ｄ、ｚ）が１．０５、１．００、・・・、１．５０等である、という事が意味する乗数ｚの性能は、非特許文献００３の図から見る事ができるのでここには触れない。ただ、非特許文献００２でＦｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅが見出した事、乗数ｚが良い性能を持つかどうかはスペクトル検定してみないとわからない、優れた乗数を発見するにはすべての原始根をｅｘｈａｕｓｔｉｖｅに検定して発見する以外の手段はない、という経験則は再度強調されるべきである。これは乗算合同法に限らず、どのような乱数生成方法についても成り立つ事であろう。しかし乗算合同法で法ｄの形を工夫すると、有利な見通しが得られる構造が表出する。現発明はこの発見を利用するものである。合格基準、μ（Ｌ，ｄ，ｚ）がμＬ未満である、が意味する次の事に注意する。この基準は
【数０２１】
2014139762.tif 000021
を与えるから、整数ベクトルｂ＝（ｊ１、ｊ２、・・・、ｊＬ）の検索を行ううちこの右辺以下の‖ｂ‖が出ればこの乗数ｚをＬ次元検定不合格として棄却して次の乗数ｚに向かう事になる。従って１つの乗数ｚについて数０１９のすべての整数ベクトルを検索し尽くすのは合格するｚの場合だけである。数０１９が示す通り、１つの乗数ｚについて検定される場合の総量は検定次数Ｌと共に増大するから、この状況ではＬ＝２から始めて不合格乗数ｚに対する無用な高い次数Ｌの検定計算をできるだけ省かなくてはならない。発明の開示００１では最も困難で次数の高いＬ＝６の場合についてｅｘｈａｕｓｔｉｖｅなスペクトル検定の計算量を調べたが、ここではまずＬ＝２次の検定計算が扱うべき整数の組の総数から段落を変えて考える。
【非特許文献００３】Ｎａｏｙａ  Ｎａｋａｚａｗａ  ａｎｄ  Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ，“Ｓｐｅｃｔｒａｌ  ｔｅｓｔｓ  ｏｆ  ｐｒｉｍｉｔｉｖｅ  ｒｏｏｔｓ  ｆｏｒ  ｐｒｉｍｅｓ  ｕｐ  ｔｏ  １０１０２７  ａｎｄ  ｏｆ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｓｅｑｕｅｎｃｅｓ  ｇｅｎｅｒａｔｅｄ  ｂｙ  ｐａｉｒｓ  ｏｆ  ｐｒｉｍｉｔｉｖｅ  ｒｏｏｔｓ．”（Ｍａｒｃｈ  １７，２０１１−Ｊｕｎｅ  ４，２０１２）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ”ｐａｉｒｔｅｓｔ９０ｒｅｖｂｉｎｄ２．ｐｄｆ．この文献付録の計算出力全データは膨大で本明細書には関係が薄いので、提出文献から除く。
【００９】簡明な奇素数の法ｄ＝ｐとその原始根、例えばＦｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅの場合、を取ろう。法ｄ＝ｐは止めると、その原始根の総数は、生成元の冪乗が再び生成元を与える様な指数を考えて、生成元の位数あるいはその巡回列の周期ｐ−１と素な指数の総数と同じ、オイラーの関数φ（ｐ−１）で与えられるとわかる。故にｅｘｈａｕｓｔｉｖｅなＬ次スペクトル検定で調べなければならない整数の組の総数はφ（ｐ−１）×Ｎ（Ｌ、ｄ）である。具体的には、整数ｑ：＝（ｐ−１）／２を定義してφ（ｐ−１）＝φ（２ｑ）≦ｑは確かである。状況はφ（２ｑ）のｑの素因数分解の場合によって定かではないが、一般にｐに比べて小さいとは言えない。原始根総数φ（２ｑ）が余りに小さい奇素数の法ｄ＝ｐでは、むしろ優れた乗数がその中に存在しないという好ましくない可能性もある。Ｆｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅが選んだ奇素数ｄ＝ｐ＝２３１−１では原始根総数はｄ＝ｐの２４．９％であった。この様な傾向、φ（ｐ−１）がｄ＝ｐの程度の大きさであり、小さくない因子である場合を仮定しよう。なお、乗数ｚと共に−ｚも原始根ならｚと−ｚ、或いはｚとｚの法ｐでの逆数ｚ−１、のスペクトル検定成績はそれぞれ同一になるので、それらの考察は省いてもよいが、因子２〜４の違いを齎すこの様な詳細は大勢に影響がない、と考えない事にする。さて、実際のスペクトル検定ではμ（２、ｄ、ｚ）が表す２次性能評価が設定した値未満となる優れた原始根ｚを選び、選ばれたｚの中からμ（３、ｄ、ｚ）が設定した値未満のものを残し、・・・、として進む。次数Ｌが大きくなると検定すべき場合の数は急激に増大するので、この進め方なら無駄で大きい計算労力を要する探索を低次の段階で篩い落とす事になって経済的であろう。従って奇素数の法ｄ＝ｐでそのすべての原始根φ（ｐ−１）個に亘るＬ＝２次のｅｘｈａｕｓｔｉｖｅなスペクトル検定が探索すべき整数の組の総数が大切となる。それは
【数０２２】
2014139762.tif 000022
と評価される。現在のスーパーコンピュータは大体１．６京フロップス＝１．６×１０１６≒２５３．８フロップスの計算速度を持つ。大変甘く１浮動小数点計算毎に乗数ｚに関わる整数の１組の検定計算が進むとすれば、現在１秒間にｃ２ｐ３／２＜２５３．８を満たすたす奇素数ｐについてその全原始根乗数の２次ｅｘｈａｕｓｔｉｖｅスペクトル計算が可能である。１日≒２１６．４秒計算させればｐ３／２＜ｃ２２７０．２であり、ｃ２＝１．０７５からｐ＜２４７．５が１日でｅｘｈａｕｓｔｉｖｅに２次スペクトル検定計算可能な奇素数の法ｄ＝ｐの上限である。現在ばかりでなくこれからの事も考える。計算速度ｖのコンピュータはそれがシミュレーションに用いる乱数の周期Ｔ≦ｐ／２が、計算中に使い切られないように、ｐがｖのある定数ｃ’倍以上である事ｐ＞ｃ’ｖ、を要求する。一方でｅｘｈａｕｓｔｉｖｅな２次スペクトル検定可能な法ｄ＝ｐはｖ２／３のある定数ｃ”倍以下ｐ＜ｃ”ｖ２／３、である。この二つの不等式を満たすｖ、式で言って
【数０２３】
2014139762.tif 000023
でのみ、２次スペクトル検定で優れた性能を持つ奇素数の法ｄ＝ｐの乗算合同法乗数（ｄ、ｚ）がｅｘｈａｕｓｔｉｖｅ  な計算で発見可能である。明らかに、ｖが増大すると、数０２３を満たすｖの共通領域は存在できなくなる。これは計算機速度の増大に伴う２次スペクトル検定の計算不可能性である。勿論、−ｃ２ｐ３／２＜ｊ２＜ｃ２ｐ３／２の範囲の２次検定捜索の途中でも、Ｂ（２，ｄ）／μ２≧‖（ｊ１、ｊ２）‖≧ｂ（２、ｄ、ｚ）となる不合格がある乗数ｚで判明すれば探索は中止され次のｚに移るから、原始根φ（ｐ−１）個すべてにこの範囲の捜索を仮定する議論は過大だが、それは奇素数単独の法でのｅｘｈａｕｓｔｉｖｅなスペクトル検定の不利を覆すものではない。奇素数冪の法ｄ＝ｐｉを採用しても、その原始根の総数は
【数０２４】
2014139762.tif 000024
の評価を持ち、２次ｅｘｈａｕｓｔｉｖｅスペクトル検定に必要な計算量は再び数０２２の右辺で与えられる。従って計算速度の向上と共に待ち受ける２次ｅｘｈａｕｓｔｉｖｅスペクトル検定の計算不可能性の困難は単独奇素数の法と変わらない。
【０１０】二つの異なる奇素数の冪の積の形の法ｄ＝ｄ１ｄ２、ｄ１：＝ｐ１＾ｉ１、ｄ２：＝ｐ２＾ｉ２、のｅｘｈａｕｓｔｉｖｅ  な２次スペクトル検定を考える。乗数ｚは連立合同式
【数０２５】
2014139762.tif 000025
によって、乱数列の任意初期値ｎも
【数０２６】
2014139762.tif 000026
によって、法ｄで一意に定まる（孫子の定理）。乗算合同法（ｄ、ｚ）からの整数列｛ｒｋ≡ｎｚｋ−１ｍｏｄ（ｄ）｜  ｋ＝１、２、・・・、１≦ｒｋ＜ｄ｝はこのとき
【数０２７】
2014139762.tif 000027
であり、孫子の定理はさらにｒｋの次の形を保障する：
【数０２８】
2014139762.tif 000028
ここでＵ１とＵ２は整数であり、成分の法ｄ１、ｄ２だけで定まる。故に乗算合同法（ｄ、ｚ）は任意の初期値ｎに対し成分乗算合同法、（ｄ１、ｚ１）と初期値ｎ１、（ｄ２、ｚ２）と初期値ｎ２、の生成する乱数列の混ぜ合わせｓｈｕｆｆｌｉｎｇである；法ｄでの値の跳躍があるから、この混ぜ合わせは単純な線形加法ではない。しかし工学的直観、成分巡回列が一様独立をよく体現していれば、混ぜ合わせられた（ｄ、ｚ）巡回列もよい一様独立性を持ちやすいだろう、は実際計算も支持する。故にｓｈｕｆｆｌｉｎｇが効果的である様にｄ１≒ｄ２≒ｄ１／２程度で余り近すぎない様に選んで、ｚ１やｚ２は法ｄ１や法ｄ２のｅｘｈａｕｓｔｉｖｅなスペクトル検定で最良のものからｓ＝１００〜１０００個程度ずつを選び、それらの組み合わせ、総数ｓ２＝２１３．３〜２１９．９、を第二段のスペクトル検定で調べる事が技術的に有望である；ｓ２は決して小さい数ではないが、ｄの大きさの程度で大きくなるφ（ｄ）ほどの事はない。本発明はこの形での二段階スペクトル検定の利用を計算効率τ≒１／２を実現する場合について目指すものである。
【０１１】段落０１０の二段階スペクトル検定の計算量をＬ＝２次で考える。第一段はｄ１≒ｄ２≒ｄ１／２でのｅｘｈａｕｓｔｉｖｅなスペクトル検定二つである。法がｄ１＝ｐ１＾ｉ１では原始根が存在するから成分乗数ｚ１は原始根或いはそのマイナスに選ぶ：請求項００１の要件００２の（ｐ１−１）／２が奇数という仮定によって原始根のマイナスは原始根ではない；これは特願２０１１−８９５７８に示されている事である。但し任意乗数ｚと−ｚのスペクトル検定成績は同一である事が分っているので、原始根総数の２倍を取る様な精密化は再び省く。ｐ１−１が偶数だから、数０２４と同様に
【数０２９】
2014139762.tif 000029
である。故にこの法でのｅｘｈａｕｓｔｉｖｅな２次スペクトル検定が調べるべき場合の総数は次の評価の最右辺未満である：
【数０３０】
2014139762.tif 000030
定数ｃ２＝１．０７５は数０１６で定義されている。法ｄ２＝ｐ２＾ｉ２でのｅｘｈａｕｓｔｉｖｅな検定についても事柄は同じであり、ｚ２は原始根を選ぶ。原始根総数は、ｐ２−１が偶数だから、
【数０３１】
2014139762.tif 000031
故に
【数０３２】
2014139762.tif 000032
これらの総和として、奇素数冪の積の法に対する第一段のｅｘｈａｕｓｔｉｖｅな２次スペクトル検定が掃過すべき場合は
【数０３３】
2014139762.tif 000033
と判明する。ｄの冪指数３／４は１より小さいから、コンピュータ計算速度ｖに対してはｄの計算可能上限はｖ４／３の形で増大し、奇素数或いはその冪の法ｄで生じた計算速度ｖの増大に伴う計算困難は存在しない。これは重大な進歩である。因みに、現在のスーパーコンピュータをｖ＝２５３．８フロップスの速度で１秒動かして２次ｅｘｈａｕｓｔｉｖｅスペクトル検定を行うなら、２つの奇素数冪の積の法ｄとして計算できるのはｄ＜２６７．７、１日動かすならｄ＜２８９．６である。計算速度がこれからどのように増大発展しても、この計算可能性の利点は失われる事はない。
【発明の開示】
発明の開示は２０１２年９月１５日に始まり、２０１２年１１月１９日までに終わっている。すでに段落００５で文献として発明の開示００１及び発明の開示００２は記されているが、以下にこれらを再記し、発明の開示００３も２つの奇素数冪の法での巡回列の構造への明確な言及として下に記す。
【発明の開示００１】
Ｎａｏｙａ  Ｎａｋａｚａｗａ  ａｎｄ  Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ：Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓｅｓ  ｆｏｒｍｅｄ  ｂｙ  ｔｗｏ  ｏｄｄ−ｐｒｉｍｅ−ｆａｃｔｏｒｓ  ｆｏｒ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒｓ  Ｉ．
Ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｎａｌｙｓｉｓ  ｆｏｒ  ｓｔｒｕｃｔｕｒｅｓ．（Ｓｅｐｔｅｍｂｅｒ  １５−１７，ｃｏｒｒｅｃｔｅｄ  ｏｎ  Ｏｃｔｏｂｅｒ  ３１，２０１２）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．Ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ  ｒｅｖｐｏｐｅｓｑｌ．ｐｄｆ．
【発明の開示００２】
Ｎａｏｙａ  Ｎａｋａｚａｗａ  ａｎｄ  Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ：Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓｅｓ  ｆｏｒｍｅｄ  ｂｙ  ｔｗｏ  ｏｄｄ−ｐｒｉｍｅ−ｆａｃｔｏｒｓ  ｆｏｒ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒｓ  ＩＩ．Ｓｔｒｕｃｔｕｒｅｓ  ａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ  ｓｐｅｃｔｒａｌ  ｔｅｓｔｓ．（Ｏｃｔｏｂｅｒ  １５，２０１２）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ  ｐｏｐｅｓｑ２．ｐｄｆ．
【発明の開示００３】
Ｈｉｒｏｓｈｉ  Ｎａｋａｚａｗａ  ａｎｄ  Ｎａｏｙａ  Ｎａｋａｚａｗａ：Ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓｅｓ  ｆｏｒｍｅｄ  ｂｙ  ｔｗｏ  ｏｄｄ−ｐｒｉｍｅ−ｆａｃｔｏｒｓ  ｆｏｒ  ｕｎｉｆｏｒｍ  ａｎｄ  ｉｎｄｅｐｅｎｄｅｎｔ  ｒａｎｄｏｍ  ｎｕｍｂｅｒｓ  ＩＩＩ．Ｍｏｄｕｌａｒ  ａｒｉｔｈｍｅｔｉｃ  ｏｆ  ｉｎｔｅｇｅｒｓ  ａｎｄ  ｒｅｄｕｃｅｄ  ｒｅｓｉｄｕｅ  ｃｌａｓｓ  ｇｒｏｕｐｓ．（Ｎｏｖｅｍｂｅｒ  １９，２０１２）．Ｉｎ  ｔｈｅ  ＵＲＬ  ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／，ｆｉｌｅｎａｍｅ  ｐｏｐｅｓｑ３．ｐｄｆ．
【発明が解決しようとする課題】
【０１２】この発明は非特許文献００１の発見から、特許番号４６６９９７９及び特願２０１１−８９５７８の発明の自然な拡張として得られた。乗算合同法の設計は、法ｄを定め、そのｄの下で性能の良い乗数ｚを発見する作業である。発明の開示００１及び発明の開示００２で論じられた通り、良い乗数の発見はスペクトル検定をすべての可能な乗数、或いは可能性の大きい、すべての乗数に予断なく行って見出す（ｅｘｈａｕｓｔｉｖｅなスペクトル検定を行う）より他には得る手段がない。背景技術で記された通り、このｅｘｈａｕｓｔｉｖｅなスペクトル検定の計算量を計算可能な大きさにするためには２つの奇素数或いはそれらの冪の積の法を取る事が必要である。ただ、この様な法のとり方を工夫しても、よい乗数従ってよい乱数生成機構の発見は計算量の多い困難な仕事である。法の取り方を多様にして、採用し得る乗数の範疇を広げる事は採るべき自由度を広げて設計を容易にする上で重要であるが、それと共に採用できる可能性のあるより広い範囲の乗数を考察に含める事は技術の実現に役立つであろう。この自由度の拡大が本発明が解決を目指す課題である。
【課題を解決するための手段】
【０１３】法ｄを定めたときの１つの乗数ｚのスペクトル検定は、次数Ｌによって段落００７の数０１９に記された総数Ｎ（Ｌ、ｄ）の整数Ｌ個の組を順次取り上げ、Ｌ次元ベクトルの長さを算出して最短の長さｂ（Ｌ、ｄ、ｚ）を発見しなければならない。次数Ｌが増大するとこの総数Ｎ（Ｌ、ｄ）は増加するから、できるだけ不合格となるものに対する計算を省くためには、Ｌ＝２次で検定を行い、整数２個の組の長さ‖（ｊ１、ｊ２）‖≧ｂ（２、ｄ、ｚ）が小さくなって比μ（２、ｄ、ｚ）＝Ｂ（２、ｄ）／ｂ（２、ｄ、ｚ）が前もって定められた上限（例えばＦｉｓｈｍａｎ  ａｎｄ  Ｍｏｏｒｅの１．２５）を越えると判明するなら直ちに検定捜索計算をやめ次の乗数に進む、もし最後まで捜索して比μ（２、ｄ、ｚ）＜１．２５で合格と判明すれば同じ乗数ｚのＬ＝３次検定を始める、・・・と進むべきである。この計算の進め方次第でｅｘｈａｕｓｔｉｖｅな検定の計算量は大きく変わる。前記上限を厳しく、例えばμ（Ｌ、ｄ、ｚ）＜１．２５ではなく＜１．１０に採れば、既にＬ＝２次の検定で多くの乗数が不合格となり、検定作業は高速に進む事になるが、そのかわり６次までの検定すべてに合格する乗数が皆無である、という結果にもなり得る。この様な進め方の詳細は工学技術として様々に工夫をしなければならない所であり、現申請では最終的な完成には至っていない。しかし良い一様独立乱数生成機構（ｄ、ｚ）は稀な存在で、その発見は困難な作業である。それらをより多く、より容易に得るための手段として、現在の請求項００１の形に発見された法ｄと乗数ｚの採り方の範囲の拡大は重要であろう。