Вычисление длины периода линейной рекуррентной последовательности

Теорема 1. Пусть d Î S (f).  Тогда

t(d) = ord m _d(l).

Доказательство. Пусть t = t(d), t = ord m _d(l). Тогда для любого x Î N ₀ имеемd _x = d _{x + t}. Следовательно, (T ^t - 1)·d = 0. Поэтому, t £ t. С другой стороны,

m _d(l)| (l^t - 1).

Таким образом, (T ^t - 1)·d = 0, т.е. для любого x Î N ₀ имеемd _x = d _{x + t}. Поэтому t£ t. Из полученных неравенств получаем t =t.

Теорема 2. Если характеристический многочлен f уравнения ЛРП не приводим, то

f = m _d(l)

для любого ненулевого решения d этого уравнения.

Доказательство. По свойству минимального многочлена

m _d(l)| f.

Так как deg m _d(l) ³1, f неприводим и оба многочлена f и m _d(l) имеют старшие коэффициенты равные 1, то f = m _d(l).

Теорема 3. Если характеристический многочлен f уравнения ЛРП не приводим и d - решение этого уравнения, то

t(d) | (pⁿ - 1).

Доказательство. Из теорем 2 и 3 следует, что наименьший период решения d равен порядку характеристического уравнения ЛРП. Порядок характеристического уравнения ЛРП делит число pⁿ – 1. Поэтому  t(d) | (pⁿ - 1).

Следствие. Если характеристический многочлен f уравнения ЛРП примитивен и d - решение этого уравнения, то

t(d) = pⁿ - 1.

Доказательство. По определению примитивного многочлена, многочлен f –неприводим и имеет порядок равный pⁿ – 1. Тогда по теореме 2  

t(d) = ord m _d(l) = ord f = pⁿ - 1.

Теорема 4. Если d – главное решение ЛРУ, то

t(d) = ord f.

Доказательство. Если d – главное решение ЛРУ, то по определению набор решений (d, T ·d,…, T^{n - 1}· d) является базисом пространства S (f). Поэтому эти решения линейно независимы над F. Поэтому минимальный многочлен d имеет степень n и поэтому совпадает с характеристическим многочленом f. Тогда по теореме 1 t(d) = ord f.

Определение 1. Максимальной линейной рекуррентной последовательностью порядка n  называют ЛРП, если она является главным решением линейного рекуррентного уравнения с характеристическим многочленом степени n.

Следствие. Период максимальной линейной рекуррентной последовательности равен pⁿ - 1.

Пусть t = t(d), t = ord m _d(l). Тогда для любого x Î N ₀ имеемd _x = d _{x + t}. Следовательно

и 3 следует, что наименьший период решения d равен порядку характеристического уравнения ЛРП. Порядок характеристического уравнения ЛРП делит число pⁿ – 1. Поэтому t(d) | (pⁿ - 1).

Регистр сдвига

Определение 1. Регистром сдвига называют электронную схему, позволяющую вырабатывать последовательность, определяемую линейным рекуррентным уравнением.

Опишем электронную схему, физическая реализация которой позволяет вырабатывать псевдослучайную двоичную последовательность, задаваемую линейным рекуррентным уравнением. Схема состоит из элементов двух видов: один из них называется сумматором, а другой задержкой или ячейкой памяти.

Сумматор имеет два входа и один выход. Задержка имеет один вход и один выход. Они изображаются следующим образом:

 

 

Сумматор работает следующим образом: если на оба его входа подаются одинаковые сигналы (0 и 0 или 1 и 1), то на выход подается 0; если на оба его входа подаются разные сигналы (0 и 1 или 1 и 0), то на выход подается 1. Таким образом сумматор реализует сложение по mod 2.

 Задержка работает следующим образом: если на вход задержки подается в данный момент времени какой-нибудь сигнал (0 или 1), то в следующий момент времени на ее выход подается тот же сигнал.

Пример 1. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x + d _{x +1} + d _{x +3}.

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.

Пример 2. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x + d _{x +3}.

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110010001111010110… с наименьшим периодом, равным 15.

Опишем электронную схему, физическая реализация которой позволяет вырабатывать псевдослучайную последовательность в любом конечном поле Z _p, задаваемую линейным рекуррентным уравнением общего вида:

d _x+n = a ₁d _{x+n- 1} + a ₂d _{x+n- 2} + …+  a_n d _x                                              (1)

Схема уже состоит из элементов трех видов: один из них называется сумматором, другой задержкой или ячейкой памяти, а третий умножитель.

Сумматор и задержка имеют тот же самый вид, что и выше.

Сумматор реализует сложение в поле Z _p, т.е. сложение по mod p.

 Задержка работает следующим образом: если на вход задержки подается в данный момент времени какой-нибудь сигнал (0, 1,…, p -1), то в следующий момент времени на ее выход подается тот же сигнал.

Умножитель имеет один вход и один выход и имеет следующий вид: он реализует умножение элемента из поля Z _p на элемент a_i того же поля, т.е. умножение по mod p.

Пример 3. Рассмотрим схему, отвечающую уравнению

d _{x +4} = d _x +  d _{x +1} +2d _{x +3} в поле Z₃

 

 

Выбирая первоначальное заполнение следующим образом:

d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 1,

получим периодическую последовательность: 10110110110… с наименьшим периодом, равным 3.