Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence:

$0110010101101$ producing LFSR $\langle{}7, 1 + x^3 + x^4 + x^6\rangle{}$

i.e. coefficients $c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, c_6 = 1, c_7 = 0$

However, when using the recurrence relation

\begin{equation} s_j = (c_1s_{j-1} + c_2s_{j-2} + \cdots + c_Ls_{j-L}) \mbox{ for } j \geq L. \end{equation} to check the result, I get back:

0110010001111, which is obviously not right.

Using the Berlekamp-Massey Algorithm calculator they say the (I believe) characteristic polynomial should be $x^7 + x^4 + x^3 + x^1$. Which, according to my paper working, the reciprocal should indeed be $1 + x^3 + x^4 + x^6$.

What am I doing wrong? Where is my understanding lacking?

share|improve this question

closed as off-topic by mikeazo May 13 at 12:24

  • This question does not appear to be about cryptography within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

    
Cross-posted on Math.SE. Please don't cross-post. That fragments answers and violates site rules. –  D.W. May 12 at 22:22
    
This question appears to be off-topic because it was cross-posted and was better off on the other site anyways. –  mikeazo May 13 at 12:24

2 Answers 2

This is probably just a difference in notation than any failure in understanding or implementation. Some people define recurrence relations with subscripts in reverse order than others; the original description given by Berlekamp in his 1968 book Algebraic Coding Theory began counting from $1$ instead of $0$ etc. Observe that $$x^7 + x^4 + x^3 + x^1 = x^7(1 + x^{-3} + x^{-4} + x^{-6})$$ in comparison to your $1 + x^3 + x^4 + x^6$ which you say is the correct reciprocal of what the web site's answer should be. So I would say that the web site seems to be following Berlekamp's original description and giving you an answer that is "off-by-one".

share|improve this answer

Unfortunately, there was an implementation problem.

Quoting Jyrki Lahtonen on Mathematics Stack Exchange:

It seems to me that something went wrong, when you tried to regenerate the sequence. When the linear span is $7$ and the feedback polynomial is $1+x^3+x^4+x^6$, we have the recurrence relation $$ s_j=s_{j-3}+s_{j-4}+s_{j-6} $$ for all $j\ge 7$.

Your sequence has $s_0=0$, $s_1=1$, $s_2=1$, $s_3=0$, $s_4=0$, $s_5=1$, $s_6=0$ as the initial segment. Using the above recurrence relation gives $$ \begin{aligned} s_7&=s_4+s_3+s_1=1,\\ s_8&=s_5+s_4+s_2=0,\\ s_9&=s_6+s_5+s_3=1,\\ s_{10}&=s_7+s_6+s_4=1,\\ s_{11}&=s_8+s_7+s_5=0,\\ s_{12}&=s_9+s_8+s_6=1, \end{aligned} $$ recovering the remaining of your input.

share|improve this answer
2  
Hi jamesj629 and welcome to crypto. Please provide a short summary of the document you linked. –  Hendrik Brummermann Aug 29 '12 at 22:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.