Root Counting, the DFT and the Linear Complexity of Nonlinear Filtering |
| |
Authors: | Kenneth G. Paterson |
| |
Affiliation: | (1) Hewlett-Packard Laboratories, Filton Road, Stoke-Gifford, Bristol, BS12 6QZ, U.K. |
| |
Abstract: | The method of root counting is a well established technique in the study of the linear complexity of sequences. Recently, Massey and Serconek [11] have introduced a Discrete Fourier Transform approach to the study of linear complexity. In this paper, we establish the equivalence of these two approaches. The power of the DFT methods are then harnessed to re-derive Rueppel's Root Presence Test, a key result in the theory of filtering of m-sequences, in an elegant and concise way. The application of Rueppel's Test is then extended to give lower bounds on linear complexity for new classes of filtering functions. |
| |
Keywords: | linear complexity Discrete Fourier Transform nonlinear filtering stream cipher cryptography |
本文献已被 SpringerLink 等数据库收录! |
|