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

doi:10.16183/j.cnki.jsjtu.2020.99.006

上海交通大学学报 ›› 2020, Vol. 54 ›› Issue (6): 599-606.doi: 10.16183/j.cnki.jsjtu.2020.99.006

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

牛志华，苑璨，孔得宇

上海大学计算机工程与科学学院，上海 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

School of Computer Engineering and Science, Shanghai University, Shanghai 200444, China

Online:2020-06-28 Published:2020-07-03

摘要/Abstract

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

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

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.

Key words: cryptography, periodic sequences, linear complexity, k-error linear complexity, genetic algorithm

中图分类号:

TN 918.1

牛志华, 苑璨, 孔得宇. 计算周期序列k-错线性复杂度的混合遗传算法[J]. 上海交通大学学报, 2020, 54(6): 599-606.

NIU Zhihua, YUAN Can, KONG Deyu. A Hybrid Genetic Algorithm for Computing the k-Error Linear Complexity of Periodic Sequences[J]. Journal of Shanghai Jiaotong University, 2020, 54(6): 599-606.

参考文献

［1］MASSEY J. Shift-register synthesis and BCH decoding［J］. IEEE Transaction on Information Theory, 1969, 15(1): 122-127. ［2］GAMES R, CHAN A. A fast algorithm for determining the complexity of a binary sequence with period 2n［J］. IEEE Transaction on Information Theory, 1983, 29(1): 144-146. ［3］KE P H, CHANG Z L. On the error linear complexity spectrum of binary sequences with period of power of two［J］. Chinese Journal of Electronics, 2015, 24(2): 366-372. ［4］ZHOU J, LIU W. The k-error linear complexity distribution for 2n-periodic binary sequences［J］. Designs Codes and Cryptography, 2014, 73(1): 55-75. ［5］PAN W, BAO Z, LIN D, et al. The distribution of 2n-periodic binary sequences with fixed k-error linear complexity［C］∥International Conference on Information Security Practice and Experience. Zhangjiajie, China: Springer, 2016: 13-36. ［6］TANG M, ZHU S. On the error linear complexity spectrum of pn-periodic binary sequences［J］. Applicable Algebra in Engineering Communication and Computing, 2013, 24(6): 497-505. ［7］LI F L, ZHU S, HU H, et al. Determining the k-error joint linear complexity spectrum for a binary multisequence with period pn［J］. Cryptography and Communications, 2016, 8(4): 513-523. ［8］TANG M. An algorithm for computing the error sequence of pn-periodic binary sequences［J］. Applicable Algebra in Engineering, Communication and Computing, 2014, 25(3): 197-212. ［9］ZHOU J. On the k-error linear complexity of sequences with period 2pn over GF (q)［J］. Designs Codes and Cryptography, 2011, 58(3): 279-296. ［10］YU F W, SU M, WANG G, et al. Error decomposition algorithm for approximating the k-error linear complexity of periodic sequences［C］∥Trustcom/BigDataSE/ISPA. Tianjin, China: IEEE, 2016: 505-510. ［11］NIU Z, CHEN Z, DU X. Linear complexity problems of level sequences of Euler quotients and their related binary sequences［J］. Science China Information Sciences, 2016, 59(3): 1-12. ［12］LIU L F, YANG X Y, DU X N, et al. On the linear complexity of new generalized cyclotomic binary sequences of order two and period pqr［J］. Tsinghua Science and Technology, 2016, 21(3): 295-301. ［13］ZHAO C, MA W, YAN T, et al. Linear complexity of least significant bit of polynomial quotients［J］. Chinese Journal of Electronics, 2017, 26(3): 573-578. ［14］CHEN Z, NIU Z, WU C. On the k-error linear complexity of binary sequences derived from polynomial quotients［J］. Science China Information Sciences, 2015, 58(9): 1-15. ［15］LIU L, YANG X, DU X, et al. On the k-error linear complexity of generalised cyclotomic sequences［J］. International Journal of High Performance Computing and Networking, 2016, 9(5/6): 394-400. ［16］ALECU A, SALAGEAN A. A genetic algorithm for computing the k-error linear complexity of cryptographic sequences ［C］∥IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007: 3569-3576. ［17］SRINIVAS M, PATNAIK L. Adaptive probabilities of crossover and mutation in genetic algorithms［J］. IEEE Transactions on Systems Man and Cybernetics, 1994, 24(4): 656-667. ［18］HERDA M. Parallel genetic algorithm for capacitated p-median problem ［J］. Procedia Engineering, 2017, 192: 313-317. ［19］LAN S, LIN W. Genetic algorithm optimization research based on simulated annealing ［C］∥International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing. Shanghai, China: IEEE, 2016: 491-494. ［20］PENG Y, LUO X, WEI W. A new fuzzy adaptive simulated annealing genetic algorithm and its convergence analysis and convergence rate estimation［J］. International Journal of Control Automation and Systems, 2014, 12(3): 670-679.

