ЛИНЕ́ЙНАЯ РЕКУРРЕ́НТНАЯ ПОСЛЕ́ДОВАТЕЛЬНОСТЬ

ЛИНЕ́ЙНАЯ РЕКУРРЕ́НТНАЯ ПОСЛЕ́ДО­ВАТЕЛЬНОСТЬ по­ряд­ка $m⩾1$ над ком­му­та­тив­ным коль­цом $R$ с еди­ни­цей $e$, по­сле­до­ва­тель­ность $u=(u(0), u(1),...)$ эле­мен­тов коль­ца $R$ та­кая, что $$u(i+m)=c_{m-1}U(i+m-1)+...+c_{1}u(i+1)+c_{0}u(i),\: i=0,\: 1,\: 2,...,\tag1$$

  для не­ко­то­рых фик­си­ро­ван­ных $c_0,...,c_{m-1}∈R$. Со­от­но­ше­ние (1) на­зы­ва­ет­ся за­ко­ном ре­кур­сии, мно­го­член $F(x)=x^m−c_{m−1}x^{m−1}−...−c_0∈R[x]$ – ха­рак­те­ри­стич. мно­го­чле­ном, век­тор $(u(0),u(1),...,u(m-1))$ – на­чаль­ным век­то­ром Л. р. п. $u$. Од­на и та же Л. р. п. u с дан­ным на­чаль­ным век­то­ром мо­жет за­да­вать­ся разл. со­от­но­ше­ния­ми ви­да (1). Ха­рак­те­ри­стич. мно­го­член Л. р. п. $u$ наи­мень­шей сте­пе­ни (оп­ре­де­ляе­мый, во­об­ще го­во­ря, не­од­но­знач­но) на­зы­ва­ет­ся её ми­ни­маль­ным мно­го­чле­ном, а его сте­пень – ран­гом или ли­ней­ной слож­но­стью Л. р. п. $u$ .

Ши­ро­кое при­ме­не­ние Л. р. п. в разл. раз­де­лах дис­крет­ной ма­те­ма­ти­ки и её при­ло­же­ний обу­слов­ле­но в зна­чит. сте­пе­ни тем, что Л. р. п. (1) мо­жет быть по­лу­че­на как вы­ход­ная по­сле­до­ва­тель­ность про­сто­го ав­то­ма­та, на­зы­вае­мо­го ли­ней­ным ре­ги­ст­ром сдви­га.

При­ме­ра­ми Л. р. п. яв­ля­ют­ся сле­дую­щие по­сле­до­ва­тель­но­сти.

Гео­мет­рич. про­грес­сия $u(i)=cq^i$, $i=0,1,2,...$, где $c$, $q∈R\setminus \left \{ 0 \right \}$, – Л. р. п. ран­га 1 с ми­ни­маль­ным мно­го­чле­ном $f(x)=x-q$.

Ариф­ме­тич. про­грес­сия $u(i)=ai+b, i=0, 1, 2, ...$, где $a∈R\setminus \left \{ 0 \right \}$, $b∈R$, – Л. р. п. ран­га 2 с ми­ни­маль­ным мно­го­чле­ном $(x-e)^2$.

Кон­гру­энт­ная по­сле­до­ва­тель­ность $u(i+1)=qu(i)+a$, $i=0,1,2,...$, где $q,a,u(0)∈R\setminus \left \{ 0 \right \}$ , – Л. р. п. ран­га 2 с ми­ни­маль­ным мно­го­чле­ном $(x-q)(x-e)$. Та­кие по­сле­до­ва­тель­но­сти ис­поль­зу­ют­ся для ге­не­ри­ро­ва­ния псев­до­слу­чай­ных чи­сел в ЭВМ.

По­сле­до­ва­тель­ность Фи­бо­нач­чи $f(i+2)=f(i+1)+f(i)$, $i=0,1,2,...$, $f(0)=0$, $f(1)=1$, – Л. р. п. над коль­цом це­лых чи­сел с ми­ни­маль­ным мно­го­чле­ном $x^2-x-1$. Эта по­сле­до­ва­тель­ность рас­смат­ри­ва­лась Ле­о­нар­до Пи­зан­ским (Фи­бо­нач­чи).

