Последовательность Фибоначчи как ЛРП или что делать, если хочется найти период у бесконечной последовательности?

Июн 21, 2025 0

Что же такое ЛРП или линейная рекуррентная последовательность? Последовательность, которую можно задать рекуррентным уравнением $s_{n+k} = a_{k-1}s_{n+k-1} + ... + a_{0}s_{k}$ , где коэффициенты — фиксированные элементы поля F_q и есть ЛРП над полем F_q .

Сопровождающая матрица ЛРП выглядит следующим образом:

$A = begin{pmatrix} 0 & 0 & 0 & cdots & 0 & a_0 \ 1 & 0 & 0 & cdots & 0 & a_1 \ 0 & 1 & 0 & cdots & 0 & a_2 \ vdots & vdots & vdots & ddots & vdots & vdots \ 0 & 0 & 0 & cdots & 1 & a_{k-1} end{pmatrix}$ .

Её характеристический многочлен: $f(x) = |xE - A| = x^k - a_{k-1}x^{k-1} - ldots - a_1x_1 - a_0$

Упражняться в теории ЛРП мы будем не на случайных примерах, а искать так называемый период Пизано, то есть период последовательности Фибоначчи по простому модулю. Про сам этот период написано довольно много, но моё домашнее задание было достаточно конкретным, продемонстрировать связь порядка и периода. Я же, в качестве бонуса, опишу стратегию поведения и для случая когда правило «порядок это период» не актуально.

mod 2

Над полем F_2 характеристический многочлен имеет следующий вид: f(x) = x^2 + x + 1 . Известно, что минимальный период ЛРП с неприводимым характеристическим многочленом (а он неприводим) при ненулевом начальном состоянии равен порядку многочлена f(x) . Есть два способа найти порядок:

Порядок неприводимого характеристического многочлена совпадает с порядком сопровождающей матрицы как элемента группы .
Порядок неприводимого многочлена делит , так как это всегда период (совпадает с порядком примитивного многочлена).

Второй быстрее. 2^2 - 1 = 3 — число простое, нетрудно, используя матрицу, убедиться, что период в точности 3.

$A = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix};$ $A^2 = begin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix};$ $A^3 = begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} = E.$

Также продемонстрируем это выписав саму последовательность Ф: 011011011011…

mod 3

Над полем F_3 характеристический многочлен уже имеет вид: f(x) = x^2 - x - 1 . Опять же по теории искомый порядок делитель числа 3^2 - 1 = 8 . Убеждаемся, что ни 2, ни 4 не подходят, то бишь искомый период ЛРП 8. Продемонстрируем это с помощью матриц:

$A = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix};$ $A^2 = begin{pmatrix} 1 & 1 \ 1 & 2 end{pmatrix};$ $A^3 =begin{pmatrix} 1 & 2 \ 2 & 0 end{pmatrix};$ $A^4 = begin{pmatrix} 2 & 0 \ 0 & 2 end{pmatrix};$ $A^5 = begin{pmatrix} 0 & 2 \ 2 & 2 end{pmatrix};$

$A^6 = begin{pmatrix} 2 & 2 \ 2 & 1 end{pmatrix};$ $A^7 = begin{pmatrix} 2 & 1 \ 1 & 0 end{pmatrix};$ $A^8 = begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix}= E.$

Снова продемонстрируем это выписав саму последовательность Ф: 01120221011…

mod 11

Над полем F_3 характеристический многочлен тоже имеет вид: f(x) = x^2 - x - 1 , отличие в том, что теперь он приводим. f(x) = x^2 - x - 1 = (x - 4)(x - 8) . Что же делать в таком случае, ведь ранее приводимые методы работают только для неприводимых многочленов, в этом случае применима следующая теорема:

Пусть таковы, что, если , ord() = , тогда ord(), где = НОК().

Порядки же теперь будем искать, так сказать, «по старинке». То есть будем искать минимальные l_1 и l_2 такие, что $x^{l_1} - 1$ и $x^{l_2} - 1$ делятся на x-4 и x-8 соответственно, причём достаточно перебирать только делители числа 11^2 - 1 = 120 . Путём перебора нетрудно получить, что l_1 = 5 , а l_2 = 10 . Следовательно, l = [5, 10] = 10 .

!!! В переборе также может помочь то, что порядок многочлена равен порядку его корня в мультипликативной группе соответствующего поля $F_{p^n}$ (в нашем случае p = 11, а n = 1).

mod 5

А теперь перейдём к самому интересному, на мой взгляд, случаю. Тут мы немного отойдём от конечным полей и обратимся к особенностям самой последовательности.

Так в чём же проблема?

Проблема в том, что над полем F_5 характеристический многочлен является полным квадратом: x^2 - x - 1 = (x - 2)^2 , а на такой случай у нас теории нет.

Для ответа на вопрос какой же всё-таки период обратимся к истокам. Доказательство формулы можно найти здесь https://www.fq.math.ca/Scanned/1-2/robinson.pdf. Мне оно кажется исчерпывающим и не требующим дополнительных комментариев, так что ограничимся лишь формулировкой (Я немного перефразирую автора дабы не заставлять читателя предварительно знакомиться с обозначениями оригинальной статьи).

Пусть — индекс первого, отличного от начального элемента, нуля в последовательности Фибоначчи , где модуль по которому рассматривается последовательность, тогда, если $(f_{n(N) + 1}, N) = 1$ , то , где $f_{n(N) + 1}^{m(N)} equiv 1$ (mod ).

Посмотрим на примере при N = 5: 0112303314044320224101123

Не забываем, что индексирование здесь начинается с нуля, то есть n(5) = 5 , следующий элемент последовательности тройка, которая взаимно проста с пятью, то есть можно найти m(5) :

(mod 5)
(mod 5)
(mod 5)
(mod 5) .

То есть период нашей последовательности T(5) = n(5)m(5) = 5 cdot 4 = 20 .

Оказывается

x^2 -x - 1 = (x - y)^2 над полем F_p эквивалентно системе сравнений

$begin{cases} -1 equiv -2y text{ mod p} \ -1 equiv y^2 text{ mod p} \ -2y equiv y^2 text{ mod p} end{cases} Rightarrow -2 equiv y text{ mod p, т.к. } y<p Rightarrow (y, p) = 1, text{ то есть } -1 equiv 4 text{ mod p},$