Как вы можете найти полином для уничтоженной LFSR?

Question

Я знаю, что если вы уничтожите ряд, сгенерированный регистром сдвига с линейной обратной связью, вы получите новый ряд и новый многочлен. Например, если вы выберете каждый пятый элемент в ряду, сгенерированном LFSR с полиномом x ⁴ + x + 1, вы получите ряд, сгенерированный как x ² + x + 1. Я могу найти второй многочлен (x ² + x + 1) грубой силой, что хорошо для полиномов низкого порядка. Однако для полиномов высшего порядка время, необходимое для грубой силы, становится неоправданным.

Таким образом, вопрос: возможно ли аналитически найти прореженный полином?

Answer 1

Недавно прочитал эту статью и подумал об этом, увидев ваш вопрос, надеюсь, это поможет ..: oÞ

Учитывая примитивный многочлен над GF (q), можно получить другой примитивный многочлен, прореживая последовательность LFSR, полученную из исходного многочлена. Это продемонстрировано в коде ниже.

K: = GF (7); C: = примитивный полином (K, 2); C; D ^ 2 + 6 * D + 3 Чтобы сгенерировать последовательность LFSR, мы должны сначала умножить этот многочлен на подходящую константу, чтобы конечный коэффициент стал равным 1.

C: = C * Коэффициент (C, 0) ^ - 1; C; 5 * D ^ 2 + 2 * D + 1 Теперь мы можем сгенерировать LFSR-последовательность длиной 72-1. Начальное состояние может быть любым, кроме [0, 0].

t: = LFSRSequence (C, [K | 1,1], 48); т; [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] Мы прореживаем последовательность значением d, имеющим свойство gcd (d, 48) = 1.

t: = прореживание (t, 1, 5); т; [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 (т); B; 3 * Д ^ 2 + 5 * Д + 1 Чтобы получить соответствующий примитивный многочлен, мы умножаем на константу, чтобы сделать ее моничной.

B: = B * Коэффициент (B, 2) ^ - 1; B; D ^ 2 + 4 * D + 5 IsPrimitive (В); правда

Answer 2

из этих примечаний : "Обрезание по n> 0 m-последовательности c, обозначаемой как c [n], имеет период, равный N / gcd (N, n), если он не равен нулю последовательность, ее порождающий полином gˆ (x) имеет корни n степени корней из g (x) "