Title :
On the Density of Irreducible NFSRs
Author :
Tian Tian ; Wen-Feng Qi
Author_Institution :
Dept. of Appl. Math., Zhengzhou Inf. Sci. & Technol. Inst., Zhengzhou, China
Abstract :
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.
Keywords :
Boolean functions; cryptography; shift registers; Boolean functions; NFSR sequences; irreducible NFSR density; linear feedback shift registers; positive integer; stream ciphers; Boolean functions; Ciphers; Generators; Linear feedback shift registers; Periodic structures; Polynomials; Families of NFSR sequences; irreducibility; nonlinear feedback shift registers; stream ciphers;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2013.2247093
