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
add comment

2 Answers

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
add comment

Unfortunately, there was an implementation problem.

see http://math.stackexchange.com/questions/134545/finding-the-lfsr-and-connection-polynomial-for-binary-sequence for the full explanation

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

Your Answer

 
discard

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

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