3
$\begingroup$

Given a non-primitive LFSR sequence (i.e number of states is less than $2^n - 1$); how do we find out the the characteristic polynomial? Will Berlekamp-Massey algorithm work in this case?

for example; for the following sequence-

[1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1]

the repetition period is $105$. Applying the Berlekamp-Massey algorithm returns

$X^7 + X^6 + X^5 + X^1 + 1$

Doing manually gives me a different answer. Where am I going wrong?

EDIT

Adding what I did manually:

I found the primitive polynomials and took LCM to confirm the $Berlekamp-Massey$ output.

To check, I represented the polynomial as $11100011$ ; took the first seven bits of the sequence and did the $and$ operation with the polynomial. took the $xor$ of the output and appended that output to the initial 7 bits and continued. This is what I did to crosscheck the answer I received. It is here I went wrong probably.

$\endgroup$
4
$\begingroup$

A binary sequence of period $105$ will have characteristic polynomial that is a divisor of $x^{105}-1$. Since $x^{105}-1$ has irreducible factors of degrees $12, 4, 3$, and $1$, it is possible to have an LFSR of length $4+3=7$ generate a sequence of period $105$, and that is exactly what has happened here. Note that $$x^7+x^6+x^5+x+1 = (x^3+x+1)(x^4+x^3+1)$$ where $x^3+x+1$ and $x^4+x^3+1$ are irreducible (in fact, primitive) polynomials of degrees $3$ and $4$. Individually, the shorter LFSRs generate sequences of periods $7$ and $15$: the "product" sequence has period $\operatorname{lcm}(7,15)=105$.

$\endgroup$
1
$\begingroup$

Berlekamp Massey, correctly implemented, always gives the right linear complexity for a periodic sequence. There is a good resource online, magma calculator, which has an implementation, if you want to check what you're doing wrong. Click on the Cryptography chapter on the Handbook link and look under the last section for a Berlekamp-Massey command and an example on how to call it (need to use GF(2) as your field, as in the example).

Edit: Magma calculator confirms the polynomial above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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