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

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

作　　者：牛志华[1] 苑璨 孔得宇 NIU Zhihua;YUAN Can;KONG Deyu(School of Computer Engineering and Science,Shanghai University,Shanghai 200444,China)

机构地区：[1]上海大学计算机工程与科学学院,上海200444

出　　处：《上海交通大学学报》2020年第6期599-606,共8页Journal of Shanghai Jiaotong University

基　　金：国家重点研发计划项目(2016YFB1000600,2016YFB1000601,2016YFB10006011);国家自然科学基金重点项目(61936001);国家自然科学基金项目(61572309);上海市自然科学基金项目(16ZR1411200,17ZR1409800,19ZR1417700);科技部广东省部省联动项目(2018B010113001)。

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

关 键 词：密码学 周期序列 线性复杂度 K-错线性复杂度 遗传算法 

分 类 号：TN918.1[电子电信—通信与信息系统] TP18[电子电信—信息与通信工程]