Глава 2

Арифметические операции по модулю неприводимого двоичного многочлена

2.1. Более подробно об алгоритме Евклида

В предыдущем разделе было показано, что для декодирования двоичных БЧХ-кодов необходимо уметь выполнять арифметические операции в поле классов вычетов по модулю неприводимого двоичного многочлена М {х). Ключевую роль в решении этой задачи и с теоретической, и прикладной точек зрения играет алгоритм Евклида.

С теоретической точки зрения алгоритм Евклида позволяет доказать однозначность (с точностью до скалярных множителей) \ разложения многочлена над любым полем в произведение неприводимых множителей. Отсюда вытекает, что многочлен степени d ни в одном поле не может иметь более чем d корней. Последний результат важен в применении к многочлену локаторов ошибок а (г). Есле бы этот многочлен имел больше корней, чем его степень, то описанн пая в примере в разд. 1.4 процедура декодирования была бы neco-i стоятельной, поскольку нарушилось бы соответствие между корнями а (z) и локаторами ошибок.

С прикладной точки зрения алгоритм Евклида важен потому, чтс его модификация - метод непрерывных дробей - приводит к одно из наиболее эффективных реализаций деления в конечных полязс Этот сравнительно новый метод будет детально разобран в это1 и следующем разделах.

Алгоритм Евклида основан на том факте, что любой делителЦ элементов R ж г должен делить также их сумму и разность. Боле того, так как любой делитель г делит также и любое его кратно скажем аг, то любой общий делитель R и. г должен делить так> R ± аг. Наоборот, любой делитель г и. R + аг делит {R ± аг)

аг - R. Следовательно, если через (Л, г) обозначить наибольшв общий делитель элементов Лиг (ниже называемый п. о. д.), то (Л, г) == (г, Д ± аг). Значит, отправляясь от начальной пары элементов и г, можно найти новую пару элементов с тем же н. о. д. Если выбра! соответствующим образом множитель а, то задача отыскания н.о. новой пары элементов может быть упрощена по сравнению с исходно задачей. Заметим, что предыдущая аргументация относится в равн мере как к целым числам, так и к многочленам с коэффициента из любого данного поля. В первом случае под н. о. д. подразумевает наибольший по абсолютной величине общий делитель; во втор4

2,1. Более подробно об алгорит.че Евклида 33

случае - общий делитель наибольшей степени. Единственность н. о. д. для многочленов (с точностью до постоянного множителя) будет установлена позже как следствие алгоритма деления. В обоих случаях н. о. д. обладает следующими важнейшими свойствами: (i?, г) = (г, R), (R, г) = (г, Л ± аг), (г, 0) = г. Если R, г - натуральные числа я г <С R, то обычно полагают а = [R/r] ). Тогда О R - аг <Z г. Таким образом, если уже получены числа r„ i и г„ , где r„ j "п-2> можно так определить числа а„ и г„, что

Здесь

Исходя из начальной пары чисел R - rz и r = r i, получаем, что

0<Г 1<Г 2,

г 2-=аоГ 1 + Го, 0<Го<г 1,

r i = airo + rj, 0<rt<ro,

Г(1 = а2г1+Г2, 0<Г2<Г1,

Гп-2=апГп-1Ч-о, 0 = r„<r„ i.

Так как {г;} - убывающая последовательность неотрицательных чисел, то существует такое натуральное п, что г„ = 0. Очевидно,

(г г, r i) = (r i. Го) = . . . = (r„ i, 0) = r„ i.

Найдем теперь последовательности [Ь) и {В}, такие, что для

всех к

г„ 1 = Ъг + BR,

где Rk = rfe-i- Так как = r.g - аГи-г, то = Ru-i - аг-и так что

ЪкГк + BkRu = Ьи {Rh~i - аги-г) + ВГи-х == = {Bk - Ukbk) Гй 1 + bft Rk-i-

Следовательно, можно взять = О, = 1 и затем двигаться в обратном направлении, полагая

Проделав эти выкладки, получим для 6 i и 5 i равенство

[x] означает наибольшее целое число, не превосходяш,ее х.

При такой форме алгоритма сначала вычисляются а, /•(,, %, Г1, . . ., а„-1, г„ 1, а„, г„ = О, а затем fe„ = О, = 1, Ь„ 2, Ьп-з- • • 1- 0 b-i = Ьо)- Слабым местом этого метода является то, что для вычисления необходимых чисел и Ь. приходится запоминать все промежуточные результаты а, г,,, г, . . ., a„-i, r„ i. Если числа начальной пары алгоритма велики, то список этих промежуточных результатов достигает существенных размеров.

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

2.11. Другой вариант алгоритма Евклида. Пусть заданы числа г 2 и г.. Положим

Р-2 = = 1.

и будем далее вычислять а, г, Pk и согласно формулам rk-i = акГк-1 + гь, О < Tft < rfe i, = auPk-i +

При r„ = О вычисления прекращаются. Легко проверить, что

+ + ft = ft-ift + ftft-i

РкГк+1 + Pk+iTh = Pk {-ak+in + fh-i) +

+ {k+lPk + Pk-l) Гк = Рк~1Ги + РкГк-1

и что

- Pk+i4k = («ft+i9ft + Qk-i)Pk - - (flft+iPft + /ft-i)5ft = - {ЧкРк-1 - /ftft-i)-Начиная с A: = -1 и проводя вычисления по индукции в соответствии j с этими тремя формулами, получим, что для всех к -i

Чк-гГк + ЧкГк-1 = -1 Рк-лТи + РкГк-1 = ЧкРк-1 - Jftft-i = (-!)"• При к = п эта формула дает г„ = О и потому

ЧпГп-1 = -1 РпТп-\ - "-2»

(2.12)

rlPn-i-r-Qn-i = ( - 1)"г„-1 = ( - 1Г(Г~2, r-i).

Более того, можно сделать некоторые выводы о величинах и qn-i- Так как а„ > О, то, очевидно,

Рп-1<.Рп=~- , qn-i<qn = -~

Отметим, что в рассматриваемой процедуре на каждом шаге необходимо запоминать не более семи чисел: два г, два р, два q и одно а. В остальных промежуточных результатах нет никакой )1еобходимости. В конце алгоритма, при г„ = О, необходимые множители Рп-1 и так же как и их н.о.д., уже вычислены.

