Свойства полиномиальных генераторов с выходной последовательностью наибольшего периода над кольцом Галуа | Прикладная дискретная математика. 2015. № 1 (27).

Пусть R = GR(q ⁿ,p ⁿ) - кольцо Галуа мощности q ⁿ и характеристики p ⁿ, где q = p ^m, и Gf,R - граф биективного преобразования кольца R, задаваемого полиномом f (x) G R[x]. Если n > 1 или q = p, то граф Gf,R не может быть циклом. Максимальная длина цикла в таком графе не превосходит q(q-1)p ^n-2. Полиномы, для которых граф Gf,R содержит цикл указанной длины, назовём полиномами с максимальной длиной цикла. Для таких полиномов предложен алгоритм проверки, лежит ли заданный элемент кольца на каком-либо цикле длины q(q - 1)p ^n-2 графа Gf,R. Алгоритм требует выполнения порядка dq операций умножения и порядка dq операций сложения в кольце R, d = degf(x), d < |R|. Предложен также алгоритм построения системы представителей различных циклов графа Gf,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 = [log _q/ _p M] + 1.