Свойства полиномиальных генераторов с выходной последовательностью наибольшего периода над кольцом Галуа

Пусть $R=\mathrm{GR}(q^n,p^n)$ – кольцо Галуа мощности $q^n$ и характеристики $p^n$, где $q=p^m$, и $G_{f,R}$ – граф биективного преобразования кольца $R$, задаваемого полиномом $f(x)\in R[x]$. Если $n>1$ или $q\not=p$, то граф $G_{f,R}$ не может быть циклом. Максимальная длина цикла в таком графе не превосходит $q(q-1)p^{n-2}$. Полиномы, для которых граф $G_{f,R}$ содержит цикл указанной длины, назовём полиномами с максимальной длиной цикла. Для таких полиномов предложен алгоритм проверки, лежит ли заданный элемент кольца на каком-либо цикле длины $q(q-1)p^{n-2}$ графа $G_{f,R}$. Алгоритм требует выполнения порядка $dq$ операций умножения и порядка $dq$ операций сложения в кольце $R$, $d=\deg{f(x)}$, $d<|R|$. Предложен также алгоритм построения системы представителей различных циклов графа $G_{f,R}$, имеющих длину $q(q-1)p^{n-2}$. Алгоритм построения представителей всех циклов длины $q(q-1)p^{n-2}$ требует выполнения порядка $d(q-1)q^{n-1}$ операций умножения и порядка $d(q-1)q^{n-1}$ операций сложения в кольце $R$. Алгоритм построения представителей $M$ различных циклов длины $q(q-1)p^{n-2}$ требует выполнения порядка $d(q-1)q^{k-1}$ операций умножения и порядка $d(q-1)q^{k-1}$ операций сложения в кольце $R$, где $k=\lceil\log_{q/p}M\rceil+1$.