Эта вариация алгоритма Евклида называется вариантом непрерывных дробей. Название это объясняется тем, что

ЛГожно также показать, что частные pjq, представляют собой соответствующие части этой непрерывной дроби, а именно

Pfe Чк

= ао + -

Читатель, заинтересованный в более глубоком изучении непрерывных дробей, может найти превосходное введение в эту теорию в гл. 5 книги Маккоя [1965] i).

Алгоритм Евклида для многочленов над полем аналогичен алгоритму Евклида для чисел. Пусть даны многочлены

г<-2> и г<-1, r-2() = 2r-V, r<-(:r) = Srl-V,

) См. также А. Я. X и н ч и н, Цепные дроби, Фи.эматгиа, М., 1961.-

Jpu.v. перев.

а al"" и ri"" - элементы поля F. Как и ранее, мы будем обозначать через deg г> степень многочлена г**) (наибольшее i, для которого г> =70). Если deg г" < degr", то, используя алгоритм деления многочленов, находим такие многочлены а<-> и г\ что г№-2) а WrC-1) + rW, deg г" < deg r- .

Операция алгоритма деления (с остатком) для многочленов несколько сложнее, чем для чисел. В любом случае имеются делимое D и делитель d и требуется найти частное Q и остаток R. (В алгоритме Евклида D = г-), d = г-, (? = а", R = г").) При этом должно выполняться условие deg R <. deg d. Для построения многочленов R ж d применяем итерацию. Начинаем с i?" = Z> и = 0. Если deg i?<" > deg d, то полагаем

д(п) старший коэффициент в Д<" д н(п) <ieg d старший коэффициент в d ♦

(2.13)

(n+l) (" - Д"

Ясно, что deg < deg i?<"> и d(?<"+i>-b i?<"+i> = rf<?<" -b i?">.

Процедура заканчивается, когда deg <; deg d. Далее полагаем

Так как многочлен + i?"> не зависит от n, то он равен + + i?*" = i?"" = D, как и требуется.

Таким образом, алгоритм Евклида для многочленов состоит из нескольких шагов итераций, в каждом из которых вычисляются новое частное а и новый остаток г, что в свою очередь осущест-j вляется путем итераций. В следующем разделе мы, однако, увидим, что эти итерации и подитерации могут быть сведены в одну общую] универсально реализуемую процедуру.

В алгоритме Евклида для многочленов возникает последователь-! ность остатков, степени которых строго убывают. Значит, г"" {х)ф1 Ф О ж г<" (х) - О для некоторого п. Далее

(г(-2) г(-1))=(г(-1), г(0))= ... =(г(«-1), 0) = г<»-1).

Как и в случае чисел, последовательно вычисляются многочлены] j,("-2) j,(0) д ftc-i), удовлетворяющие уравнению

(0y-2)j,(-iy-l) (u-l)

Этот метод обладает тем же серьезным недостатком - он требуе чрезвычайно большого объема памяти для запоминания промежуточ-

ных значений (а} и (г}. По этой причине в качестве более привлекательной альтернативы возникает вариант непрерывных дробей. Полагаем

(-2) = !, с-1) = 0

Как и в случае чисел, многочлены и {() определяются

наряду с {а*} и и, таким образом, сокращается большая

промежуточная память. Так же, как и для чисел, получаем

И») = О,

p(n)r(n-l) = (-2)

Г(- 1) r(-2)(n-1) ( 1) V"-1).

Так как dega<")>0, то, очевидно,

;.(-2) (-1)

degp(»-i)<deg--(; и degg<»-i)<deg--.

Из алгоритма Евклида вытекает несколько следствий. Во-первых, ясно, что любой общий делитель многочленов г" и г~ должен также делить r~j3"" и д"", и, следовательно, любой общий делитель г<" и г<~. делит г>"~. Это доказывает, что г<"~- наибольший общий делитель многочленов г- и г*~>. Во-вторых, ясно, что два н. о. д. этих многочленов должны делить друг друга, В числовой области отсюда сразу следует единственность н. о.д. с точностью до знака. Для многочленов над полем F отсюда вытекает, что н. о. д. двух многочленов определяется с точностью до скалярных множителей - элементов поля F. Эту неоднозначность можно устранить с помощью задания н. о. д. в виде нормированного многочлена со старшим коэффициентом, равным 1. Тогда можно утверждать, что любые два многочлена над F имеют единственный нормированный и.о.д. (исключается случай двух нулевых многочленов). Многочлен (ненулевой степени), не имеющий делителей, кроме скаляров и скалярных кратных самого себя, называется неприводимым. Используя алгоритм Евклида, легко показать, что если неприводимый многочлен / делит произведение многочленов g< и g\ то / делит либо либо gK Действительно, если / не делит g<, то (/, ) = 1 и тогда pf + qg = 1. Значит, pfg + qgg" = = g. Так как / делит оба члена в левой части этого равенства, то он