21.9 Периодические ЛРП над конечным полем.

Утверждение 21.18:
Линейная рекуррентная последовательность $u$ над полем $P$ является периодической тогда и только тогда, когда $m_u(x)$ периодический многочлен.
Если при этом последовательность $u$ периодическая, то $\Lambda(u)=\Lambda(m_u(x))$, $T(u)=T(m_u(x))$.

Доказательство:

По утверждению 21.6 $$F(x)u=0\Leftrightarrow{m}_u(x)|F(x),$$ в частности $$x^{\lambda}(x^t-e)u=0\Leftrightarrow{m}_u(x)|x^{\lambda}(x^t-e).$$

Теорема 21.12:
Пусть $P:=GF(q)$ поле характеристики $p$, многочлен $F(x)\in{P}[x]$ унитарен, каноническое разложение многочлена $F(x)$ имеет вид: $$F(x)=x^lG_1(x)^{k_1},\ldots,G_s(x)^{k_s},$$ $k:=\max\{k_1,\ldots,k_s\}$, тогда многочлен $F(x)$ периодический и $\Lambda(F)=l$, $T(F)=[T(G_1(x)),\ldots,T(G_s(x))]p^c$, где число $c\in\mathbb{N}_0$ определяестя из условия $p^{c-1}<k\leq{p}^c$.

Доказательство:

Введем следующие обозначения $G(x):=G_1(x)\cdots{G}_s(x)$, $H(x):=G_1(x)^{k_1}\cdots{G}_s(x)^{k_s}$, тогда по утверждениям 21.16, 21.17 $$ F(x)=x^lH(x)\Rightarrow\Lambda(F)=\max\{\Lambda(x^l),\Lambda(H)\}=\max\{l,0\}=l $$ $$T(F)=[T(x^l),T(H)]=[1,T(H)]=T(H).$$ По утверждению 21.16 $T(G)=[T(G_1),\ldots,T(G_s)]$, осталось доказать, что $T(H)=T(G)p^c$. Так как многочлен $G(x)$ реверсивный, то по утверждению 17.7 и п. 2 утверждения 21.15 $$ G(x)|x^{T(G)}-1\Rightarrow{G}(x)^k|\bigl(x^{T(G)}-1\bigr)^k\Rightarrow{G}(x)^k|\bigl(x^{T(G)}-1\bigr)^{p^c}=\left(x^{T(G)p^c}-1\right)\Rightarrow {H}(x)|x^{T(G)p^c}-1\Rightarrow{T}(H)|T(G)p^c $$ кроме того по следствию 21.9 $$G(x)|H(x)\Rightarrow{T}(G)|H(G)\Rightarrow\exists{d}\in\overline{0,c}:T(H)=T(G)p^d.$$ Осталость доказать, что $d\geq{c}$.
Для любого $i\in\overline{1,s}$ обозначим $m_i:=\deg{G}_i(x)$. Так как для любого $i\in\overline{1,s}$ $G_i(x)$ неприводим над $GF(q)$ и реверсивен, то по п. 2 теоремы 19.5, по п. 2 утверждения 21.15 $$ G_i(x)\bigl|x^{q^{m_i}}-x\Rightarrow{G}_i(x)\bigl|x^{q^{m_i}-1}-1\Rightarrow{T}(G_i)|q^{m_i}-1\Rightarrow(T(G_i),p)=1\Rightarrow(T(G),p)=1 $$ Многочлен $x^{T(G)}-1$ взаимнопрост со своей производной равной $x^{T(G)-1}\neq0$, следовательно, по следствию 7.9 многочлен $x^{T(G)}-1$ не имеет кратных корней. При этом по утверждению 17.7 $$x^{T(H)}-1=x^{T(G)p^d}-1=\bigl(x^{T(G)}-1\bigr)^{p^d}\Rightarrow{H}(x)\bigl|\bigl(x^{T(G)}-1\bigr)^{p^d}.$$ Кратность любого корня многочлена стоящего справа равна $p^d$, кратность корней многочлена стоящего слева (многочлен $H(x)$) не превосходит $k$, таким образом $p^{c-1}<k\leq{p}^d$, то есть $c\leq{d}$.

В силу доказанного результата для нахождения периода многочлена $F(x)$ осталось найти периоды неприводимых многочленов $G_i(x)$ входящих в каноническое разложение $F(x)$.

