A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 New Randomness Test Based on Linear Complexity Profile Um novo teste de aleatoriedade baseado no perfil de complexidade linear

Kenji HAMANO, Fumio SATO, Hirosuke YAMAMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.1 pp.166-172
Data de publicação
2009/01/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E92.A.166
Tipo de Manuscrito
Special Section PAPER (Special Section on Cryptography and Information Security)
Categoria
Matemática

autores

Palavra-chave