Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Suppose that we have a sequence of $N$ digits which is produced by a Linear Feedback Shift Register (LFSR) and the shortest such LFSR is of length $L$. A very important tool in cryptanalysis of stream ciphers (among many other things) is the Berlekamp-Massey algorithm; if $2L\leq N$, this algorithm will produce the unique shortest LFSR of length $L$ that generates the given sequence.

I just knew this as a fact but never really gave a look at the algorithm. Now I'm reading the paper by Massey that presents the algorithm and I was kind of surprised to realize that the algorithm returns a desired LFSR in any case, even if $2L&gt;N$, however in that case we don't have a unique LFSR that generates the sequence, but $2L-N$ of them (in the binary case).

So why do we always refer to the Berlekamp-Massey algorithm only for the case when $2L\leq N$? Practically speaking, what kind of lengths $L$ do we use in cryptosystems, and can the algorithm be used when $2L&gt;N$ and $N$ is "reasonably" close to $2L$? Or is the algorithm useless in that case regardless?
The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence.
Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the 
algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for 
$i = t, t+1, \ldots, {n-1}$, the following equation holds:
$$
S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t = 0,
\tag{1}
$$
that is,
$$S_i = -\bigr(S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \cdots + S_{i-t}\lambda_t
\bigr).
\tag{2}$$
Note that for $i=t$, we have
$$S_{t} = -\bigr(S_{t-1}\lambda_{1} + S_{t-2}\lambda_2 + \cdots + S_{0}\lambda_t
\bigr)\tag{3}$$
The idea is that the initial loading of the LFSR is $(S_0, S_1, \ldots, S_{t-1})$, 
and the weighted sum of the LFSR contents stated in $(3)$ is fed back
into the right end of the shift register as the LFSR contents shift one place
to the left. Thus, the new state of the LFSR is $(S_1, S_2,\ldots, S_{t-1}, S_t)$. In later clock cycles,
the LFSR will contain $(S_{i-t}, S_{i-t+1},\ldots, S_{i-1})$, the feedback
will compute $S_i$ as given in $(2)$ and so the new state of the LFSR
is $(S_{i-t+1}, S_{i-t+2},\ldots, S_{i-1}, S_i)$.  The output of the
LFSR is the symbol falling off the left end and is thus $S_0, S_1, \ldots, S_{n-1}$.

The dsp.SE reader will recognize that if we define polynomials
$$S(z) = S_0 +S_1z + \cdots + S_{n-1}z^{n-1}, ~~ 
\Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_tz^t,$$
then the left side of $(1)$ is the coefficient of $z^i$ in the
product $S(z)\Lambda(z)$. Thus, the product $S(z)\Lambda(z)$
contains no terms of degree $t, t+1, \ldots, n-1$.

Turning to the problem at hand, if the given sequence can in fact,
generated by a LFSR of length $L$ (where $L$ is the length of the shortest
LFSR capable of generating $S(z)$), and if $n \geq 2L$, then
the Berlekamp-Massey algorithm will find the feedback coefficients
$\lambda_1, \lambda_2, \lambda_L$ of the unknown LFSR as soon
as it has examined the first $2L$ terms $S_0, S_1, \ldots, S_{2L-1}$
of the given sequence. It will then process the remaining terms
$S_{2L}, S_{2L+1}, \ldots, S_{n-1}$ of the sequence, and will discover 
that the same LFSR that it has
already found will generate these remaining terms as well.

It is important to remember that the Berlekamp-Massey algorithm
will find the shortest LFSR that will generate 
$(S_0, S_1, \ldots, S_{n-1})$, and this LFSR
might not be the same one
that was actually used to generate $(S_0, S_1, \ldots, S_{n-1})$.
Any sequence that can be generated via a LFSR with feedback polynomial
$\Lambda(z)$ can also be generated via a (longer) LFSR with feedback
polynomial $\Lambda(z)\Psi(z)$, and the Berlekamp-Massey algorithm
will find the shortest shift register that works.

What if $L$ is such that $2L &gt; N$, then the Berlekamp-Massey
algorithm will find the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$. The length of this LFSR
will generally not be $L$ and its feedback coefficients will in
general not be the same as those of the actual LFSR
that was used to generate the sequence. If at a later time,
the terms $S_{n}, S_{n+1}, \ldots, S_{2L-1}$ become known,
the algorithm will extend the LFSR and ultimately come up
with the right answer, but for now, it will simply find
the shortest LFSR that will generate
$(S_0, S_1, \ldots, S_{n-1})$.



In broad terms, the Kolmogorov-Chaitin theory of complexity
of a sequence
says that for almost all sequences of length $n$, the shortest
program that can print out the sequence has length $n+c$ where
$c$ is a constant. In other words, for most sequences, one can do
little better than simply store the sequence in memory and print it out: there
are no computational methods that will allow you to generate
the sequence via calculations. Thus, given an arbitrary sequence
of length $n$, the Berlekamp-Massey algorithm will typically
find an LFSR of length $n-1$ that stores the first $n-1$ symbols
and then calculates $S_{n-1}$ via $(2)$ with $t = i = n-1$.

The answer to the OP's question


  "...can the algorithm be used when $2L&gt;N$ and $N$ is "reasonably" close to $2L$?"


is that the algorithm can be used, and it will find the
shortest LFSR
that will generate  $(S_0, S_1, \ldots, S_{n-1})$, but
this LFSR will typically not be of length $L$ and
the feedback polynomial will typically differ from
that of the LFSR of length $L$ that is known to
generate $(S_0, S_1, \ldots, S_{n-1})$.