The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
A complexidade linear pode ser usada para detectar sequências não aleatórias previsíveis e, portanto, está incluída no conjunto de testes de aleatoriedade do NIST. Mas, como mostrado neste artigo, o conjunto de testes do NIST não consegue detectar sequências não aleatórias que são geradas, por exemplo, pela concatenação de duas sequências M diferentes com baixa complexidade linear. Esse defeito decorre do fato de o teste de complexidade linear do NIST utilizar desvio do valor ideal apenas na última parte de todo o perfil de complexidade linear. Neste artigo, é proposto um novo teste de complexidade linear fiel, que utiliza desvios em todas as partes do perfil de complexidade linear e, portanto, pode detectar até mesmo as sequências não aleatórias acima. Uma fórmula eficiente é derivada para calcular a distribuição exata da área necessária para o teste proposto. Além disso, é fornecido um procedimento simples para calcular a estatística de teste proposta a partir do perfil de complexidade linear, que requer apenas O(M) complexidade de tempo para uma sequência de comprimento M.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Kenji HAMANO, Fumio SATO, Hirosuke YAMAMOTO, "A New Randomness Test Based on Linear Complexity Profile" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 1, pp. 166-172, January 2009, doi: 10.1587/transfun.E92.A.166.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.166/_p
Copiar
@ARTICLE{e92-a_1_166,
author={Kenji HAMANO, Fumio SATO, Hirosuke YAMAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Randomness Test Based on Linear Complexity Profile},
year={2009},
volume={E92-A},
number={1},
pages={166-172},
abstract={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.},
keywords={},
doi={10.1587/transfun.E92.A.166},
ISSN={1745-1337},
month={January},}
Copiar
TY - JOUR
TI - A New Randomness Test Based on Linear Complexity Profile
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 166
EP - 172
AU - Kenji HAMANO
AU - Fumio SATO
AU - Hirosuke YAMAMOTO
PY - 2009
DO - 10.1587/transfun.E92.A.166
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2009
AB - 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.
ER -