Paper 2026/1680 Original: eprint.iacr.org/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}$.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2026-08-13: last updated
- 2026-08-13: published
- Short URL
- https://ia.cr/2026/1680
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}