|
2017年度に引き続き、2018年度も擬似乱数用統計的検定パッケージで最も広く使われているTestU01および米国国立標準技術研究所(NIST)作成のSP800-22について、それらの信頼性および改善法に関する検定を行なっている。
2018年度は、NISTの検定パッケージで用いられている「二重検定」に関する研究を行なった。二重検定は通常の擬似乱数列に対する統計的検定(第1段階の検定)から得られるp値の分布が、一様性とどの程度乖離しているかをカイ二乗適合度検定によって検定(第2段階の検定)する手法であり、擬似乱数検定においては広く用いられている。
二重検定は、第1段階の検定のサンプルサイズに制約がある場合でも全体のサンプルサイズを簡単に大きくすることができ、局所的な検定では捉えきれない偏りを検出できる利点がある。一方で、第2段階の検定のサンプルサイズは経験的に決められることが多く、特にNIST SP800-22に関しては、暗号用擬似乱数生成法が棄却されないよう、実験的に1000から10000程度とする報告が多い。
本研究では、NISTの15種類の検定のうち6種類の検定について、与えられたサンプルサイズによる第1段階の検定から得られるp値の正確な分布と、理論分布である一様分布との乖離をカイ二乗ディスクレパンシーを用いて測り、第1段階のサンプルサイズnに応じて第2段階のサンプルサイズNの上限を決定する方法を研究した。この結果、n=1000000の場合、(1) Longest Run of Ones 検定ではN=21000, (2) Overlapping Template Matching 検定ではN=2600000, (3) Random Excursions 検定ではN=934000、と従来の研究よりも精度よくNの上限を見積もることができた。
また、正確なp値の分布が計算できない検定では、モンテカルロ法を用いてカイ二乗ディスクレパンシーを計算することによって、Nの上限を近似的に求めることとした。これにより(4) Linear Complexity 検定ではN=510000, (5) Frequency test within a Block ではN=105000, (6) Discrete Transform 検定ではN=3700という値を得た。
これらの上限が適切であるかを、Mersenne TwisterおよびSHA-1アルゴリズムを用いた擬似乱数生成法でシミュレーションしたところ、理論と適合する実験結果が得られた。また、代数的・幾何的な欠陥が指摘されているいくつかの古い擬似乱数生成法について、これまでの推奨サンプルサイズでは棄却できなかったものを、統計的検定においても適切に棄却することができた。
以上の結果をまとめ、2019年7月に開催されるモンテカルロ法・準モンテカルロ法に関する国際会議 "12th International Conference on Monte Carlo Methods and Applications (MCM2019)" の擬似乱数分科会で口頭発表をすることとなった。
なお、2017年度に行なった、擬似乱数用統計的検定パッケージに対する三重検定を用いた信頼性評価について論文を作成したところ、計算機シミュレーション分野では著名な国際査読付き論文誌 "Mathematics and Computers in Simulation" から出版された。この際、修正作業のため、2018年度に改めて必要な追試・実験を行なっている。
|