周期序列的线性复杂度及其稳定性是序列密码评价的重要度量指标.k-错线性复杂度是线性复杂度稳定性的一个重要评价指标.然而，目前对于大部分周期序列(除周期为2n、pn、2pn外)，尚无有效的算法求解其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 k-error linear complexity is only 8% higher than the exact value when k<8 and the period is less than 256.
［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.
