Research On K-error Linear Complexity Of Any Periodic Seuquence And Error Sequence Of 2p~n-periodic Sequence

The linear complexity and its stability are of fundamental importance as complexity measures in evaluation of periodic sequences in stream cipher.The k-error linear complexity of periodic sequences is also a fundamental concept for assessing the stability of the linear complexity.However,there is no effective algorithm for the k-error linear complexity of non-special periodic(2~n,p~n,2p~n etc.)sequences.Not only do we need to know how much the linear complexity decreased after several bits have been changed,but also want to find out which positions have changed so that the linear complexity of the sequence decreased.In other words,we need to compute the k-error linear complexity and the error sequence of a sequence.At present,for the study of the error sequence of periodic sequence,there are definite algorithms for computing the error sequence of 2~n-periodic and p~n-periodic sequences.In sequence evaluation,this paper attempts to use improved genetic algorithm to compute the k-error linear complexity of any periodic sequences,analyzes the results obtained by the genetic algorithm,and does more in-depth research based on the results.Algorithms for computing the error sequence of 2p~n-periodic sequence have been studied.The main research contents are as follows:(1)Design a genetic algorithm to compute the k-error linear complexity of periodic sequences.First,we repeat the experiments of the designed genetic algorithm with different combinations of parameters,and pick out the best combination by experimental results.Then we use the best combination to compute the k-error linear complexity of sequences with different periods,q and small k,and compare the results and computing speed with exact algorithm's.Experiments showed that,with small k,the designed algorithm can get an approximate solution with the accuracy generally higher than 95%,and the time is far less than the exact algorithm.(2)An algorithm for computing the k-error linear complexity and corresponding error sequence of 2p~n-periodic sequences over GF(q).First,we analysis the feasibility and existence of error sequences of 2p~n-periodic sequences.Then,we design a trace function to track the vector cost in order to computing the error sequences.Experiments show that the error sequence e we get makes the linear complexity of(s+e)reach the k-error linear complexity of the sequence s.(3)An algorithm for computing the minimum number k so that the k-error linear complexity of s is not greater than a given constant c.The corresponding error sequence is also obtained by the trace function.First,we prove there exists an error sequence,which makes the linear complexity of(s+e)reaches the k-error linear complexity.Then,we prove that we can get the error sequence by calling the trace function.Finally,we provide an example to illustrate our algorithm.