ный. Пусть S - ненулевой элемент кольца; тогда 1 s - 1. Так как д просто, то НОД (s, 9) = 1, и в силу следствия 4.1.4

\ = ад -i- bs

для некоторых а и Ь. Таким образом,

i=R,m = R,[aq-\- bs] = R,\R,[aq] f R,[bs]} =

= R, [bs] = R,{R, [b] R, [s]\ =R,\R, [b] s\.

Следовательно, элемент Rq [b] является мультипликативным обратным элементу s относительно операции умножения по модулю д.

Теперь допустим, что д - составное число. Тогда д = rs. Если данное кольцо представляет собой поле, то г имеет обратный элемент Г, и поэтому

S = Rq [S] = Rq [r-i rs] = Rq [r-q] = 0.

Ho s 0, так что мы получили противоречие. Следовательно, рассматриваемое кольцо не является полем. □

В случае когда кольцо отношений Zl{g) образует поле, оно также обозначается через GF (д), чтобы подчеркнуть тот факт, что оно является полем.

4.3. КОЛЬЦА МНОГОЧЛЕНОВ

Многочленом над полем GF (д) называется математическое выражение

где символ X называется неопределенной переменной, коэффициенты fn-i, /о принадлежат полю (9), а индексы и показатели степеней являются целыми числами. Нулевым многочленом называется многочлен / {х) = 0. Приведенным многочленом называется многочлен, старший коэффициент которого равен 1. Два многочлена равны, если равны все их коэффициенты ft.

Степенью ненулевого многочлена / (х) называется индекс старшего коэффициента /„ г; степень многочлена / (х) обозначается через deq / (х). Степень ненулевого многочлена всегда конечна. Степень нулевого многочлена по соглашению полагается равной отрицательной бесконечности (-оо).

Множество всех многочленов над полем GF (д) образует кольцо относительно сложения и умножения, определяемых по обычным правилам сложенияи умножения многочленов. Такое полиномиальное кольцо можно определить для каждого поля Галуа GF (д) Это кольцо обозначается через GF (q) [х]. В исследованиях по кольцам GF (q) [х] элементы поля GF (q) иногда называются скалярами.

Суммой двух многочленов f {х) и g {х) из GF (д) [х ] называется многочлен из GF (q) 1х\, определяемый равенством

f{x)+gix)=}:{fi-gi)x,

где, конечно, члены с индексом, большим наибольшей из степеней многочленов f (х) и g (х), равны нулю. Степень суммы не превосходит наибольшей из этих двух степеней. Например, над G/ (2)

{х + х + I) + {х + X + 1} =

х"" + {I + I) Х + X + (1 + \) = х"" + X.

Произведением двух многочленов из GF (q) [х ] называется многочлен из GF {q) [х\, определяемый равенством

f{x)g{x)= 2: Itfjgi-j] I \/=о у

Например, над GF (2)

{х + х + \) {х + X + \) = х + X + I.

Степень произведения равна сумме степеней множителей.

Кольцо многочленов во многих отношениях аналогично кольцу целых чисел. Чтобы сделать эту аналогию очевидной, в изложении данного параграфа мы следуем § 4.1. Скажем, что многочлен S (х) делится на многочлен / (л:) или что / (х) делит s {х), если существует многочлен а {х), такой, что г {х) а (х) = s (х). Многочлен Р {х), делящийся только на многочлены ар (х) или а, где а - произвольный непулевой элемент поля GF (q), называется неприводимым жногочугенолг. Приведенный неприводимый многочлен называется простым многочленом.

Наибольший общий делитель двух многочленов г {х) и s {х) обозначается через НОД [/ {х), s {х)]н определяется как приведенный многочлен наибольшей степени, делящий одновременно оба из них. Наименьшее общее кратное двух многочленов г {х) и s {х) обозначается через НОК 1/ {х), s (х)] и определяется как приведенный многочлен наименьшей степени, делящийся на оба из них. Как мы увидим, наибольший общий делитель и наименьшее общее кратное определены единственным образом, так что наше определение корректно. Если наибольший общий делитель двух многочленов равен I, то они называются взаимно простыми.

Если г {х) одновременно делится на s {х) и делит s {х), то г (х) = == а S {х), где а - элемент поля GF (q). Это доказывается следующим образом. Должны существовать многочлены а (х) и b {х), такие, что г {х) = S {х} а (х) и s (х) = г (х) b (х); следовательно, (х) = г (х) b {х) а {х). Но степень правой части равна сумме Степеней / {х), b (х) и а (х). Так как эта величина должна быть рав-

НОЙ степени левой части, то b (х) и а (х) должны иметь нулевую степень и, таким образом, являться скалярами.

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

Определение 4.3.1. Пусть / (х) = /п-гх""" + а„ 2 -"" "1-----Ь

+ 1\х + Го - многочлен над GF (q). Формальная производная от г (х) определяется как многочлен вида

/ (х) = ((« - 1)) х"- + ((п - 2)) /-„.а-з -f • • + /-х,

где коэффициенты ((i)) называются числами поля GF (q) и вычисляются как сумма i членов в поле GF {q):

((0) = 1 + 1+•+1.

Легко проверить, что сохраняются многие полезные свойства производных, а именно что

[/ (Х) S (х) V = / (Х) S (х) + г (х) S (х)

и что если а (х) делит / (х), то а (х) делит г (х.)

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

Теорема 4.3.2 (алгоритм деления для многочленов). Для каждой пары многочленов с (х) и d {х), d {х) Ф О, существует единственная пара многочленов Q (х) (частное) и s (х) (остаток), таких, что

с {х) = Q (х) d (х) + S (х)

и deg S (х) < deg d (х).

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

c(x) = d {X) Qi (х) + Si (X) = d (X) Qa (х) + (x),

d{x) [QAx)~QA>c)] = s,{x)-sAx).

В правой части стоит ненулевой многочлен, степень которого меньше deg d (х), а в левой - ненулевой многочлен, степень которого не меньше deg d (х). Следовательно, оба многочлена равны нулю, и представление единственно. □