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.
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
.
DOI: 10.16183/j.cnki.jsjtu.2020.99.006
［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.
