для уравнения + z + = О при = 6 б GF(2*) найдено множество корней (7, 8, 10, и] . Следовательно, уравнение (5.59) с параметрами S = l,R - 6,Q~Q имеет множество кортей о, 7, 8, 10, и) .

Подставляя в формулу перехода из табл. 5.7 л: = С/В + 1/w = X + + 1/(й + г) = 11 + 1/(12 + г) вместо t указанные пять значений, вычисляем множество корней заданного уравнения: ( 3, 12, 7, 10, 15} , совпадающее (с точностью до порядка элементов) с исходным набором.

Наконец, составим по множеству корней (5, 9, 16, 24, ЗО} G GF (2) уравнение (5.54), в котором коэффициенты принимают следующие значения: Л = 3; 5 = 18; С = 21; Z) = 15; £" = 18. Как ив предыдущем примере, рассчитаем параметры: X = 4; а = 2; (5 = 14; 7= 21; л =13; г, = 5 = 17; с = 20; = 31; 7? = 23; Q = 30. Таким образом, получим полином

+5? +7?r + 2 = f5 + 17? +23?+ 30, GF(2) (5.64)

и каноническое уравнение (5.60), в котором е = Qb~l- =24, в = = =12.

Из табл. 5.8 для = 12, е = 24 находим: z = 2; z " = 7; z" = 21; z"" = 29; z"" = 31. По формулам перехода t - zS - 21 z hx=X + У ll(a + f) = 4 + 1/(13 + ?) для уравнений (5.59) и (5.54) с вычисленными вьппе коэффициентами находим множества корней соответственно (28,2,16,24,26} и (16,24,5,30,9}.

Факторизация полиномов из левых частей уравнений (556) и (559). В работе [54] показано, что возможно следующее разбиение полинома из уравнения (5.56) на два сомножителя:

"tGy л-Ну --ly-yj = (у +ау +]3; + 7) +а; + 5),

где G = a+ 3 + 5; Я=а5+а]3 + 7; /=/35+а7; J =уд.

Однако в зависимости от того, будет ли G = О или Я = О, приходится прибегать к различным вычислительным процедурам. Поэтому мы осуществим факторизацию полинома из уравнения (5.59):

г* +5г +Л? + е= (г +йг +Ьг+ с)(г -ay-yd), (5.65)

5=й + йг? + с; R=bd-\-ac\ Q-cd; л +г?+с? = 0.

(5.66)

К сожалению, в общем виде не удается полностью разрешить систему (5.66) нелинейных уравнений относительно неизвестных. Так, например, исключая переменные Ь, с, d, вновь приходим к уравнению пятой степени (относительно а),

В работе [54] предложен гибридный метод, основанный на сочетании факторизации и частичного перебора. Суть его состоит б следующем.

1. Вводят дополнительное соотношение d = Dqu, исходя из условия Tr(Z)o) = О разрешимости квадратных уравнений + at + (i = 0 hz + 2 + Z)o = О, rjieD-d/a\ г =flz - см. § 5.1.

2. Исключая неизвестные b, с, d из системы (5.66), составляют квадратное уравнение относительно переменных а и Dq- Конкретно данный этап распадается на несколько шагов:

а) неизвестные b и с выражают через переменные а и Z)o> именно:

c = Q/dQI(Doa); Ь = G + + с? = (7 + (1 + Do). где G = 0;

б) подставляя значения Ь, с, d в соотношения для S иЯ т системы (5.66), составляют уравнения пятой степени:

й +г?й2 +2/!>о = 0;

а (1 +£>о) + (R/Do)a + Q/D = 0;

в) исключая из последних уравнений а, ползают типовое квадратное уравнение + Ма + 7V = О, которое сводят к канонической форме

й? +Й1 = О,

(5,67)

3. Задаются допустимыми значениями Dq, которые, например, выбирают из таблиц для корней квадратных уравнений, и рассчитывают параметр Di. Если в той же самой таблице нет ни одного из полученных значений Di, т.е. Tr(Di) = 1, то делают вьюод, сформулированный в п. 5. В противном случае выбирают из этой таблицы одну из величин, соответствуюищх Di, в качестве корня й[ уравнения (5.67), а также пару величин z\z", соответствующих io •

4. Рассчитывают корни й = Ма[, t = az *, t" = az параметры b, с, d и одним из методов, изложенных в § 5.2, находят разные корни ti, ?2, ?з кубического уравнения f + at + + с = 0. Все пять нулей полиномов второй и третьей степеней в выражении (5.65) принимают в качестве корней факторизуемого полинома (5.65). Если же суммарное количество нулей в используемом поле GF(2) менее пяти, то обращаются к п. 5.

5. Исходное уравнение пятой степени не имеет пяти разных корней в заданном поле GF (2").

Пример 5.15. Факторизуем полином (5,64). Составим соотношение

Обратившись к табл. П.З GF(2), выбираем наугад Do = 5. Тогда получим Di = 25 - значение, отсутствующее в указанной таблице. Следовательно, выбор Dq = 5 был неудачным. Вообще, можно убедиться, что множество значений Dq Е {о, 5, 8, 15, 17, 28, ЗО} недопустимо.

Остальные значения Dq е [2, 3, 9, 16, 20, 24, 26, 29, 31} в табл. П.З -допустимы.

Примем Do = 2 1А найдем значение Z>i = 31, которому в табл. П.З соответствуют величины 12 и 20. Зафиксируем первую из них в качестве корня al = 12 уравнения (5.67). Тогда а = Mai - 30, где Л/=

= Л/[5£)о(1 +/)о)] = 19, а также Ь =а(1 + Dq) = l5,d = Doa =29, c = Q/d = 2.

Таким образом, осуществлена факторизация + 17? +23?+ 30= (? +30? + 15? +2)(? +30? + 29), GF(2).

Итак, при решении уравнений пятой степени, так же как и четвертой, можно ограничиться хранением лишь таблиц для корней квадратных и кубических уравнений, что существенно при использовании полей высоких размерностей.

В § 5.1 ... 5.4 излагались методы решения степенных уравнений невысокого порядка, причем каждый метод имел свою специфику в зависимости от порядка уравнения. В следующем параграфе рассматриваются универсальные методы исследования корней полиномов

над полями Галуа, т.е. такие методы, которые не зависят от порядка полино ма.

>. УНИВЕРСАЛЬНЫЕ МЕТОДЫ ВЫЧИСЛЕНИЯ КОРНЕЙ ФАКТОРИЗАЦИИ ПОЛИНОМОВ НАД ПОЛЯМИ ГАЛУА

Выявление кратных корней с Помощью формальной производной и алгоритма Евклида. В теории помехоустойчивого кодирования "рабочими" являются только такие полиномы (полиномы локаторов), которые не имеют кратных корней, так как несколько ошибок на одной и той же позиции воспринимаются как одна. Если же полином

локаторов имеет кратные корни, то это означает, что количество действительно происшедших ошибок превьппает число, допустимое для данного используемого кода.

Понятие кратного корня многочлена над любым полем (как бесконечным, так и конечным) тесно связано с понятием формальной производной.

Подчеркнем различие и аналогию между производной по переменной Z в поле вещественных чисел и формальной производной в конечном

поле.

Пусть, например, над вещественным полем задан полином

/(2) = 2 =

( = о