Утверждение 21.19:
Пусть $P:=GF(q)$, многочлен $F(x)\in{P}[x]$ неприводимый, унитарный, реверсивный, $m:=\deg{F(x)}>0$, тогда период многочлена $F(x)$ равен порядку его корня в поле разложения $GF(q^m)$, при этом $T(F)|q^m-1$ и для любого $r\in\overline{1,m-1}$ $T(F)\nmid{q}^{r-1}-1$.

Доказательство:

Пусть $a\in{G}F(q^m)$ - корень многочлена $F(x)$, тогда так как многочлен $F(x)$ реверсивен, то $F(x)|x^{T(F)}-1$, следовательно, $a$ - корень многочлена $x^{T(F)}-1$, то есть $a^{T(F)}=1$, следовательно, по п. 2 теоремы 9.16 $\Ord{a}|T(F)$.
С другой стороны, многочлены $F(x)$ и $x^{\Ord{a}}-1$ имеют общий корень $a$, следовательно, они не взаимнопросты над $GF(q^m)$, тогда они не взаимнопросты над $GF(q)$. Многочлен $F(x)$ неприводим над $GF(q)$, следовательно, $F(x)|x^{\Ord{a}}-1$, тогда по п. 2 утверждения 21.15 $T(F)|\Ord{a}$, то есть $T(F)=\Ord{a}$. Тогда из п.1 следствия 19.2 следует, что $T(F)|q^m-1$, из п. 2 следствия 19.2 следует, что для любого $r\in\overline{1,m-1}$ $T(F)\nmid{q}^r-1$.

Следствие 21.11:
Пусть $P:=GF(q)$ поле характеристики $p$, многочлен $F(x)\in{P}[x]$ унитарен и его каноническое разложение имеет вид $$F(x)=x^lG_1(x)^{k_1}\cdots{G}_s(x)^{k_s},$$ $k:=\max\{k_1,\ldots,k_s\}$, тогда $T(F)=O(F)p^c$, где символ $O(f)$ вводится определением 19.3, а $c\in\mathbb{N}_0$ такое, что $p^{c-1}<k\leq{p}^c$.

Доказательство:

По теореме 21.12 и п. 3 следствия 19.2 $$T(F)=[T(G_1),\ldots,T(G_s)]p^c=[O(G_1),\ldots{O}(G_s)]p^c=O(F)p^c.$$

Алгоритм нахождения периода неприводимого многочлена над конечным полем.

Дано: неприводимый, унитарный многочлен $F(x)$ степени $m$ над полем $P=GF(q)$.
Найти: $T(F)$.

1. Раскладываем число $q^m-1$ на множители, выписываем все множители $t$ такие, что для любого $r\in\overline{1,m-1}$ $t\nmid{q}^r-1$.
2. Из всех множителей выписанных в пункте 1 находим минимальный $t$ удовлетворяющий условию $x^t\equiv1\pmod{F(x)}$, это и будет $T(F)$.

Пример 21.14:
Пусть $P:=GF(2)$, $F(x)=x^4+x+1$. $$2^4-1=15=5\cdot3\Rightarrow{T}(F)\in\{1,3,5,15\}.$$ $$\{2^r-1\mid{r}\in\overline{1,3}\}=\{1,3,7\}\Rightarrow{t}\in\{5,15\}.$$ $$x^4\equiv{x}+1\pod{F(x)}\Rightarrow{x}^5\equiv{x}^2+x\neq1\pod{F(x)}\Rightarrow{T}(F)=15.$$ Таким образом, $F(x)$ многочлен максимального периода.

Премер 21.15:
Дано: $P=GF(2)$, $F(x)=\sum_{k=0}^8f_kx^k=x^8+x^5+x^3+x^2+x$, $u\in{L}_P(F)$, $u(\overline{0,7})=(0,0,0,0,1,0,1,0)$.
Найти: $\Lambda(u)$, $T(u)$.

