Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm trying to use the Berlekamp-Massey algorithm on the following bit sequence:

0 1 0 0 1 0 0 1 0 1

I have the correct answer and most of the approach to get there, but I'm unable to fill in what I don't have, in other words I don't understand how it works.

I create a table, written horizontally here just for convenience:

N: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 S_N: Ø, ... f_N: 1, ... L_N: 0, ...

Where ... means the values I should determine using the BM algorithm. Ø is the empty set.

I have already filled in the values for S_0, f_0 and L_0, as these are trivial.

My first step is to calculate f_1:

This is the formula that I use, this is directly copied from some printed lecture notes, so it should be correct.

$$f_1 = \begin{cases} f_N + X^{2L-N-1}\cdot f_m, & \mbox{if } L > N/2 \\ X^{N-2L+1}\cdot f_N + f_m, & \mbox{if } L \leq N/2 \end{cases}$$

We see that for the case of f_1, L = 0 and N = 0, hence we use the lower case:

$$f_1 = X^{N-2L+1}\cdot f_N + f_m = X^{0-2\cdot 0+1}\cdot 1 + 1 = X + 1$$

However, from my known solution I know f_1 should be 1. I have double checked this, why do I get X + 1 when I just mechanically follow this simple formula? Is there something more to this that I'm overlooking?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.