Paper 2026/1680
New Results on the Density of Irreducible NFSRs
Abstract
Nonlinear feedback shift registers (NFSRs) are fundamental building blocks for modern stream-cipher constructions. An $n$-stage NFSR $f$ is classified as irreducible when the output sequence set of $f$ does not contain the output family of any NFSR of order less than $n$. Existing research has established upper and lower bounds for the density of irreducible NFSRs, confining this value within the range of 0.4461 to 0.4834. This study tightens these bounding intervals with high accuracy, reducing the original 0.04 gap down to only $8\times10^{-6}$.
Note: This preprint corresponds to the work under review at IEEE Transactions on Information Theory. Revisions will be synchronized with the journal submission process.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Nonlinear feedback shift register (NFSR)irreducible NFSRdensity estimationBoolean NullstellensatzGroebner basisstream ciphers.
- Contact author(s)
-
zhangdaoyuan @ iie ac cn
ddlin @ iie ac cn - History
- 2026-08-15: approved
- 2026-08-13: received
- See all versions
- Short URL
- https://ia.cr/2026/1680
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1680,
author = {Daoyuan Zhang and Dongdai Lin},
title = {New Results on the Density of Irreducible {NFSRs}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1680},
year = {2026},
url = {https://eprint.iacr.org/2026/1680}
}
