二进制序列的k错误线性复杂度渐近分析

本文主要探讨了二进制序列的归一化k错误线性复杂度的研究，该主题发表在《Des Codes Cryptogr》(2012)期刊上，卷62，第313-321页。文章的DOI是10.1007/s10623-011-9519-8。作者林谭、文峰祁和洪旭在2011年1月7日收到修订稿，同年4月27日接受并最终于5月18日在线发布，版权归属Springer Science+Business Media。 线性复杂度和k错误线性复杂度是流密码中衡量序列性能的重要指标。本文针对一个尼德雷特定理开放问题中的问题，即对随机二进制序列的归一化k错误线性复杂度\( L_{n,k}(s)/n \)进行了深入的渐近分析。研究结果显示，当\( k = n\theta \)，其中\( 0 \leq \theta \leq \frac{1}{2} \)为固定比值时，得到了关于\( L_{n,k}(s)/n \)累积点的下界和上界的概率为1的界限。这意味着对于这类特定的k和n的关系，这种复杂度的行为有明确的极限性质。 另一方面，文章还证明了一个重要定理：对于任何固定的k，当n趋向于无穷大时，\( L_{n,k}(s)/n \)几乎必然收敛到1/2。这个结果揭示了随着序列长度的增长，归一化k错误线性复杂度的平均行为，具有深远的理论意义。 此外，文中还提供了关于二进制序列归一化k错误线性复杂度期望值的渐近界限，这在评估流密码性能以及设计新型序列时具有重要的实际应用价值。关键词包括流密码、二进制序列、线性复杂度和k错误线性复杂度，文章被归类在2000年的数学学科分类为94A55和94A6，表明了其在密码学和离散数学中的核心地位。 这篇研究论文不仅解决了尼德雷特定理中的一个问题，还扩展了我们对随机二进制序列线性复杂度理解，为流密码的设计与分析提供了理论依据。