Пе­рио­ди­че­ские по­сле­до­ва­тель­но­сти. По­сле­до­ва­тель­ность $u$ над коль­цом $R$ на­зы­ва­ет­ся пе­рио­ди­че­ской, ес­ли су­ще­ст­ву­ют па­ра­мет­ры $d \in \textbf{N}_{0}=\textbf{N}\cup \left \{ 0 \right \}, t \in \textbf{N}$ та­кие, что $u(i+t)=u(i)$ для всех $i \geqslant d$.  Та­кая по­сле­до­ва­тель­ность есть Л. р. п. с ха­рак­те­ри­стич. мно­го­чле­ном $F(x)=x^{d}(x^{t}-e)$. Ес­ли $R$ – ко­неч­ное коль­цо, то лю­бая Л. р. п. над $R$ яв­ля­ет­ся пе­рио­дич. по­сле­до­ва­тель­но­стью. На мно­же­ст­ве $R^{\left \langle 1 \right \rangle}$всех по­сле­до­ва­тель­но­стей над $R$ ес­те­ст­вен­ным об­ра­зом за­да­ют­ся опе­ра­ции сло­же­ния и ум­но­же­ния на кон­стан­ты из $R$. Опе­ра­ция ум­но­же­ния по­сле­до­ватель­но­сти $u \in R^{\left \langle 1 \right \rangle}$на мно­го­член $H(x)=\sum _{s\geqslant 0} h_{s}x^{s}\in R\left [ x \right ]$ по правилу $(x)u=\upsilon \in R^{\left \langle 1 \right \rangle}$, где $\upsilon (i)=\sum _{s\geqslant 0}h_{s}u(i+s),\: i\geqslant 0,$ по­зво­ля­ет сфор­му­ли­ро­вать ус­ло­вие (1) в ви­де ра­вен­ст­ва $F(x)u=0$. Ус­ло­вие пе­рио­дич­но­сти по­сле­до­ва­тель­но­сти $u$ озна­ча­ет су­ще­ст­во­ва­ние па­ра­мет­ров $d \in \textbf{N}_{0}, t \in \textbf{N}$ та­ких, что$$x^{d}(x^{t}-e)u=0.\tag2$$

Для пе­рио­дич. по­сле­до­ва­тель­но­сти $u$ су­ще­ст­ву­ют па­ра­мет­ры $D(u)∈N_0$, $T(u)∈N$ (на­зы­вае­мые со­от­вет­ст­вен­но де­фек­том и пе­рио­дом $u$) та­кие, что для лю­бых $d∈N_0$, $t∈N$ ус­ло­вие (2) рав­но­силь­но па­ре ус­ло­вий: $d⩾D(u)$, $T(u)$ де­лит $t$.

Осн. про­бле­ма­ми тео­рии Л. р. п. счи­та­ют­ся: за­да­ча вы­чис­ле­ния об­ще­го чле­на $u(i)$ Л. р. п. $u$ без ре­кур­рент­но­го вы­чис­ле­ния пре­ды­ду­щих зна­ков; за­да­ча оцен­ки ран­га Л. р. п., за­дан­ной к.-л. спо­со­бом; оцен­ка пе­рио­да Л. р. п. над ко­неч­ным коль­цом; оцен­ка час­тот по­явле­ния эле­мен­тов коль­ца на за­дан­ном от­рез­ке Л. р. п.; за­да­ча вос­ста­нов­ле­ния на­чаль­но­го век­то­ра Л. р. п. и за­ко­на рекур­сии по час­тич­ной ин­фор­ма­ции о Л. р. п.; изу­че­ние по­стро­ен­ных из от­рез­ков Л. р. п. ко­дов, ис­прав­ляю­щих ошиб­ки.

Мно­же­ст­во всех Л. р. п. над $R$ с ха­рак­те­ри­стич. мно­го­чле­ном $F(x)$ обо­зна­ча­ет­ся $L_R(F)$. Фор­му­ла для вы­чис­ле­ния зна­ка $u(i)$ Л. р. п. $u∈L_R(F)$ без ре­кур­рент­но­го вы­чис­ле­ния пре­ды­ду­щих зна­ков стро­ит­ся с по­мо­щью т. н. би­но­ми­аль­но­го пред­став­ле­ния Л. р. п. $u$. Ес­ли мно­го­член $F(x)$ рас­кла­ды­ва­ет­ся на ли­ней­ные мно­жи­те­ли над коль­цом $R$, т. е. , при­чём раз­но­сти $α_i-α_j$ – об­ра­ти­мые эле­мен­ты в $R$, то $L_R(F)$ есть мно­же­ст­во всех по­сле­до­ва­тель­но­стей ви­да $$u(i)=\sum_{s=1}^{t}(c_{s0}\alpha _{s}^{i}+ c_{s1}C_{i}^{1}\alpha _{s}^{i-1}+\: ...+c_{sk_{s}}C_{i}^{k_{s}}\alpha _{s}^{i-k_{s}}),$$ где $c_{sj}∈R$, а  – би­но­ми­аль­ные ко­эф­фи­ци­ен­ты. Напр., об­щий член по­сле­до­ва­тель­но­сти Фи­бо­нач­чи над по­лем ра­цио­нальных чи­сел име­ет вид $f(i)=(\alpha _{1}^{i}-\alpha _{2}^{i})/\sqrt{5}$, где $\alpha _{1}=(\sqrt{5}+1)/2, \alpha _{2}=(\sqrt{5}-1)/2$.

