How can you find the polynomial for the destroyed LFSR?

Question

I know that if you destroy a series generated by a linear shift register with feedback, you will get a new series and a new polynomial. For example, if you select every fifth element in a series created by LFSR with polynomial x ⁴ + x + 1, you get a series generated by x ² + x + 1. I can find the second polynomial (x ² + x + 1) by brute force, which is great for low order polynomials. However, for higher order polynomials, the time required for brute force becomes unreasonable.

So, the question arises: is it possible to analytically analyze the analyzed polynomial?

Answer 1

I recently read this article and thought about it, seeing my question, I hope this helps ..: oÞ

Given a primitive polynomial over GF (q), we can obtain another primitive polynomial by omitting the LFSR sequence obtained from the original polynomial. This is shown in the code below.

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

C: = C * Coefficient (C, 0) ^ - 1; C; 5 * D ^ 2 + 2 * D + 1 Now we can 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 the value of 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, multiply by a constant to make it monodic.

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