このエントリーをはてなブックマークに追加
ID 15036
本文ファイル
著者
Nishimura, Takuji
キーワード
Random number generation
Fourier transform
Statistical test
NDC
統計
抄録(英)
We introduce a non-empirical test on pseudorandom number generators (prng), named sum-discrepancy test. We compute the distribution of the sum of consecutive m outputs of a prng to be tested, under the assumption that the initial state is uniformly randomly chosen. We measure its discrepancy from the ideal distribution, and then estimate the sample size which is necessary to reject the generator. These tests are effective to detect the structure of the outputs of multiple recursive generators with small coefficients, in particular that of lagged Fibonacci generators such as random() in BSD-C library, as well as add-with-carry and subtract-with-borrow generators like RCARRY. The tests show that these generators will be rejected if the sample size is of order 106. We tailor the test to generators with a discarding procedure, such as ran_array and RANLUX, and exhibit empirical results. It is shown that ran_array with half of the output discarded is rejected if the sample size is of the order of 4×1010. RANLUX with luxury level 1 (i.e. half of the output discarded) is rejected if the sample size is of the order of 2×108, and RANLUX with luxury level 2 (i.e. roughly 3/4 is discarded) will be rejected for the sample size of the order of 2.4×1018. In our previous work, we have dealt with the distribution of the Hamming weight function using discrete Fourier analysis. In this work, we replace the Hamming weight with the continuous sum, using a classical Fourier analysis, i.e. Poisson's summation formula and Levy's inversion formula.
掲載誌名
Mathematics and Computers in Simulation
62巻
3-6号
開始ページ
431
終了ページ
442
出版年月日
2003-03
出版者
Elsevier Science
ISSN
0378-4754
NCID
出版者DOI
言語
英語
NII資源タイプ
学術雑誌論文
広大資料タイプ
学術雑誌論文
DCMIタイプ
text
フォーマット
application/pdf
著者版フラグ
author
権利情報
Copyright (c) 2003 Elsevier Science
関連情報URL(IsVersionOf)
http://dx.doi.org/10.1016/S0378-4754(02)00227-6
部局名
理学研究科