1. Находим минимальный многочлен $u$ по формуле $m_u(x)=\frac{F(x)}{(F(x),\Phi(x))}$.
   $$\Phi(x)=\sum_{k=0}^7\phi_kx^k=\sum_{k=0}^7(u(k)+f_{8-1}u(k-1)+\cdots+f_{8-k}u(0))x^{8-k-1}.$$ $\phi_7=u(0)=0,$
   $\phi_6=u(1)+f_7u(0)=0+0=0,$
   $\phi_5=u(2)+f_7u(1)+f_6u(0)=0+0+0=0,$
   $\phi_4=u(3)+f_7u(2)+f_6u(1)+f_5u(0)=0+0+0+0=0,$
   $\phi_3=u(4)+f_7u(3)+f_6u(2)+f_5u(1)+f_4u(0)=1+0+0+0+0=1,$
   $\phi_2=u(5)+f_7u(4)+f_6u(3)+f_5u(2)+f_4u(1)+f_3u(0)=0+0+0+0+0+0=0,$
   $\phi_1=u(6)+f_7u(5)+f_6u(4)+f_5u(3)+f_4u(2)+f_3u(1)+f_2u(0)=1+0+0+0+0+0+0=1,$
   $\phi_0=u(7)+f_7u(6)+f_6u(5)+f_4u(4)+f_4u(3)+f_3u(2)+f_2u(1)+f_1u(0)=0+0+0+1+0+0+0+0=1.$
   $$\Phi(x)=x^3+x+1.$$ Несложно видеть, что в данном случае $\Phi(x)|F(x)$, действительно
   

   $x^8$			$+x^5$		$+x^3$	$+x^2$	$+x$		$x^3+x+1$
   $x^8$		$+x^6$	$+x^5$						$x^5+x^3+x$
   		$x^6$			$+x^3$	$+x^2$	$+x$
   		$x^6$		$+x^4$	$+x^3$
   				$x^4$		$+x^2$	$+x$
   				$x^4$		$+x^2$	$+x$
   							$0$

   следовательно, $$m_u(x)=\frac{F(x)}{(F(x),\Phi(x))}=\frac{F(x)}{\Phi(x)}=x^5+x^3+x.$$
2. Разложим многочлен $m_u(x)$ на множители. $$m_u(x)=x(x^4+x^2+1)=x(x^2+x+1)^2.$$
3. $$\Lambda(u)=\Lambda(m_u(x))=1,$$ $$T(u)=T(m_u(x))=[T(x^2+x+1),1]p^c,$$ Так как $T(x^2+x+1)|2^2-1=3$ и $T(x^2+x+1)\nmid1$, то $T(x^2+x+1)=3$. Число $c\in\mathbb{N}_0$ находим из условия $2^{c-1}<2\leq2^c$, то есть $c=1$. Таким образом, $T(F)=3\cdot2^1=6$.

21.10 ЛРП максимального периода над конечным полем.

Определение 21.24:
Пусть $P=GF(q)$, $F(x)\in{P}[x]$ - унитарный, реверсивный многочлен степени $m$, тогда многочлен $F(x)$ называется многочленом максимального периода (или примитивным многочленом), если его период равен $q^m-1$.

Определение 21.25:
Ненулевая линейная рекуррентная последовательность $u$ порядка $m$ над полем $GF(q)$ называется последвательностью максимального периода, если ее период равен $q^m-1$.

Замечание 21.8:
Пусть $P=GF(q)$, $F(x)\in{P}[x]$ - унитарный многочлен степени $m$, $q^m>2$.

1. Если $F(x)$ реверсивный, то по теореме 21.11 $T(F)\leq{q}^m-1$. То есть среди всех унитарных, реверсивных многочленов степени $m$ многочлен максимального периода имеет максимальный период.
2. Если $u\in{L}_P(F)$, то по следствию 21.10 $\Lambda(u)+T(u)\leq{q}^m-1$, следовательно, среди всех ЛРП из $L_P(F)$ ЛРП максимального периода имеет максимальный период и если $u$ - ЛРП максимального периода, то $\Lambda(u)=0$.

Теорема 21.13:
Пусть $P=GF(q)$, $F(x)\in{P}[x]$ - реверсивный многочлен степени $m$, $q^m>2$; $u\in\alpha{P}^{\infty}$, $F(x)$ - минимальный многочлен $u$, тогда эквивалентны следующие утверждения.

1. Последовательность $u$ является последовательностью максимального периода.
2. Для любой ненулевой последовательности $v\in{L}_P(F)$ существует $k\in\mathbb{N}_0$ такое, что $v=x^ku$.
3. Многочлен $F(x)$ неприводим над $P$ и его корень в минимальном поле разложения является примитивным элементом.
4. Многочлен $F(x)$ являтеся многочленом максимального периода (ММП).

Доказательство:

