Algorithm for constructing the system of representatives of maximal length cycles of polynomial substitution over the ga.pdf Рассмотрим кольцо Галуа R = GR(qn,pn) мощности qn и характеристики pn, где q = pm. Пусть /(x) E R[x] - биективный полином над кольцом Галуа R. Граф преобразования, задаваемого полиномом /(x) над кольцом R, обозначим через G/,r. Напомним, что цикловая структура графа - это таблица [l^1,... , ], указывающая, что граф состоит из k1 циклов длины l1, ... , kt циклов длины lt. В работе [1] показано, что граф Gf,R не может содержать цикл, длина которого больше q(q - 1)pn-2. В данной работе рассматривается класс полиномов над кольцом Галуа R, граф которых содержит цикл максимальной длины q(q - 1)pn-2. Назовём такие полиномы полиномами с максимальной длиной цикла (МДЦ-полиномами). Пусть f (x) Е R[x] -МДЦ-полином. В работе решается задача построения множества Wf,R С R - системы представителей всех циклов максимальной длины (q-1)qpn-2 графа Gf,R. Мощность множества Wf,R равна (q/p)n-2, так как в графе Gf,R содержится (q/p)n-2 циклов длины (q - 1)qpn-2 [2]. Введём необходимые обозначения. Положим J = pR и Rk = R/Jk, k Е {1,... , n}. Рассмотрим эпиморфизмы (i : R ^ Ri для i Е {1,...,n}, которые естественным образом продолжаются до эпиморфизмов колец многочленов (i : R[x] ^ Ri[x]. Положим fi(x) = (Pi(f (x)). Строить набор Wf,R будем итеративно, последовательно находя элементы в цепочке множеств Wfl ,R1 ,Wf2,R2 ,...,Wfn,Rn, и тогда Wf,R = Wfn,Rn Множество Wf1,R1 состоит из одного элемента, так как граф Gf1R1 состоит из единственного цикла длины q. Поэтому в качестве множества Wf1 ,r1 подойдёт любое одноэлементное множество {a}, a Е R1. Множество Wf2,R2 также состоит из одного элемента, поскольку граф Gf2,R2 состоит из двух циклов длины q(q - 1) и q. Следовательно, в качестве элемента множества Wf2,R2 подойдёт любой элемент на цикле длины q(q - 1) графа Gf2,R2. Теперь покажем, как по известному множеству Wfk,Rk построить множество Wffc+1 ,Rk+1, k ^ 2. Рассмотрим эпиморфизмы (i : Ri+1 ^ Ri для i Е {1,..., n - 1}. Для каждого a Е Wfk,Rk обозначим через Ca цикл графа Gfk,Rk, на котором лежит элемент a. Так как прообраз (-1(Ca) состоит из q/p циклов максимальной длины q(q - 1)pk-1 графа Gfk+1,Rk+1, то для построения множества Wfk+1,Rk+1 достаточно для каждого элемента a Е Wfk ,Rk найти множество элементов {a1, a2,..., aq}, лежащих на этих циклах, причём разные элементы должны лежать на разных циклах. Пусть элемент a Е Wfk ,Rk. Установим связь между элементами кольца Rk+1, которые лежат на одном цикле максимальной длины и образ которых под действием эпиморфизма (k совпадает с a. Утверждение 1. Пусть элемент a Е Wfk,Rk является представителем цикла C максимальной длины графа Gfk,Rk, тогда на любом цикле C максимальной длины графа Gfk+1,Rk+1, таком, что (i(C ) = C, лежат ровно p элементов, образ которых под действием эпиморфизма (i совпадает с a. Теорема 1. Пусть a1 = a + pkab ..., ap = a + pkap - элементы на некотором цикле максимальной длины q(q - 1)pk-i графа G/fc+1,Rfc+1, образ которых под действием эпиморфизма ^k совпадает с a Е W/fc,Rfc. Тогда выполняется соотношение ai+1 = ai + r, i = 1, 2,... ,p, где r - некоторый элемент поля Rl . Следствие 1. Пусть a Е W/fc,Rfc. Два элемента a + pka' и a + pka" кольца Rk+1 лежат на одном и том же цикле максимальной длины графа G/fc+1,Rfc+1 в том и только в том случае, если элементы a , a Е Rl лежат на одном цикле графа Gx+r,R1 полиномиального преобразования x + r, где элемент r Е Rl находится из сравнения F(a) = a + pkr (mod Jk+1). Граф Gx+r,R1 состоит из q/p циклов длины p. Элементы каждого цикла образуют смежный класс аддитивной группы поля Rl = GF(q) по подгруппе (r). Это означает, что для нахождения q/p элементов поля GF(q), которые лежат на разных циклах графа Gx+r,GF(q), достаточно найти представителей смежных классов поля GF(q) по подгруппе (r). Аддитивная группа поля (GF(q), +) изоморфна группе (Z^ +). Если на группе (Z^m, +) ввести внешнюю операцию умножения на элементы поля Zp, то получим векторное пространство размерности m. Дополним до базиса пространства элемент r, получим базис r, r2,..., rm и рассмотрим представление пространства в виде прямой суммы подпространств Zm = (r) + (r2) + ••• + (rm). Представителями смежных классов группы (GF(q), +) по подгруппе ((r), +) являются все элементы множества {(r2) + ••• + (rm)}. Изложим алгоритм построения системы представителей циклов максималь ной длины графа Gf,R. В качестве W/1,r1 можно взять любое одноэлементное множество {a}, a Е Rl, а в качестве W/2,r2 -одноэлементное множества {a }, где a -элемент на цикле длины q(q - 1) графа G/2,r2. Далее покажем, как по имеющемуся элементу a Е W/fcпостроить множество из q/p элементов Аа С W/fc+1,Rfc+1, k ^ 2. При этом, по построению, для различных a1,a2 Е W/fc,Rfc множества Аа1 и Аа2 не пересекаются. Поскольку p |W/k,Rfc | = | W/fc+1,Rfc+1|, p то U Аа = W/fc+1,Rfc+1 • aeWfk,Rk Алгоритм 1. Построение множества Аа Вход: f (x) Е R[x], a Е W/fc,Rfc Выход: множество Аа С W/fc+1,Rfc+1 1: Находим элемент r Е Ri, такой, что f[q(q-1)pk 2l(a) = a + pkr (mod Jk+1). 2: Дополняем до базиса пространства Zm элемент r, получим базис r, r2,... , rm 3: Аа := {cir2 + ... + Cmrm : С Е {0,... ,p - 1},i = 1,... , m}. За элементарную операцию возьмём операцию умножения в кольце Галуа R. Сложность построения множества Wfn, Rn составляет O(lqn-1) элементарных операций при n, стремящемся к бесконечности, где l - степень многочлена f (x) на входе алгоритма.

Скачать электронную версию публикации