Cryptanalysis of Linear Feedback Shift Registers It is well known that simple m-sequence linear feedback shift registers have a linear algebraic structure and therefore the generator seed can easily be deduced using the Berlekamp-Massey algorithm. Are there any other algorithms that can that can be used to "break" LFSR's and if so how does the algebra of said algorithm(s) compare to the Berlekamp-Massey algebra?
The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem.


  Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the
  shortest linear feedback shift register (LFSR) that generates this sequence.


Here, LFSR is a linear array of $n$ elements with initial value
$$(s_0, \quad s_1,\quad  \ldots, \quad s_{n-2}, \quad s_{n-1})$$ and successive values
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\\
\downarrow\\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\\
\downarrow\\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\\
\downarrow\\
\cdots \quad \cdots$$
where the array contents shift leftwards at each step (clock cycle) 
so that the field elements falling
off the left end (the LFSR output) are the given sequence, while 
the field elements shown as entering the LFSR on the right*
 are being computed as a linear combination of the LFSR
contents at the previous step.  In particular, for $i \geq 0$,
the state transition can be expressed as
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\\
\downarrow\\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad \sum_{j=0}^{n-1}c_{n-j} s_{i+j}\biggr),$$
that is, the linear combination 
$c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$ of previous
LFSR contents is being fed back into the right end of the LFSR
as $s_{n+i}$
(and hence the name linear feedback shift register).

As mentioned previously, the Berlekamp-Massey algorithm
finds the shortest LFSR that generates the given
sequence meaning it figures out the values of the
$c_i$ elements.  The iterative process consists of finding
the shortest LFSR that generates the first $t$ elements
$s_0, s_1, \ldots s_{t-1}$ and checking if the LFSR
finds $s_t$ correctly. If so, $s_{t+1}$ is checked,
while if not, the $c_i$'s are updated so that the
revised LFSR generates $s_t$. If the sequence was 
indeed created by a
$n$-stage LFSR as described above, the Berlekamp-Massey
algorithm finds all $n$ coefficients $c_i$ after 
examining $s_0, s_1, \ldots, s_{2n-1}$.  From this
point onwards, the Berlekamp-Massey algorithm can
continue checking the rest of the sequence (if so
desired) but does not need to update the $c_i$'s
because each check of the next symbol simply reports
back that everything is OK.



Let $S(z) = \sum_i s_i z^i$ and $C(z) = -1 + \sum_{i=1}^n c_iz^i$
denote generating functions of the given sequence and 
LFSR feedback coefficients. Then, the equation
$$s_{i+n} = c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$$
is equivalent to saying that the coefficients of $z^{i+n}$
in the product $C(z)S(z)$ is $0$ for all $i \geq 0$. But
the coefficients of $z^0, z^1, \ldots, z^{n-1}$ are not zero.
When only the first $2n$ symbols $s_0, s_1, s_{2n-1}$ have been
looked at, what the Berlekamp-Massey algorithm has solved (thus
far) is the congruence
$$C(z)S(z) \equiv D(z) \bmod z^{2n}$$
where $\deg D(z) &lt; n$.  Indeed, Berlekamp's formulation
of what is now called the Berlekamp-Massey algorithm
envisioned solving congruences
$$C^{(m)}(z)S(z) \equiv D^{(m)}(z) \bmod z^{m}$$
(where $\deg D^{(m)} \leq m/2$) iteratively for 
$m=1, 2, \ldots, $ until arriving at the desired
solution at $m = 2n$.



Finally and at long last, the extended Euclidean algorithm
for polynomial greatest common divisors can be used to
solve the congruence 
$$C(z)S(z) \equiv D(z) \bmod z^{2n}.$$
Define $\hat{S}(z) = s_0 + s_1z + \cdots +s_{2n-1}z^{2n-1}$
and start the extended Euclidean algorithm to find the
gcd of $z^{2n}$ and $\hat{S}(z)$.  The extended Euclidean
algorithm begins with $r_0(z) = z^{2n}, r_1(z) = \hat{S}(z)$ and
finds the sequence of remainder polynomials
$r_2(z), r_3(z), \ldots$ etc where $r_i(z)$ is the remainder when
$r_{i-2}(z)$ is divided by $r_{i-1}(z)$. It also
expresses each $r_i(z)$ as 
$$r_i(z) = \alpha_i(z)r_0(z) + \beta_i(z)r_1(z)$$
where polynomials $\alpha_i(z)$ and $\beta_i(z)$
are computed iteratively.  Consider the smallest
value of $i$ for which $\deg r_i(z) &lt; n$.  We have
$$r_i(z) = \alpha_i(z)z^{2n} + \beta_i(z)\hat{S}(z)$$
and so
$$\beta_i(z)\hat{S}(z) \equiv r_i(z) \bmod z^{2n}.$$

Notice that the Euclidean algorithm processes the 
the $s_i$ in descending order of subscripts whereas
the Berlekamp-Massey algorithm processes the $s_i$ in
ascending order of subscripts. The Euclidean algorithm
can be reformulated to process the $s_i$ in increasing
order of subscripts in which case it is virtually
indistinguishable from the Berlekamp-Massey algorithm.
Either way, the algorithms have very similar
computational
complexity.



For details on the extended Euclidean algorithm and its
connections to the Berlekamp-Massey algorithm, see
R. E. Blahut's Algebraic Codes for Data Transmission,
Cambridge Press 2003.