%0 DATA
%A Alexandra, Alecu
%A Ana, Salagean
%D 2008
%T Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences
%U https://repository.lboro.ac.uk/articles/Modified_Berlekamp-Massey_algorithm_for_approximating_the_k-error_linear_complexity_of_binary_sequences/9405239
%2 https://repository.lboro.ac.uk/ndownloader/files/17021951
%K Pseudorandom sequences
%K Stream ciphers
%K Linear complexity
%K K-error linear complexity
%X Some cryptographical applications use pseudorandom sequences
and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear
complexity. Efficient algorithms for computing the k-error linear complexity of a sequence only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. We show that the Berlekamp-Massey Algorithm, which computes the linear complexity of a sequence, can be adapted to approximate the k-error linear complexity profile
for a general sequence over a finite field. While the complexity of this algorithm is still exponential, it is considerably more efficient than the exhaustive search.