On the Density of Irreducible NFSRs

Let n be a positive integer. An NFSR of n stages is called irreducible if the family of output sequences of any NFSR of stages less than n is not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs of n stages is larger than 0.39. This implies that it is e...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2013-06, Vol.59 (6), p.4006-4012
Main Authors: Tian, Tian, Qi, Wen-Feng
Format: Article
Language:English
Subjects:
Applied sciences
Boolean functions
Ciphers
Cryptography
Exact sciences and technology
Families of NFSR sequences
Generators
Information theory
Information, signal and communications theory
irreducibility
Linear feedback shift registers
Mathematical analysis
nonlinear feedback shift registers
Periodic structures
Polynomials
Signal and communications theory
stream ciphers
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let n be a positive integer. An NFSR of n stages is called irreducible if the family of output sequences of any NFSR of stages less than n is not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs of n stages is larger than 0.39. This implies that it is expected to find an irreducible NFSR of n stages among three randomly chosen NFSRs of n stages.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2013.2247093