广义多项式商构造的二元序列线性复杂度分析

"基于广义多项式商的二元序列线性复杂度研究" 这篇研究论文主要探讨了在密码学领域中，如何利用广义多项式商来构建具有高线性复杂度的二元序列，以增强序列的安全性，抵御如Berlekamp-Massey算法的攻击。线性复杂度是衡量伪随机序列安全性的重要指标，它反映了通过线性探测算法恢复序列规律所需的最少数目。在通信保密和密码系统中，高线性复杂度的序列能提供更好的安全保证。 作者万韫琦和杜小妮首先回顾了费马商在设计密码本原中的应用，费马商及其扩展函数已经被证明是构造伪随机序列的有效工具。他们将研究焦点从模素数p的多项式商扩展到了模r p(1 r≤)的情形，引入了新的商式，以此构造出周期为r p+1的二元门限序列。这里的r是一个正整数，而p是模运算的基数，通常选择为奇素数，因为这可以确保序列的某些理想性质。 论文的核心贡献在于，作者分析了当w取任意值且2为模2 p的本原根时，这些新序列的线性复杂度。本原根是指在模p下，2能够生成所有非零剩余类的乘法群，这是一个关键条件，因为它影响序列的代数性质。通过结合分圆多项式（ cyclotomic polynomial）和序列满足的线性递归关系，他们成功地推导出了序列的线性复杂度特性。 论文的结果不仅扩展了之前关于费马商序列的研究，还提出了具有高线性复杂度的新序列，这表明它们在实际应用中可能更难被破解。特别是，由于这些序列能够抵抗Berlekamp-Massey算法，这种广泛使用的线性复杂度估计方法，因此它们在保密通信、扩频通信以及流密码系统等场景中具有潜在的应用价值。 这篇论文对基于广义多项式商的二元序列的线性复杂度进行了深入研究，为密码学和信息安全领域的理论研究及实际应用提供了新的思路和方法。通过这种方式构造的序列，有望在未来的设计中提升密码系统的安全性。