Обозначим $t:=q^m-1$.
$1)\Rightarrow2)$ Если $t$ период ЛРП $u$, то все последовательности из множества $\{u,xu,\ldots,x^{t-1}u\}\subset{L}_P(F)$ попарноразличны. Так как $t=|L_P(F)\backslash\{0\}|$, то $$\{x^ku\mid{k}\in\overline{0,t-1}\}=L_P(F)\backslash\{0\}.$$ $2)\Rightarrow3)$ Докажем от противного, что многочлен $F(x)$ неприводим над $P$. Предположим, что существуют многочлены $A(x),B(x)\in{P}[x]$ такие, что $A(x)B(x)=F(x)$. Рассмотрим последовательность $v:=A(x)u\in{L}_P(F)$. По п. 1 утверждения 21.7 $$ m_v(x)=\frac{m_u(x)}{(m_u(x),A(x))}=\frac{F(x)}{(F(x),A(x))}=\frac{F(x)}{A(x)}=B(x). $$ С другой стороны, так как $v\in{L}_P(F)\backslash\{0\}$, то существует $k\in\mathbb{N}_0$ такое, что $v=x^ku$. Так как $F(x)$ реверсивен, то $(x^k,F(x))=1$, тогда $$m_v(x)=\frac{F(x)}{(x^k,F(x))}=F(x)\neq{B}(x).$$ Таким образом, получено противоречие с доказанным ранее равенством $m_u(x)=B(x)$, следовательно, $F(x)$ неприводим.
Пусть $\alpha\in{Q}:=GF(q^m)$ - корень многочлена $F(x)$, тогда по утверждению 21.19 $\Ord{\alpha}=T(F)$. Так как $F(x)=m_u(x)$, то по утверждению 21.18 $T(F)=T(u)$ и из условия 2 следует, что $T(u)=|L_P(F)\backslash\{0\}|=q^m-1$. Таким образом, $\Ord{\alpha}=q^m-1=|Q^*|$.
$3)\Rightarrow4)$ Если $\alpha$, корень многочлена $F(x)$ в МПР, то по утверждению 21.19 $T(F)=\Ord{\alpha}=q^m-1$.
$4)\Rightarrow1)$ По утверждению 21.18 $T(u)=T(m_u(x))=T(F)=q^m-1$.

Следствие 21.12:
Если $P=GF(q)$, $F(x)\in{P}[x]$ - многочлен максимального периода, то любая $u\in{L}_P(F)\backslash\{0\}$ является последовательностью максимального периода.

Доказательство:

Так как многочлен $F(x)$ - ММП, то он по определению реверсивный, тогда по п. 3 теоремы 21.13 многочлен $F(x)$ неприводим. Тогда по теореме 21.6, утверждению 21.18 $$m_u(x)=F(x)\Rightarrow{T}(u)=T(m_u(x))=T(F)=q^m-1.$$

Пусть $\vec{a}=(a_0,a_1,\ldots,a_{r-1})\in{P}^r$, $u\in\alpha{P}^{\infty}$. Обозначим как $N_u(\vec{a})$ число решений системы уравнений $$ \begin{cases} u(\overline{i,i+r-1})=\vec{a} \\ i\in\overline{0,T(u)-1}. \end{cases} $$ То есть $N_u(\vec{a})$ число появлений вектора $\vec{a}$ на цикле (т. е. на отрезке длины $T(u)$) ЛРП $u$.

Теорема 21.14:
Пусть $P\in{G}F(q)$, $u\in\alpha{P}^{\infty}$ - последовательность максимального периода порядка $m$, $r\in\overline{1,m}$, Тогда $$ N_u(\vec{a})= \begin{cases} q^{m-r},&\vec{a}\in{P}^r\backslash\{0\} \\ q^{m-r}-1,&\vec{a}=0 \end{cases} $$

Доказательство:

Обозначим $F(x):=m_u(x)$, $t:=q^m-1$, тогда ${\deg{F(x)}=m}$ и все последовательности из множества $\{x^ku\mid{k}\in\overline{0,t-1}\}\subset{L}_P(F)$ попарноразличны. Тогда попарно различны векторы из множества $$M:=\{u(\overline{i,m-i-1})\mid{i}\in\overline{0,t-1}\}.$$ Так как $|M|=t=q^m-1=|P^m|-1$ и $0\notin{M}$, то $M=P^m\backslash\{0\}$. Тогда для любого появления вектора $\vec{a}$ на периоде существует $k\in\overline{0,t-1}$ такое, что вектор $\vec{a}$ занимает первые $r$ позиций вектора $u(\overline{k,u+k-1})\in{M}$. Таким образом, искомое число $N_u(\vec{a})$ есть число векторов из $P^m\backslash\{0\}$ таких, что первые $r$ позиций в них занимает вектор $\vec{a}$. Очевидно, что это число описывается доказываемым равенством.

