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