F_q上周期为q ^ n-1的序列的最小线性复杂度近似

本文所讨论的是在有限域F_q上具有周期为q^n-1的序列的最小线性复杂度近似问题。我们需要了解几个关键的密码学和数学概念。 线性复杂度是衡量序列密码安全性的核心参数，指的是一个序列的最小线性反馈移位寄存器（LFSR）的长度，该长度能产生该序列。序列的线性复杂度越高，其预测难度越大，因而安全性越高。一个序列的线性复杂度通常是通过Berlekamp-Massey算法计算得到的。 最小线性复杂度近似涉及的是对原始序列进行微小的改动，比如改变序列中的一个数字，然后确定这个改动对序列的线性复杂度产生的影响。这在研究序列密码攻击模型时非常重要，特别是研究所谓的“重量复杂度”和“k错误线性复杂度”。 重量复杂度指的是序列在去掉至多k个数字后，剩余部分的最小线性复杂度。它是衡量序列抵抗攻击能力的一个指标，可以用来评估在序列中存在错误或被干扰时，序列的复杂度变化。 k错误线性复杂度则是指从原始序列中至多有k个数字错误的序列的最小线性复杂度。这个概念与重量复杂度类似，但它关注的是在序列存在错误的情况下，其复杂度的变化。 本研究提出的两个算法专门用来确定给定周期为q^n-1的序列，与另一个序列相比，只在一个数字上存在差异时的最优移位和最小线性复杂度。这项研究对设计和评估序列密码系统具有重要意义。 此外，文中还提到了m序列，即最大周期的q-进制序列。它们是由n级线性反馈移位寄存器生成的序列，并满足三个随机性属性：平衡分布、良好的游程特性以及理想自相关特性。m序列在实际应用中易于实现，因此它们通常被用作流密码的组成部分，以确保有较大的周期。在给定线性复杂度的所有序列中，m序列往往被选用，以保证流密码的安全性。 研究论文的撰写背景在于，随着流密码的研究不断深入，对伪随机序列的评价标准也在不断提高。通过对原始序列进行小的改动（比如改变一个数字）来观察线性复杂度的变化，有助于更好地理解序列的稳定性和安全性。因此，本研究不仅对于理论研究者具有重要价值，对于实际应用中的密码系统设计也有着实际的指导意义。