Следствие 21.13:
Пусть $P=GF(q)$, $u\in\alpha{P}^{\infty}$ - последовательность максимального периода, тогда для любого $a\in{P}^*$ $a$ встречается на цикле $u$ $q^m-1$ раз, нуль встречается на цикле $u$ $q^{m-1}-1$ раз.

Доказательство:

Следует из теореме 21.14 при $r=1$.

Чтобы построить многочлен максимального периода надо:

1. построить неприводимый многочлен с помощью критерия Батлера (теорема 19.6);
2. найти период этот многочлена с помощью алгоритма описанного в разделе 21.9;
3. если период максимальный - конец, иначе перейти к пункту 1.

Утверждение 21.20:
Пусть $P=GF(q)$, $F(x)\in{P}[x]$ - неприводимый реверсивный многочлен степени $m$, тогда $F(x)$ многочлен максимального периода тогда и только тогда, когда для любого собственного простого делителя $\pi$ числа $q^m-1$ выполняется соотношение $$x^{\frac{q^m-1}{\pi}}\not\equiv1\pmod{F(x)}.$$

Доказательство:

Так как многочлен $F(x)$ неприводим, то по утверждению 21.9 $T(F)|q^m-1$. Тогда многочлен $F(x)$ не ММП тогда и только тогда, когда существует собственный простой делитель $\pi$ числа $q^m-1$ такой, что $$x^{\frac{q^m-1}{\pi}}\equiv1\pmod{F(x)}.$$ Так как для любых высказываний $A$ и $B$ $(\overline{A}\Leftrightarrow\overline{B})\sim(A\Leftrightarrow{B})$, то утверждение доказано.

Следствие 21.14:
Если $2^m-1$ - простое число, то любой неприводимый реверсивный многочлен степени $m$ над $GF(2)$ является многочленом максимального периода.

Доказательство:

Если $2^m-1$ простое число, то оно не имеет собственных простых делителей, поэтому результат следует из утверждения 21.20.

Премер 21.16:
Положим $P:=GF(3)$ и проверим является ли многочлен $F(x)=x^3+2x+1$ ММП над $P$.

1. Так как $F(0)=F(1)=F(2)=1\neq0$, то многочлен $F(x)$ степени 3 не имеет корней, следовательно, он неприводим.
2. Так как $T(F)|3^3-1=26$, то $T(F)\in\{2,13,26\}$. Так как ${T(F)\nmid3^1-1=2}$ и $T(F)\nmid3^2-1=8$, то $T(F)\in\{13,26\}$.
   Проверим выполняется ли сравнение $x^{13}\equiv1\pod{F(x)}$. $$ x^3+2x+1\equiv0\pod{F(x)}\Rightarrow{x}^3\equiv{x}+2\pod{F(x)}\Rightarrow {x}^4\equiv{x}^2+2x\pod{F(x)}\Rightarrow{x}^{13}\equiv(x^4)^3x=(x^2+2x)^3x=x^7+2x^4\pod{F(x)}. $$ Поделив $x^7+2x^4$ на $F(x)$ получим
   

   $x^7$			$+2x^4$					$x^3+2x+1$
   $x^7$		$+2x^5$	$+x^4$					$x^4+x^2+x+1$
   		$x^5$	$+x^4$
   		$x^5$		$+2x^3$	$+x^2$
   			$x^4$	$+x^3$	$+2x^2$
   			$x^4$		$+2x^2$	$+x$
   				$x^3$		$+2x$
   				$x^3$		$+2x$	$+1$
   							$2$

   
   то есть $x^{13}\equiv2\pod{F(x)}$, следовательно, $x^{13}\not\equiv1\pod{F(x)}$. Таким образом, многочлен $F(x)$ - ММП.

Пример 21.17:
Числа $2^2-1=3$, $2^3-1=7$, $2^5-1=31$ являются простыми, следовательно, любые неприводимые над $GF(2)$ многочлены степеней $2,3,5$, например, $x^2+x+1$, $x^3+x+1$, $x^3+x^2+1$, $x^5+x+1$ являются ММП.
Числа вида $2^m-1$ называются числами Мерсенна. Если число Мерсена простое, то $m$ простое, действительно, если $m=ab$, то $$(q^{ab}-1)=(q^a-1)(q^{a(b-1)}+q^{a(b-2)}+\cdots+q^a+1).$$ Простыми, например, являются числа $2^m-1$ при $m$ равном $2$, $3$, $5$, $7$, $13$, $17$, $19$, $31$, $127$. По состоянию на август 2018 года не известно является ли множество простых чисел Мерсенна конечным, наибольшим (пятидесятым) из найденных является число $2^{77232917}-1$.

previous contents next