(57)【要約】【課題】十分な長周期と確率統計的な意味でより高い精度を実現する一様独立性とをコンピュータ上に実現し、検定値による性能保障を与える事ができる乗算合同法乱数の検定方法の設計。【解決手段】乗算合同法乗数ｚの従来のスペクトル検定に加えて、乗数ｚの２次以上の冪の２次スペクトル検定の簡単で強力な判定による設計の必要を見出し、その設計のための実際手続きを示して、コンピュータ上に実装されるべき最も簡単な構造と最も一般的な表現可能性とを持つ乱数生成機構である乗算合同法において出力の統計的独立性の格段の向上を実現する方法を与え、また検定結果の表示による乱数生成方式の高精度の性能明示に重要な手段を与えた。【選択図】なし【特許請求の範囲】
【請求項１】
（ｄ、ｚ、ｎ）或いは本質には関係しないｎを省いて（ｄ、ｚ）と記す乗算合同法、即ち奇整数ｄを法、ｄとは素な整数ｚを乗数、ｄとは素な任意整数ｎは出発値を定めるものとして、整数列｛ｒ１、ｒ２、ｒ３、・・・｝を漸化合同式
【数１】
2015187892.tif 000022
で定め、除法の等式ｖｋ＝ｒｋ／ｄを実現して、一様独立乱数列｛ｖｋ｜ｋ＝１、２、・・・｝を出力する乗算合同法（ｄ、ｚ）、をコンピュータ上の一様独立乱数生成機構として設計するための新しい方法であって、純正な一様独立乱数の典型見本列が持つ性質、即ち乱数列を１、２、・・・の任意のものｊだけ離れて取って得られる対（ｖｋ、ｖｋ＋ｊ）を平面の点Ｐｋ（ｊ）と見るとき点列｛Ｐ１（ｊ）、Ｐ２（ｊ）、・・・｝の各点の第１と第２の座標が互いに独立な乱数であるという性質、を統計的仮説として最も弱く否定する様に設計するため、従来の乗算合同法の設計及び性能評価において用いられていた（ｄ、ｚ）の２次スペクトル検定即ち点列｛Ｐ１（１）、Ｐ２（１）、・・・｝の２次スペクトル検定のみを行うという先行技術、を拡張し、少なくともｊ＝２、３、・・・、６に対しても点列｛Ｐ１（ｊ）、Ｐ２（ｊ）、・・・｝の２次スペクトル検定を行う新しい方法、より具体的に述べれば、これらのｊ飛びに取られた対が座席を占める平面Ｐの格子の平行隣接格子間隔の最大値λｄ（２）（ｚｊ）を計算し、幾何学的な理想である平面３角格子での値λｄ（２）、
【数１】
2015187892.tif 000023
に十分近い条件、即ち比ρｄ（２）（ｚｊ）：＝λｄ（２）（ｚｊ）／λｄ（２）が次の範囲
【数２】
2015187892.tif 000024
にある事を少なくともｊ＝２からｊ＝６までに亘って満たす条件、を合格基準として乗算合同法乱数生成機構（ｄ、ｚ）を設計する方法、即ち計算としてはｚ’をｚｊに法ｄで合同な任意のものとして平面双対（逆）格子の基ベクトル
【数３】
2015187892.tif 000025
のすべての整数ｍ１、ｍ２を係数とする１次結合のベクトルｆ＝ｍ１ｆ１＋ｍ２ｆ２の長さ
【数４】
2015187892.tif 000026
の０ではない正の最小値を与えるベクトルｆｍｉｎを関係する整数ｍ１、ｍ２をすべて計算機上で掃過する事によって各長さ‖ｆｍｉｎ‖を算出し、それが不等式
【数５】
2015187892.tif 000027
を、今までの技術のｊ＝１のｚ’＝ｚ１＝ｚで満たす以外に、少なくともｊ＝２から６までのｚ’≡ｚｊ（ｍｏｄ  ｄ）も満たす、という新条件で合格乗数ｚを探索計算によって選出する乗算合同法（ｄ、ｚ）の新設計であり、コンピュータ上に高い精度の統計的性質を持つ一様独立乱数生成機構として実装する事を可能にする方法。
【発明の詳細な説明】
【技術分野】
【０００１】本発明はコンピュータ上に実装されるべき一様独立乱数生成機構設計の新しい方法に関する。【０００２】コンピュータ上の乱数生成機構は再現可能性を求められる。再現可能性とは、例えば使用者がシミュレーションプログラムのデバッグを必要とするとき、その要求に応じて完全に任意の値から完全に同一の乱数列を再度出力できる性質を言う。また、乱数生成機構は移植可能性、即ちそれらを他のコンピュータ或いは計算言語に移植しても同一の乱数列を発生できる性質、を求められる。そしてシミュレーションは通常記憶装置に備蓄して使用できる限界を遥かに超える量の乱数を必要とする。故にコンピュータ上の乱数は、再現性移植可能性を確保するため、長大計算で制御し難く累積する打ち切り或いは丸めの誤差を持たず、計算言語への依存性もない整数演算のみを用いて順次生成されなければならない。具体的には整数の列｛ｘ１、ｘ２、ｘ３、・・・、ｘＴ｝で条件０≦ｘｋ＜ｚをすべてのｋと十分大きい整数ｚに対して満たすものを整数演算で生成し、順次ｋ＝１、２、・・・に対するｕｋ＝ｘｋ／ｚの算出においてのみ実数計算を実現して、一様独立乱数を擬するものとして出力しなげればならない。任意の計算機上で次の出力を算出するために用い得る異なる状態総数は常に有限であるから、初期状態は必ず再現し、出力できる乱数の総数Ｔは、いかに大きくても必ず有限である。すべてが０ではない整数の任意の有限列｛ｘ１、ｘ２、ｘ３、・・・、ｘＴ｝を取り、条件０≦ｘｋ＜ｚがすべてのｋ＝１、２、・・・で成り立つと仮定する。この列は自明に、次の既約分数ｎ／ｄの基数ｚでの割り算で得られる循環小数の循環節に対応する：
【数３】
2015187892.tif 000002
ここでは｛ｘ１、ｘ２、ｘ３、・・・、ｘＴ｝はすべてがｄ−１ではない、と限って０＜ｘ＜１に簡単化した。分母ｄはｚＴ−１の因数だからｚとは共通素因数を持たない（互いに素である）。分子ｎの、ｎとは素な分母ｄによる割り算は終る事なく続き、次の諸式で表される：
【数４】
2015187892.tif 000003
第２式を積ｄｚで割ったものは鍵となる次の評価を与える：
【数５】
2015187892.tif 000004
この評価式は、除法ｎ／ｄで余りが小さければ次の段の商は小さい、という自明の事実を表す。しかし結果は全く自明ではなく、実用ではｚは２３０以上だから、誤差の上限１／ｚ＜２−３０は無視できるほど小さい。不等式は、コンピュータ上で用いられるべきどんな一様乱数列｛ｘｋ／ｚ｜ｋ＝１、２、・・・、Ｔ｝も小さい一様誤差限界１／ｚ＜２−３０内で列
【数６】
2015187892.tif 000005
によって近似される、と示す。この列は正確に整数の法ｄ、ｄとは素な整数の乗数ｚ、ｄとは素な系列の初期値を定める整数ｎで生成される乗算合同法数列を定めている。乗算合同法を以下（ｄ、ｚ、ｎ）と、不明確がなければ（ｄ、ｚ）と略記する。整数の全く一般的な算術原理としての上述の事柄から、十分長い周期Ｔを持ち、優れた一様独立性を持つ乗算合同法（ｄ、ｚ、ｎ）が見出されれば、コンピュータ上の一様独立乱数生成機構としては十分である、と見通す事ができる。この透視が現在の発明を貫く技術思想である。【０００３】乗算合同法（ｄ、ｚ）はその設計、性能評価にスペクトル検定を用いる事が可能であり容易である、という技術的特性を持つ。現在の発明はその中の２次スペクトル検定のみに関わるので、議論を２次スペクトル検定に限定して、使用者の十分な理解を容易に得る様説明する。（ｄ、ｚ）乗算合同法乱数のｄで割って正規化する前の整数の２連は、（ユークリッド）平面Ｐの座標を法ｄで考えれば、点（ｎｚｋ、ｎｚｋ＋１）と表す事ができる。即ち乗算合同法は平面Ｐの点列｛（ｎｚｋ、ｎｚｋ＋１）｜ｋ＝１、２、３、・・・｝を生成する。座標の法ｄでの同値、ｄの整数倍の違いを無視する立場、あるいは平面を周期ｄのドーナッツ面（トーラス）と看做す立場、で考えて、これらのすべて点は平面Ｐのある格子に座標を持つ、言い換えればある格子の格子点に席を占める。この格子は次の２つの（行）ベクトルを基ベクトルとする：
【数７】
2015187892.tif 000006
実際、法ｄを考えなければ、２連の点はベクトルｎｚｋｅ１である。座標を法ｄで考えて同一視する事はこのベクトルを各座標軸方向にｄの整数倍だけ平行移動する事である。第２軸方向のｄ平行移動は自明にｅ２の整数倍をこのベクトルに加えて実現される。第１軸方向にはベクトル
【数８】
2015187892.tif 000007
の整数倍を加えればよい。故に（ｄ、ｚ）乗算合同法の２連の点と、それとは法ｄで同値な座標を持つすべての点は、ベクトルｅ１及びｅ２の整数倍を位置座標とする点全体、ｅ１とｅ２が基ベクトルとして張る平面格子Ｇ（これを（ｄ、ｚ）格子とも呼ぶ；Ｇはドイツ語Ｇｉｔｔｅｒによる）の格子点の中にある。中にある、というのは、全格子点ではなく、ｄの整数倍の（ごく希少な）座標の格子点は除いて席を占めるからである。従って格子Ｇの格子点の分布の幾何学的状態は、（ｄ、ｚ）乗算合同法乱数列の相続く２連が互いに独立かどうか、の統計的推論に強力な判定道具を与える。【０００４】上の議論からも示唆される通り、整数の演算、特に法ｄの合同法算法、は理解と応用の要である。議論は難しいものではないが、現在の学校教育では殆ど取り上げられていないため、コンピュータ技術に優れた青少年が困難を感じる事を恐れる。しかし整数論の系統立った学習は全く必要なく、簡単な要点のみが求められる。それを述べる試みは中澤と中澤（２００８）、ファイル名”３０９７０４ｊ．ｐｄｆ”の付録に与えられている：
【非特許文献１】中澤と中澤（２００８）：中澤宏／中澤直也、”長周期で高精度の一様独立乱数の設計：数の連が作る点列幾何の直積群構造及び格子構造に基く制御”／（Ｍａｒｃｈ  ９−Ｊｕｌｙ  ４，  ２００８）／  ｆｉｌｅｎａｍｅ″３０９７０４ｊ．ｐｄｆ″／（２００８／３／９−２００８／７／４）。この文献は次のＵＲＬ″ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈ−ｎｋｚｗ／ｐａｓｔｒｅｐｏｒｔｓ．ｈｔｍｌ″にダウンロード可能に公開されていて、現発明の利用、乗算合同法（ｄ、ｚ）の作成開発、・・・には十分と思われるので、必要ならばこの付録だけでも一読を薦める。
【０００５】述べられた通り、平面の点の座標に法ｄの合同を置く事はまた、平面Ｐを各軸方向に周期ｄのドーナツ面（トーラス）と考える事でもある。だから考察は平面Ｐ全体でなく、例えば原点から各軸方向にｄの辺を持つ正方形Ｓの上で行えば十分である。Ｓ内の上述の（ｄ、ｚ）格子の様々な姿は、視覚的な認識で最も容易な直観理解が得られるので、簡単な奇数の法ｄとそれと素な乗数ｚについて、図１及び図２に乗算合同法（ｄ、ｚ）の２連を正方形Ｓ内の点と見る典型的な分布図を示す。法ｄと乗数ｚの値は図に記された（ｄ、ｚ）から読み取られる。各図を与える（ｄ、ｚ）の性能評価は、乗数ｚについて後に正確に計算方法を述べる評価値ρ＝ρｄ（２）（ｚ）で示されている。これら諸図から見られる通り、（ｄ、ｚ）格子点の分布は様々な姿を取る。乱数列が一様独立と仮定する。その相続く２つの値の点がＳのある格子点に現れるとしよう。その点の第２座標は次の点の第一座標であり、次の点の第２座標はこの第１座標とは関係なく０からｄまでのどのような値も同じ確率で取るはずである。この統計的仮説を否定する事の最も弱い座席配置、格子点の幾何学、は第１図のρが１に上から近いものが示す正３角形に近い形を作る基ベクトルを持つもの、物理の言葉で３角格子に近い形、である。言葉で明確に形容すれば、望ましいのは格子点の配置が平面Ｅ内で一様で、かつ方向によらない（等方）様な分布を持つ事である。この状況は格子Ｇ内の平行隣接格子線の最大間隔で定量的に表され、この事実を用いる技術が（２次）スペクトル検定である。【０００６】乗算合同法（ｄ、ｚ）の相続く出力が作るＥ内の点列という限定、即ち｛ｅ１＝：（１、ｚ）、ｅ２：＝（０、ｄ）｝が張る格子、という限定を離れて、平面Ｐ内の一般の格子、平面格子Ｇを考える。それは平行でない任意の２ベクトル｛ｅ１、ｅ２｝の整数係数の１次結合の全体として格子Ｇを定義する事と同じである：
【数９】
2015187892.tif 000008
どんな格子Ｇでも基ベクトルの取り方は無数にある。格子Ｇが平面Ｐに与えられたとして、それから基ベクトルの組を見出す操作を考える。平面Ｐの直線Ｌでその上に２つの格子点があるものを格子線Ｌと呼ぶ；実際はＬ上には無数の格子点が載っている。格子線Ｌ上で隣接する任意の２つの格子点をＯ、Ａとし、矢印Ｏ→Ａを第１の基ベクトルｅ１とする。この格子線Ｌに平行で隣接する格子線Ｌ’、即ちＬとＬ’の間に他の平行な格子線が存在しないもの、を任意に取り、その上の任意の格子点Ｂを取って、矢印Ｏ→Ｂを第２の基ベクトルｅ２と定義する。組｛ｅ１、ｅ２｝は平行４辺形を作り、頂点以外にはその辺にも内部にも格子点が存在しない。この平行４辺形を２辺の方向に平行移動させれば、頂点Ｏは全ての格子点を巡り、平行４辺形は平面Ｐを重複なく埋め尽す。この｛ｅ１、ｅ２｝は格子を張る基ベクトルである。そしてこの様な任意の取り方で作られるものが基ベクトルのすべてである。自明に、すべての基ベクトルは同じ面積Ｓの平行４辺形を張る。（ｄ、ｚ）格子の場合は、Ｓは前述の２次元基ベクトルの組が作る行列式の絶対値として常にＳ＝ｄである。【０００７】平面Ｐの任意の格子Ｇの任意の基ベクトルの組がつねに同一面積の平行４辺形を張る、という事実は重要な意味を持つ。Ｇの基ベクトルの組を｛ｅ１、ｅ２｝とし他の任意の基ベクトルの組を｛ｅ１’、ｅ２’｝とする。後者は第１の組で張られる格子Ｇのベクトルだから、整数ｕ１１、ｕ１２、ｕ２１、ｕ２２を用いて第１の組によって
【数１０】
2015187892.tif 000009
と表される。（ｕ１１、ｕ１２）を第１行、（ｕ２１、ｕ２２）を第２行とする行列Ｕ、行ベクトル｛ｅ１、ｅ２｝を第１、２行とする行列Ｅ、そして行ベクトル｛ｅ１’、ｅ２’｝を第１、２行とする行列Ｅ’、をそれぞれ導入すると、上の関係は行列積Ｅ’＝ＵＥである。両辺の行列式を絶対値の記号を流用して表せば｜Ｅ’｜＝｜ＵＥ｜＝｜Ｕ｜・｜Ｅ｜である。基ベクトルの張る面積がつねに一定である事は｜Ｅ’｜＝±｜Ｅ｜を意味するから、これは｜Ｕ｜＝±１を意味する。行列Ｕが整数成分を持ち行列式が｜Ｕ｜＝±１である事はＵがユニモジュラー行列である、と定義される。任意の平面Ｐの格子Ｇのすべての基ベクトルの間にはユニモジュラー行列による変換がある。逆に任意の基ベクトルの組が作る行列Ｅを任意のユニモジュラー行列Ｕで変換したＥ’の第１、２行は同じ格子の基ベクトルである。【０００８】以下、平面Ｐの任意の格子の観察を続ける。任意の基ベクトルの組を具体的にＰの点をつなぐ矢印｛Ｏ→Ａ、Ｏ→Ｂ｝と考え、幾何学的には平行４辺形より基本的な３角形、△ＯＡＢを考える。辺ＡＢは１つの格子線であり、頂点Ｏから辺ＡＢに平行に引いた直線も格子線であって、これらの間に他の格子線はない。だから辺ＡＢに平行で最隣接の格子線の間隔は△ＯＡＢで頂点Ｏから底辺ＡＢへの垂線の長さ、頂点Ｏの底辺ＡＢからの高さである。△ＡＢＣの辺と対する頂点の他の組についても同じで、次の重要な一般理解が得られる：
［補題α］任意の平面格子Ｇで、平行な最隣接格子線の最大間隔は、あらゆる基ベクトルの組が作る面積一定の３角形で頂点の底辺からの高さの最大値である。【０００９】（ｄ、ｚ）平面格子に戻ろう。（ｄ、ｚ）格子の基ベクトルの作る３角形は面積ｄ／２で一定であるが、図１及び図２の例で見た様に３角形そのものは様々に取る事ができるし、様々な幾何学的な姿と見る事ができる。格子点の座席上には乱数の相続く対が点として現れる。既に述べた通り、乱数が一様独立であるという仮説に最も弱い否定で合格するのは、図１、２からの明らかな直観として、格子Ｇが正３角形に近い形を作る基ベクトルの組を持つ場合である。このは次の補題βでスペクトル検定と結びつく。
［補題β］基ベクトルが面積ｄ／２一定の３角形を作る平面格子Ｇの中の平行で最隣接の格子線の間隔の最大値は、正３角形を張る基ベクトルを持つ３角格子の場合に最も小さい値λｄ（２）：＝２−１／２３１／４ｄ１／２を取る。故に、（ｄ、ｚ）乗算合同法乱数列に伴われる（ｄ、ｚ）平面格子Ｇの平行最隣接格子線間隔λｄ（２）（ｚ）は常にλｄ（２）（ｚ）＞λｄ（２）を満たす。
（証明）少し長いがやさしい。面積Ｓ＝ｄ／２一定の平面格子を任意に考える。そしてまず、面積Ｓの正３角形の辺の長さＤ０、頂点の高さＨ０が次で与えられる事を確認する：
【数１１】
2015187892.tif 000010
この格子の基ベクトルの任意の組は直接には、それが作る３角形△ＯＡＢの３辺に平行な隣接格子線の３組を記述する。辺ＡＢが、この格子の中で隣接格子線間隔の最大値Ｈを与えている、としよう。即ちＯからＡＢに平行な（格子）線を引けば、それとＡＢとの間隔、即ち頂点Ｏの底辺ＡＢへの高さＨがこの格子のすべての隣接格子線間隔の最大値である、とする。格子の基ベクトルの組が作る３角形はすべて、等しい面積Ｓを持つから、底辺ＡＢ（それは１つの基ベクトルを与えている）の長さＤとＨとはＤＨ＝２Ｓ、Ｄ＝２Ｓ／Ｈの関係にあり、Ｈがすべての基ベクトル対３角形の頂点の高さの最大だから底辺の長さＤは格子のすべての基ベクトルの長さ以下である。必要なら３角形の頂点Ｏを底辺ＡＢ（基ベクトル）に平行にＡＢの長さＤの整数倍だけ（Ｄを法として）動かしてＡＢの両端からの垂線の間に新しい頂点Ｏ’を持つ△Ｏ’ＡＢに移る。△Ｏ’ＡＢも格子の基ベクトルが作る３角形で、基ベクトルとして最小の底辺ＡＢの長さＤは辺Ｏ’Ａ、Ｏ’Ｂの長さ以下である。故に（基ベクトルの組が作る３角形を一般に離れて）辺ＡＢの垂直２等分線上の高さＨの点Ｏ”を取って２等辺３角形の△Ｏ”ＡＢを考えると、等辺Ｏ”Ａ、Ｏ”ＢはＤ以上であり、底辺ＡＢ上に作った正３角形は（△Ｏ”ＡＢに内接する場合も含めて）完全に△Ｏ”ＡＢに含まれる。故にＤ≦Ｄ０かつＨ≧Ｈ０＝λｄ（２）である。（証明終）【００１０】この理解は、（ｄ、ｚ）乗算合同法に対して相続く乱数出力が載る格子の最大の格子線間隔λｄ（２）（ｚ）を求め、それを幾何学的最小値のλｄ（２）で割った比
【数１２】
2015187892.tif 000011
が１に近い事、平行隣接格子線の最大間隔が理想３角格子のそれに近い事、を（ｄ、ｚ）乱数の性質の良さとする判断の根拠である。ＦｉｓｈｍａｎとＭｏｏｒｅ（１９８６）は、彼らの画期的な仕事で（ｄ、ｚ）２次スペクトル検定の合格基準１＜ρｄ（２）（ｚ）＜１．２５を始めて導入した。この判断の妥当性は図１、図２から直感的に明らかであり、今までもこれからも重要性を失う事のない基準である。概念的にも彼らの仕事は、優れた乱数生成方法は検定をすべての可能な候補に予断なく行う以外に発見方法がない、という重要な理解を与えるものであった。
【非特許文献２】ＦｉｓｈｍａｎとＭｏｏｒｅ（１９８６）：Ｇ．Ｓ．Ｆｉｓｈｍａｎ  ａｎｄ  Ｌ．ＲＭｏｏｒｅ，“Ａｎ  ｅｘｈａｕｓｔｉｖｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｃｏｎｇｒｕｅｎｔｉａｌ  ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒｓ  ｗｉｔｈ  ｍｏｄｕｌｕｓ  ２▲３１▼−１”，ＳＩＡＭ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｃｉｅｎｔｉｆｉｃ  ａｎｄ  Ｓｔａｔｉｓｔｉｃａｌ  Ｃｏｍｐｕｔｉｎｇ  Ｖｏｌ．７（１９８６），ｐｐ．２４−４５．
【００１１】現在の発明は次の新しい認識から生まれた。もし（ｄ、ｚ）乱数｛ｖ１、ｖ２、・・・｝が一様独立なら、ｊ飛びの番号に対する｛ｖ１、ｖ１＋ｊ、ｖ１＋２ｊ、ｖ１＋３ｊ、・・・｝も一様独立である。この列はｚ’≡ｚｊ（ｍｏｄ  ｄ）を乗数とする乗算合同法（ｄ、ｚ’）で与えられる乱数列だから、それが一様独立であるためにはその２次スペクトル検定も合格である事、即ち
【数１３】
2015187892.tif 000012
が必要である。実際にこの２次スペクトル検定をＦｉｓｈｍａｎとＭｏｏｒｅが選んだ素数の法ｄ＝２３１−１で合格とされた５つの乗数ｚの２次スペクトル検定結果に行った結果が図３である。ａと記されたのはＦｉｓｈｍａｎとＭｏｏｒｅが用いた評価値で、ここでの記法はρ＝１／ａに当る。ＦｉｓｈｍａｎとＭｏｏｒｅは小数点以下４桁で結果を表したのでそれを小数点以下８桁に計算し直したのがｂである。ｃ欄が新しい（ｄ、ｚｊ）のｊ＝２、３、・・・、６での結果である。結果は悪い。これらの乗数ｚは一様独立乱数列を作るとは言えない。教訓は明らかである。第１に、乱数生成方式を検定なしに性能が良いだろう、と考える事はつねに危険で決して行ってはいけない。第２に、ＦｉｓｈｍａｎとＭｏｏｒｅの結果は法ｄ＝２３１−１のすべての原始根乗数ｚを調べたものだから、この法では一様独立な乗算合同法乱数として合格と言えるものが存在しない；優れた（ｄ、ｚ）の探索はより多くの法ｄと、それらに関わるすべての乗数ｚについて行わなければならない。そして第３にその探索は（ｄ、ｚｊ）についても、現在までのｊ＝１は当然として、ｊを２以上少なくとも６まで、少なくとも乗数の６乗まで、に対する２次スペクトル検定を新しく行い、合格するものだけを求めなければならない。【００１２】乗算合同法（ｄ、ｚｊ）の２次スペクトル検定は（ｄ、ｚｊ）格子の平行最隣接格子線の最大間隔λｄ（２）（ｚｊ）の算出を要する。これは現在のスペクトル検定技術の範囲内だから十分既知である。また計算上は、（ｄ、ｚ）の２次検定プログラムにおいて乗数ｚを法ｄでｚｊに合同なｚ’で置換する操作だけで正しいプログラムが得られ、実際技術としても実現容易である。しかし優れた（ｄ、ｚ）探索を目指す若い人々が要点の把握を記述の錯綜する、或いは分かりやすいとは思われない、他の特許非特許文献に亘って調べ考えなくてもよい様に、以下解説する。まず、（ｄ、ｚｊ）乱数の相続く出力が平面Ｅに作る格子Ｇの基ベクトル｛ｅ１＝（１、ｚｊ）、ｅ２＝（０、ｄ）｝は既知だが、基ベクトルではなくＧの双対格子（逆格子）を用いて考える方がよい。以下暫く、平面Ｐの格子Ｇは（ｄ、ｚｊ）格子と限定せず一般のものとして、１組の基ベクトル｛ｅ１、ｅ２｝は既述の一般の取り方で与えられた格子から構成されたもの、とする。次の直交関係で｛ｅ１、ｅ２｝に対する双対基ベクトル｛ｆ１、ｆ２｝を導入する（ここで（ｅｊ、ｆｋ）は内積である）：
【数１４】
2015187892.tif 000013
｛ｅ１、ｅ２｝を行とする２×２行列をＥ、｛ｆ１、ｆ２｝を行とする２×２行列をＦと記すと、この関係は行列積で簡明にＥ（ｔＦ）＝Ｉと表される；ｔＦはＦの転置（ｔｒａｎｓｐｏｓｅ）行列、Ｉは単位行列である。これは直ちにＦ＝ｄ｛ｔ（Ｅ−１）｝、Ｅ−１はＥの逆行列、と解かれ、Ｆの一意性もわかる。基ベクトルの組｛ｅ１、ｅ２｝が△ＯＡＢを張るとし、基ベクトルを具体的に
【数１５】
2015187892.tif 000014
と対応させる。双対ベクトルｆ１はｅ２に垂直だから、それは辺ＡＢに垂直である。故にこの△ＯＡＢで頂点Ｏの辺ＡＢへの高さｈはベクトルｆ１の長さを‖ｆ１‖と記して
【数１６】
2015187892.tif 000015
である。Ｏは格子Ｇの任意の基ベクトルの組が作る３角形△ＯＡＢの任意の頂点だから、この事実は次の基本関係を示す：
［補題γ］任意の平面格子Ｇの平行最隣接格子線の最大間隔ＨはＨ＝ｄ／‖ｆｍｉｎ‖で与えられる。ここでｆｍｉｎはすべての基ベクトルに対する双対基ベクトルの中で正で最小の長さを持つもの、最短の双対基ベクトルである。【００１３】上では双対基ベクトルはＧのある１組の基ベクトルで定義された。次が成り立つ：
［補題δ］（Ａ）平面格子Ｇの任意の基ベクトルの１組｛ｅ１、ｅ２｝が定義する双対基ベクトル｛ｆ１、ｆ２｝が張る平面内の格子、即ち｛ｆ１、ｆ２｝のすべての整数係数１次結合の全体、をＧの双対格子（逆格子）Ｇ＊と呼ぶ。Ｇの他の任意基ベクトルの組｛（ｅ１）’、（ｅ２）’｝が定義する双対基ベクトルはすべて、双対格子Ｇ＊の基ベクトルである。
（Ｂ）格子Ｇの平行隣接格子線の最大間隔ＨはＨ＝ｄ／‖ｆｍｉｎ‖で与えられる。ここでｆｍｉｎは双対格子Ｇ＊の０ベクトルではない最短ベクトルである。
（証明）（Ａ）Ｇの基ベクトルの２組｛ｅ１、ｅ２｝及び｛（ｅ１）’、（ｅ２）’｝をそれぞれの行ベクトルとする２×２行列をＥ及びＥ’と記すと、既に見たように必ず整数を成分とするユニモジュラー行列ＵがあってＥ’＝ＵＥの１次変換が成り立つ。Ｅに対応する双対基｛ｆ１、ｆ２｝を行とする行列ＦはＦ＝ｄ｛ｔ（Ｅ−１）｝で与えられ、Ｅ’に対応する双対基｛（ｆ１）’、（ｆ２）’｝を列とする行列Ｆ’は
【数１７】
2015187892.tif 000016
で与えられる。Ｕの逆行列Ｕ−１は整数成分のユニモジュラー行列であり、その転置行列も同じ行列式のユニモジュラー行列である。故にＦ’は平面ＰでＦが張る双対格子Ｇ＊の他の（双対）基ベクトルの作る行列であり、その各行ベクトルはＧ＊の基ベクトルである。
（Ｂ）双対格子Ｇ＊の一般ベクトルの正で最小の長さのベクトルは、明らかに最小の長さの基ベクトルだから、補題δ（Ｂ）は成り立つ。（証明終）【００１４】補題δによって、問題の（ｄ、ｚｊ）の２次スペクトル検定は、（ｄ、ｚｊ）格子の双対格子の中で最短のベクトルｆｍｉｎを探索する問題であり、λｄ（２）（ｚｊ）＝ｄ／‖ｆｍｉｎ‖＞λｄ（２）を求め２次スペクトル検定評価値ρｄ（２）（ｚｊ）＝２−１／２３１／４ｄ１／２／‖ｆｍｉｎ‖を得る計算問題である。技術構造としては、まず十分な長さの乱数周期を与え得る法ｄを取って乗数ｚで周期に関して好ましい性質を持つもの、例えば奇素数の法ｄでの原始根、などは予断なく検定のため選出し、先行技術としての（ｄ、ｚ）の２次検定を行い、合格なら現発明での（ｄ、ｚ２）、（ｄ、ｚ３）、・・・、（ｄ、ｚ６）のと２次検定に次々と進んで、すべてに合格するｚだけを選出する方法が発明である。（ｄ、ｚｊ）個々の２次検定は、良く知られた技術であるが、このような総合検定の必要は新しい発見であり、検定方法は新技術である。例えば図３の表でρｄ（２）（ｚ３）＞６などの悪い性質を持つものはある乱数出力ｖｋとｖｋ＋３とが独立とは考えられない、それにも関わらず高次検定だけを行って合格という誤った判断も生じた。それを防ぐ（ｄ、ｚｊ）の２以上のｊに対する２次検定は緊要な新技術である。【００１５】新しくこのような検定を行おうとする若い技術者のために、２次スペクトル検定に限定して、注意をより具体的に述べる。スペクトル検定にはより短いベクトルを大きい歩幅で発見するためにシュミットの直交化を利用し、それで十分小さい範囲とわかれば総当り的な探索に移る方がよい、とする方法も提唱されているが、問題のスペクトル検定に登場する（双対）格子ベクトルの探索すべき長さは、下で示すように法ｄに対して十分に小さいと思われる範囲、１．０７４５７ｄ１／２未満、に限ってよいという理論的な理解があり、直交化が整数成分ベクトルとあまり計算上の合性良くない事とも相俟って、始めからこの、ｄに比べて十分小さい範囲の総探索を行う方がよいと考える。それは実際計算でも十分現実的と示されていて、以下のように述べる事ができる。まずｚｊの検定は法ｄでｚ’≡ｚｊとなる任意のｚ’で行えばよい事は触れた。通常は１＜ｚ’＜ｄのｚ’を選ぶ事が計算量として得策である。従って以下このように選ばれた（ｄ、ｚ’）の２次検定に関して述べる。２次検定での特殊事情は格子ベクトルでも双対格子ベクトルでも計算はほぼ同じ最短ベクトル問題であるが、３次以上では双対格子での計算がより易しく、実際的なので、ここでは通常の双対格子の最短ベクトル問題として考える。２次元（ｄ、ｚ’）双対格子の最短ベクトルｆｍｉｎを求めてｄ／‖ｆｍｉｎ‖を計算する。具体的に、（ｄ、ｚ’）格子の基ベクトルの１組が｛（１、ｚ’）、（０、ｄ）｝は既知であり、これに対応する双対基ベクトルの組が｛ｆ１：＝（ｄ、０）、ｆ２：＝（−ｚ’、１）｝である事は内積計算でわかる。必要なのは任意の整数ｍ１、ｍ２で定まる双対格子のベクトル
【数１８】
2015187892.tif 000017
の最短のものを求める事である。しかしあらゆる整数の組（ｍ１、ｍ２）を調べる２次元探索は必要ではない。それは次の関係に基く。
［補題ε］座標でｆ＝（ｙ１、ｙ２）と表される２次元整数ベクトルは、法ｄでｙ１＋ｚ’ｙ２≡０を満たすなら２次元（ｄ、ｚ’）双対格子のベクトルであり、逆に任意の双対格子ベクトルｆ＝（ｙ１、ｙ２）はすべてこの条件、法ｄでｙ１＋ｚ’ｙ２≡０、を満たす。
（証明）ｆ＝（ｙ１、ｙ２）が条件、法ｄでｙ１＋ｚ’ｙ２≡０、を満たすなら、整数ｍがあってｙ１＋ｚ’ｙ２＝ｍｄであり、ｙ１＝ｍｄ−ｚ’ｙ２であって、ｆ＝ｍｆ１＋ｙ２ｆ２が成り立つ、即ちｆは双対格子ベクトルである。逆にｆ＝（ｙ１、ｙ２）が２次元（ｄ、ｚ’）双対格子ベクトルなら、整数の組（ｍ１、ｍ２）があって、ｆ＝（ｍ１ｄ−ｍ２ｚ’、ｍ２）と表される。故に法ｄでｙ１＋ｚ’ｙ２＝ｍ１ｄ≡０である。（証明終）【００１６】さらに、我々が証明を見た事実から次の制限がある：
［補題ζ］（ｄ、ｚ’）双対格子の正で最短の長さを持つベクトルｆｍｉｎは、その長さが制限‖ｆｍｉｎ‖＜２１／２３−１／４ｄ１／２を必ず満たす。故にデカルト座標でｆｍｉｎ＝（ｙ１、ｙ２）と表すとき、ｙ１、ｙ２は
【数１９】
2015187892.tif 000018
を満たすものだけを掃過すれば十分である。
（証明）２次元（ｄ、ｚ’）格子の平行隣接格子線の最大間隔は
【数２０】
2015187892.tif 000019
を満たす。故に次の成立が理論的に保証されている：
【数２１】
2015187892.tif 000020
故にこの（最）右辺よりも小さい長さの範囲、座標の大きさの範囲で最小長さの双対ベクトルｆｍｉｎの探索すれば十分である。（証明終）【００１７】ｄは大きな整数であり、それと比べてｄ１／２は非常に小さい。上の補題ζはスペクトル検定は格子の最小長さベクトルの探索問題として非常に性質がよい事を示している。実際、整数デカルト座標成分でｆ＝（ｙ１、ｙ２）であるベクトルが（ｄ、ｚ’）双対格子の任意ベクトルであるとすると、補題εによって法ｄでｙ１＋ｚ’ｙ２＝ｍｄ≡０となる整数ｍがあり、ｙ１＝ｍｄ−ｚ’ｙ２であるが、制限
【数２１】
2015187892.tif 000021
の下ではこの整数ｍは様々に取る必要はなく、ｙ１はコンピュータ上の計算言語には必ず装備されているｍｏｄ関数で一意に定まる。故に（ｄ、ｚ’）双対格子ベクトル（ｙ１、ｙ２）の探索はｙ１とｙ２を動かす２次元探索ではなく、ｙ２を上の範囲に定めてｙ１をただ１つ定める探索、ｙ２だけを大きさ±ｄ１／２の範囲で動かす１次元探索である。まとめれば、（ｄ、ｚ’）乗算合同法の２次スペクトル検定値ρｄ（２）（ｚ’）は例えば次の探索設計によって得られる：
［探索方法η］（Ａ）必要な周期を与える法ｄを定める。
（Ｂ）法ｄでｚ’≡ｚｊとなるｚ’を０＜ｚ’＜ｄの範囲で定める。
（Ｃ）整数ｙ２を範囲｜ｙ２｜＜２１／２３−１／４ｄ１／２＜１．０７４５７ｄ１／２で掃過し、法ｄで−ｚ’ｙ２に等しく範囲｜ｙ１｜＜１．０７４５７ｄ１／２にある（一意の）整数ｙ１を求めて、‖（ｙ１、ｙ２）‖２＝（ｙ１）２＋（ｙ２）２の最小値、‖ｆｍｉｎ‖２を算出する。
（Ｄ）ρｄ（２）（ｚ’）＝２１／２３−１／４ｄ１／２／‖ｆｍｉｎ‖＜１．２５が成立すれば、ｚ’を２次スペクトル検定合格とし次に進む。（Ｃ）の途中でもｙ２が小さい‖（ｙ１、ｙ２）‖の値を与えて‖ｆｍｉｎ‖＜２１／２３−１／４ｄ１／２／１．２５と判明すれば、ｙ２の掃過を中止しｚ’を棄却して、ｚの次の候補、法ｄの次の候補へと進む。
なお、（Ｄ）において整数ベクトルｆ＝（ｙ１、ｙ２）に関し等式‖ｆ‖２＝２・３−１／２ｄ／（１．２５）２が成り立つ事はなく、‖ｆｍｉｎ‖＜２１／２３−１／４ｄ１／２／１．２５と不等号で十分である。【００１８】このような２次スペクトル検定のプログラムは、ＦＯＲＴＲＡＮの、それも化石的な形ではあるが、中澤（２０１２）に与えられダウンロード可能な形で公開されている。その中のサブルーチンｔｅｓｔ２を参照して頂きたい。
【非特許文献３】中澤（２０１２）：Ｎａｏｙａ  Ｎａｋａｚａｗａ，″ｓｗｅｅｐ１２５ｎａｏｚ．ｆｏｒ″／ｈｔｔｐ：／／ｗｗｗ１０．ｐｌａｌａ．ｏｒ．ｊｐ／ｈｎｋｚｗ／ｉｎｄｅｘ．ｈｔｍｌ（Ｊｕｎｅ  ２６，  ２０１２）／ｆｉｌｅｎａｍｅ″ｓｗｅｅｐ１２５ｎａｏｚ．ｆｏｒ″．これはプログラムとしてダウンロード可能である。
【図面の簡単な説明】
【００１９】
【図１】乗算合同法（ｄ、ｚ）が発生する２連の出力を平面の点と見る場合の典型的な分布図。描かれた図は検定評価値ρ＝ρｄ（２）（ｚ）がほぼ１．０５、１．１０、・・・、１．３０となる場合である。外枠の正方形は単位正方形を囲む少し大きい正方形である。（ｄ、ｚ）は図の説明から読み取る事ができる。
【図２】乗算合同法（ｄ、ｚ）が発生する２連の出力を平面の点と見る場合の典型的な分布図。描かれた図は検定評価値ρ＝ρｄ（２）（ｚ）が図１よりは大きく、ほぼ１．３５、１．４０、・・・となる場合である。外枠の正方形は単位正方形を囲む少し大きい正方形である。（ｄ、ｚ）は図の説明から読み取る事ができる。
【図３】ＦｉｓｈｍａｎとＭｏｏｒｅ（１９８６）によって選ばれた上位５個の優れた乗数の性能表。行ａは彼らの与えた評価値、行１／ａはａ行の数値の逆数でここでρｄ（２）（ｚ）と記すもの、行ｂはρ＝ρｄ（２）（ｚ）の発明者による再計算、行ｃはρｄ（２）（ｚｊ）のｊ＝２，３、・・・、６の値を表す。
【発明を実施するための形態】
ＦｉｓｈｍａｎとＭｏｏｒｅ（１９８６）は素数の法ｄ＝２３１−１でのすべての原始根の検定を行ったが、その最良合格者の図３に示された結果は、これらはすべて一様独立乱数列としては棄却されるべきであると知らせる。より多くの法、より多くの乗数を試し、また用い得る周期の長い乗算合同法を発見しなければならない。そのための２次スペクトル検定に限って大まかに再記すれば次の手順になる：
（Ａ）必要な周期を与える法ｄを定める。
（Ｂ）法ｄでｚ’≡ｚｊとなるｚ’を０＜ｚ’＜ｄの範囲で定める。
（Ｃ）整数ｙ２を範囲｜ｙ２｜＜２１／２３−１／４ｄ１／２＜１．０７４５７ｄ１／２で掃過し、法ｄで−ｚ’ｙ２に等しく範囲｜ｙ１｜＜１．０７４５７ｄ１／２にある（一意の）整数ｙ１がなければ次のｙ２へ、あれば‖（ｙ１、ｙ２）‖＝｛（ｙ１）２＋（ｙ２）２｝１／２の値を記録して次のｙ２へ、と探索を進め、‖ｆｍｉｎ‖を求める。
（Ｄ）ρｄ（２）＝（ｚ’）＝２１／２３−１／４ｄ１／２／‖ｆｍｉｎ‖＜１．２５ならｚ’を２次スペクトル検定合格として次に進む。手続き（Ｃ）の途中でも‖（ｙ１、ｙ２）‖が小さくなり過ぎて不合格なら、ｚそのものを棄却し、ｚの次の候補へ進む。乗数を調べ尽くしたなら、法ｄを新しく取らなければならない。
（Ｅ）合格者（ｄ、ｚ）が発見されれば、続いて３次から６次のスペクトル検定でさらに進まなければならないが、それは現在の発明の外であるので触れない。
【図１】
2015187892.tif 000028
【図２】
2015187892.tif 000029
【図３】
2015187892.tif 000030