• 学报（中文） •

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

1. 上海大学 计算机工程与科学学院，上海 200444
• 出版日期:2020-06-28 发布日期:2020-07-03
• 通讯作者: 牛志华（1976-），女，山西省晋中市人，副教授，主要研究方向为序列密码. 电话（Tel.）：021-66135387；E-mail：zhniu@shu.edu.cn.
• 基金资助:
国家重点研发计划项目(2016YFB1000600，2016YFB1000601，2016YFB10006011)，国家自然科学基金重点项目(61936001)，上海市自然科学基金项目（16ZR1411200，17ZR1409800，19ZR1417700），科技部广东省部省联动项目（2018B010113001），国家自然科学基金项目（61572309）

### A Hybrid Genetic Algorithm for Computing the k-Error Linear Complexity of Periodic Sequences

NIU Zhihua,YUAN Can,KONG Deyu

1. School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China
• Online:2020-06-28 Published:2020-07-03

Abstract: The linear complexity of periodic sequences and its stability are important metrics for the evaluation in stream cipher. The k-error linear complexity is an important evaluation index for the stability of linear complexity. However, at present, it is difficult to compute the k-error linear complexity of the period sequences (except for 2n、pn、2pn). Therefore, a hybrid genetic algorithm is proposed to approximate the k-error linear complexity of arbitrary periodic sequences by adopting the roulette wheel and elitist reserved strategy, the two-point crossover and simple random mutation, and by introducing adaptive operators to adjust the crossover and mutation probabilities to ensure the convergence of the genetic algorithm. The efficiency of the algorithm is improved by using the parallel computing fitness function. Simultaneously, by combining with the simulated annealing algorithm, it increases the convergence speed and avoids the premature convergence. The results show that the experiment value of k-error linear complexity is only 8% higher than the exact value when k<8 and the period is less than 256.