[1]	闫青, 鲁建厦, 江伟光, 邵益平, 汤洪涛, 李英德. 考虑双端口布局的紧致化仓储系统堆垛机路径优化[J]. 上海交通大学学报, 2022, 56(7): 858-867.
[2]	周天颜, 冯小恩, 范云锋, 董诗音, 李玉庆, 金慧中. 避免防空火力过剩的地面兵力防御部署优化模型[J]. 空天防御, 2022, 5(4): 19-23.
[3]	王箫剑, 洪君, 陈晶华, 李鸿光. 基于参数化建模和响应面优化的箱体减重研究[J]. 空天防御, 2022, 5(4): 60-66.
[4]	王卓鑫, 赵海涛, 谢月涵, 任翰韬, 袁明清, 张博明, 陈吉安. 反向传播神经网络联合遗传算法对复合材料模量的预测[J]. 上海交通大学学报, 2022, 56(10): 1341-1348.
[5]	陶海红, 闫莹菲. 一种基于GA-CNN的网络化雷达节点遴选算法[J]. 空天防御, 2022, 5(1): 1-5.
[6]	周宇泰, 徐岳, 李宇, 蒋国韬. 基于遗传算法的干扰态势下三维雷达网优化布站方法[J]. 空天防御, 2022, 5(1): 52-59.
[7]	李翠明, 王宁, 张晨. 基于改进遗传算法的光伏板清洁分级任务规划[J]. 上海交通大学学报, 2021, 55(9): 1169-1174.
[8]	顾一凡, 赵文龙, 唐善军, 杨擎宇, 郑鑫. 分布式主/被动成像探测系统目标空间协同定位方法研究[J]. 空天防御, 2021, 4(4): 119-126.
[9]	卓鹏程, 严瑾, 郑美妹, 夏唐斌, 奚立峰. 面向滚动轴承全生命周期故障诊断的GA-OIHF Elman神经网络算法[J]. 上海交通大学学报, 2021, 55(10): 1255-1262.
[10]	王金凤, 陈璐, 杨雯慧. 考虑设备可用性约束的单机调度问题[J]. 上海交通大学学报, 2021, 55(1): 103-110.
[11]	康俊涛, 张亚州, 秦世强. 基于一种混合智能算法的有限元模型修正多解问题[J]. 上海交通大学学报, 2020, 54(6): 652-660.
[12]	戴少怀, 王磊, 李旻, 余科, 罗晨. 基于遗传算法的SVM自适应干扰样式选择[J]. 空天防御, 2020, 3(2): 59-64.
[13]	姚来鹏, 侯保林, 刘曦. 采用摩擦补偿的弹药传输机械臂自适应终端滑模控制[J]. 上海交通大学学报, 2020, 54(2): 144-151.
[14]	高云凯, 马超, 刘哲, 田林雳. 基于NSGA-III的白车身焊装生产平台的离散拓扑优化[J]. 上海交通大学学报, 2020, 54(12): 1324-1334.
[15]	施振兴, 管再升, 王磊, 施臣钢, 伍彬. 基于遗传算法的自动驾驶仪参数多目标优化研究[J]. 空天防御, 2020, 3(1): 41-49.

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

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价