В свя­зи с при­ло­же­ния­ми в тео­рии ко­дов и крип­то­гра­фии наи­бо­лее пол­но раз­ра­бо­та­на тео­рия Л. р. п. над ко­неч­ны­ми по­ля­ми. Для Л. р. п. $u$ над по­лем $P$ су­ще­ст­ву­ет един­ст­вен­ный ми­ни­маль­ный мно­го­член $M_u(x)$. Пусть $P=GF(q)$ – по­ле из $q$ эле­мен­тов. Пе­ри­од $T(u)$ и де­фект $D(u)$ Л. р. п. $u$ рав­ны со­от­вет­ст­вен­но наи­мень­шим $t∈N$ и $d∈N_0$ та­ким, что $M_u(x)$ де­лит $x^d(x^t-e)$.

Ес­ли $u$ – Л. р. п. ран­га $m$ над $P=GF(q)$, то $T(u)⩽q^m-1$. В слу­чае ес­ли $T(u)=q^m-1$, Л. р. п. $u$ на­зы­ва­ют Л. р. п. мак­си­маль­но­го пе­рио­да $τ=q^m-1$ ран­га $m$ над по­лем $P$. На от­рез­ке $(u(0),u(1),...,u(τ-1))$ ка­ж­дый не­ну­ле­вой эле­мент по­ля $P$ встре­ча­ет­ся $q^{m–1}$ раз, а ну­ле­вой эле­мент – $q^{m-1}$– 1 раз, и мно­же­ст­во от­рез­ков $(u(i),...,u(i+m- 1))$, $i=1,...,τ-1$, сов­па­да­ет с мно­же­ст­вом всех не­ну­ле­вых строк дли­ны $m$ над по­лем $P$. Та­ким об­ра­зом, Л. р. п. мак­си­маль­но­го пе­рио­да по ря­ду свойств хо­ро­шо ими­ти­ру­ет слу­чай­ную рав­но­ве­ро­ят­ную по­сле­до­ва­тель­ность. Это яв­ля­ет­ся ос­но­ва­ни­ем для ши­ро­ко­го ис­поль­зо­ва­ния та­ких Л. р. п. в крип­то­гра­фии.

Мно­же­ст­во $K$ всех от­рез­ков $(u(0),...,u(τ- 1))$, со­от­вет­ст­вую­щих разл. Л. р. п. $u∈L_P(G)$ с мак­си­маль­ным пе­рио­дом $τ$ и ну­ле­вым де­фек­том, есть ли­ней­ный цик­лич. код дли­ны $n=τ$ раз­мер­но­сти $m$ с ко­до­вым рас­стоя­ни­ем $d=q^m-q^{m-1}$. Этот код яв­ля­ет­ся наи­луч­шим в том смыс­ле, что для не­го дос­ти­га­ет­ся т. н. гра­ни­ца Плот­ки­на, со­глас­но ко­то­рой $d⩽(∣\!P\!∣-1)\!∣\!K\!∣\!n/(P(∣\!K\!∣-1))$.

Ос­но­вы тео­рии Л. р. п. бы­ли за­ло­же­ны в 18–19 вв. в ра­бо­тах А. де Му­ав­ра, Д. Бер­нул­ли, Л. Эй­ле­ра и Ж. Ла­гран­жа. В кон. 19 – нач. 20 вв. тео­рия Л. р. п. раз­ви­ва­лась в тру­дах франц. ма­те­ма­ти­ка Э. Лю­ка, П. Л. Че­бы­ше­ва, А. А. Мар­ко­ва. Ис­сле­до­ва­ния свойств Л. р. п. над коль­ца­ми вы­че­тов и ко­неч­ны­ми по­ля­ми бы­ли на­ча­ты в 1920–30-х гг., даль­ней­шее раз­ви­тие эта тео­рия по­лу­чи­ла в ра­бо­тах амер. учё­ных С. Го­лом­ба, Г. Ни­дер­рай­те­ра, Н. Цир­ле­ра и рос. учё­ных М. М. Глу­хо­ва, А. С. Кузь­ми­на, А. В. Ми­ха­лё­ва, А. А. Не­чае­ва, В. И. Не­чае­ва, В. М. Си­дель­ни­ко­ва.