A New Randomness Test Based on Linear Complexity Profile
スポンサーリンク
概要
- 論文の詳細を見る
Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.
- （社）電子情報通信学会の論文
- 2009-01-01
著者
-
Yamamoto Hirosuke
Department Of Complexity Science And Engineering The University Of Tokyo
-
Yamamoto Hirosuke
Department Of Complexity Science And Engineering Graduate School Of Frontier Science The University
-
Hamano Kenji
Department Of Complexity Science And Engineering The University Of Tokyo
-
SATO Fumio
Technical Research & Development Institute, Ministry of Defense
関連論文
- Strongly Secure Linear Network Coding
- THE UTILITY OF DOBUTAMINE (DOB) STRESS ECG
- A Randomness Test Based on T-Complexity
- A New Randomness Test Based on Linear Complexity Profile
- The Optimal n-out-of-n Visual Secret Sharing Scheme for Gray-Scale Images(Special Section on Information Theory and Its Applications)
- Correction of Overlapping Template Matching Test Included in NIST Randomness Test Suite(Information Theory and Its Applications)
- A CASE OF OCULAR TOXOPLASMOSIS IN AN ADULT, THE INFECTION BEING CONFIRMED BY THE ISOLATION OF THE PARASITE FROM SUBRETINAL FLUID