How can you find the polynomial for a decimated LFSR?

Question

I know that it if you decimate the series generated by a linear feedback shift register, you get a new series and a new polynomial. For example, if you sample every fifth element in the series generated by a LFSR with polynomial x^4+x+1, you get the series generated by x^2+x+1. I can find the second polynomial (x^2+x+1) by brute force, which is fine for low-order polynomials. However, for higher-order polynomials, the time required to brute force it gets unreasonable.

So the question is: is it possible to find the decimated polynomial analytically?

Answer 1

Recently read this article and thought of it when seeing your question, hope it helps.. :oÞ

Given a primitive polynomial over GF(q), one can obtain another primitive polynomial by decimating an LFSR sequence obtained from the initial polynomial. This is demonstrated in the code below.

K := GF(7); C := PrimitivePolynomial(K, 2); C; D^2 + 6*D + 3 In order to generate an LFSR sequence, we must first multiply this polynomial by a suitable constant so that the trailing coefficient becomes 1.

C := C * Coefficient(C,0)^-1; C; 5*D^2 + 2*D + 1 We are now able to generate an LFSR sequence of length 72 - 1. The initial state can be anything other than [0, 0].

t := LFSRSequence (C, [K| 1,1], 48); t; [ 1, 1, 0, 2, 3, 5, 3, 4, 5, 5, 0, 3, 1, 4, 1, 6, 4, 4, 0, 1, 5, 6, 5, 2, 6, 6, 0, 5, 4, 2, 4, 3, 2, 2, 0, 4, 6, 3, 6, 1, 3, 3, 0, 6, 2, 1, 2, 5 ] We decimate the sequence by a value d having the property gcd(d, 48)=1.

t := Decimation(t, 1, 5); t; [ 1, 5, 0, 6, 5, 6, 4, 4, 3, 1, 0, 4, 1, 4, 5, 5, 2, 3, 0, 5, 3, 5, 1, 1, 6, 2, 0, 1, 2, 1, 3, 3, 4, 6, 0, 3, 6, 3, 2, 2, 5, 4, 0, 2, 4, 2, 6, 6 ] B := BerlekampMassey(t); B; 3*D^2 + 5*D + 1 To get the corresponding primitive polynomial, we multiply by a constant to make it monic.

B := B * Coefficient(B, 2)^-1; B; D^2 + 4*D + 5 IsPrimitive(B); true