计算周期序列k-错线性复杂度的混合遗传算法

作者：牛志华; 苑璨; 孔得宇

来源：上海交通大学学报, 2020, 54(06): 599-606.

DOI：10.16183/j.cnki.jsjtu.2020.99.006

• 密码学
• 周期序列
• 线性复杂度
• k-错线性复杂度
• 遗传算法

周期序列的线性复杂度及其稳定性是序列密码评价的重要度量指标.k-错线性复杂度是线性复杂度稳定性的一个重要评价指标.然而,目前对于大部分周期序列(除周期为2n、pn、2pn外),尚无有效的算法求解其k-错线性复杂度.因此,本文提出了一种混合的遗传算法来近似计算任意周期序列的k-错线性复杂度.采用轮盘赌、最优保留策略、两点交叉和单点随机变异,并引入自适应算子来调整交叉概率和变异概率,以保证遗传算法的收敛性.通过并行计算适应度函数来提高算法的效率,同时与模拟退火算法相结合,加速算法收敛并避免早熟.结果表明:当k<8且周期小于256时,k-错线性复杂度的实验值仅比精确值高8%.

• 单位
  上海大学