## Modified Berlekamp-Massey algorithm for approximating the k-error linear complexity of binary sequences

online resource

posted on 21.04.2008 by Alexandra Alecu, Ana Salagean#### online resource

Any type of resource available online.

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.

### History

#### School

- Science

#### Department

- Computer Science