Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 26
Текст из файла (страница 26)
Пусть β ∈ GF (pn ) — корень неприводимого многочлена ϕ(x) степени n с коэффициентами из GF (p).n−1Тогда β, β p , . . . , β pвсе различны и исчерпывают списоккорней этого многочлена.Т. е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.Доказательство. Вначале докажем, что если β — кореньϕ(x), то β p — тоже корень.Как было показано выше, ap = a для всех a ∈ GF (p).Поэтому для любого многочлена f (x) с коэффициентами изGF (p) выполняется равенствоf (x)p = f (xp ).(3.8)Действительно, возведение в степень p сохраняет операциисложения и умножения (см. выше раздел 3.2). Поэтому(a0 + a1 x + · · · + ak xk )p = ap0 + ap1 xp + ap2 x2p + · · · + apk xkp == a0 + a1 (xp ) + a2 (xp )2 + · · · + ak (xp )k .Если ϕ(β) = 0, то и ϕ(β)p = 0.
Из (3.8) получаем, что иϕ(β p ) = 0.n−1Итак, мы доказали, что β, β p , . . . , β p— корни многочлена ϕ(x). Осталось доказать, что они все различны, тогдаиз леммы 3.7 будет следовать, что мы нашли все корни многочлена ϕ(x).3.6.Мультипликативная группа поляℓ151kПредположим, что β p = β p , причем без ограничения общnности ℓ 6 k.
Мы знаем, что β p = β. С другой стороны,посколькуnk n−kk pn−kℓ pn−kn−k+ℓβ p = β p ·p= βp= βp= βp,n−k+ℓ−1то β — корень уравнения xp− 1 = 0. Из теоремы 3.38получаем n − k + ℓ > n, так что ℓ > k. Другими словами, ℓ = kи все выписанные выше корни различны.Пример 3.42. Рассмотрим GF (2) и неприводимый над этимполем многочлен четвертой степени x4 +x3 +1. Найдем его корни. Для этого строим расширение GF (24 ) как кольцо вычетовпо модулю идеала, образованного всеми кратными этого многочлена. Один корень получаем немедленно: {x}. Теперь потеореме 3.41 можно выписать остальные: {x2 }, {x4 } = {x3 +1},{x8 } = {x6 + 1} = {x3 + x2 + x}, так как {x5 } = {x4 + x} == {x3 + x + 1}, {x6 } = {x4 + x2 + x} = {x3 + 1 + x2 + x}.Таким образом, если мы решаем уравнение f (x) = 0, гдеf — неприводимый многочлен, то нужно построить по идеалу (f ) поле.
Первый корень есть сразу, это {x}. Остальныеполучаются применением теоремы 3.41. В общем случае длярешения уравнения нужно уметь раскладывать многочлен нанеприводимые множители.3.6. Мультипликативная группа поляЕсли в поле Галуа убрать нулевой элемент, то остальныеэлементы по умножению образуют группу, которая называется мультипликативной группой поля. Оказывается, что это непросто коммутативная группа, а циклическая группа. Другими словами, в ней есть порождающий элемент, и все остальныеполучаются возведением в степень этого порождающего.Пример 3.43. Возьмем поле GF (2) и его расширение четвертой степени. Как сказано выше (но пока не доказано), расширение четвертой степени можно строить с помощью любого изтрех неприводимых многочленов. Удобнее всего это сделать,если взять многочлен x4 + x + 1. Будем задавать элементы152Глава 3.Конечные поля или поля Галуастепень ααα2α31 + α = α4α + α2 = α5α2 + α3 = α63α + α + 1 = α3 + α4 = α71 + α2 = α + 1 + α2 + α = α8α + α3 = α922α + 1 + α = α + α4 = α10α + α2 + α3 = α11231 + α + α + α = α2 + α3 + α4 = α121 + α2 + α3 = α + α2 + α3 + α4 = α131 + α3 = α + α3 + α4 = α141 = α + α4 = α15===============1,(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,x, x2 , x31, 0, 0)0, 1, 0)0, 0, 1)1, 0, 0)1, 1, 0)0, 1, 1)1, 0, 1)0, 1, 0)1, 0, 1)1, 1, 0)1, 1, 1)1, 1, 1)0, 1, 1)0, 0, 1)0, 0, 0)Таблица 3.1.
Мультипликативная группа поля GF (24 ).расширения наборами коэффициентов многочлена, которыйполучается в остатке при делении на x4 + x + 1, записываяих в порядке возрастания степеней.Порождающим является элемент α = x, который в силу нашего соглашения записывается как (0, 1, 0, 0). Посчитаемпоследовательность степеней α. Результаты вычислений приведены в таблице 3.1.Имея такую таблицу, очень просто производить умножение:(x3 + x + 1) · (x2 + x + 1) = x2 ,(1, 1, 0, 1) · (1, 1, 1, 0) = (0, 0, 1, 0),α7 α10 = α17 = α2 .Теорема 3.44.
Мультипликативная группа любого конечного поля циклическая.Для доказательства этой теоремы нам потребуется дополнительная лемма о конечных абелевых группах.3.6.Мультипликативная группа поля153Лемма 3.45. Пусть m — максимальный порядок элемента вконечной абелевой группе G. Тогда порядок любого элементаG делит m.Доказательство. Группа G по теореме 1.79 однозначно разлагается в прямую сумму примарных компонент — циклических групп, порядки которых являются степенями простыхчисел. Для каждого простого делителя pi порядка группы найдем примарную компоненту hai ∼= Cpki максимального поkiрядка p .
Обозначим произведение чисел pki через M . Попостроению любого x ∈ G выполняется xM = e, т. е. порядок xделит M . С другой стороны, произведение всех порождающихвыбранных примарных компонент a1 a2 . . . имеет порядок M ,поскольку наименьшее общее кратное взаимно простых чиселравно произведению этих чисел. Поэтому m = M .Доказательство теоремы 3.44.
Пусть m — максимальныйпорядок элемента в мультипликативной группе поля.По доказанной выше лемме 3.45, каждый ненулевой элемент поля является корнем уравнения xm = 1. Но у многочлена степени m не более m корней. Поэтому m равен числуненулевых элементов поля. Но это и означает, что мультипликативная группа поля циклическая: существует такой элемент,что его порядок совпадает с порядком группы (и тогда всеэлементы группы являются степенями этого элемента).Мультипликативная группа простого поля характеристики p обозначается GF (p)∗ .
Ее порождающие элементы первообразными корнями по модулю p. Найдем наименьшие первообразные корни по модулям некоторых простых чисел.p = 2. Группа GF (p)∗ состоит из одного элемента 1̄, он жеявляется первообразным корнем.p = 3. Первообразный корень 2̄ — единственный неединичный элемент GF (p)∗ .p = 5. Поскольку (2̄)2 = 4̄, порядок 2̄ равен 4. Других вариантов нет, поскольку порядок элемента — делитель порядкагруппы. Значит, 2̄ — первообразный корень.p = 7.
Снова (2̄)2 = 4̄ 6= 1̄. Но у p−1 = 6 есть еще один делитель 3, а (2̄)3 = 8̄ = 1̄. Поэтому порядок 2̄ равен 3. Поскольку(3̄)2 = 9̄ 6= 1̄, (3̄)3 = 27 6= 1̄, 3̄ — первообразный корень.154Глава 3.Конечные поля или поля ГалуаВычисления можно продолжить. Приведем небольшую таблицу первообразных корней.модуль p3 5 7 11 13 17 19 23 29 31 37 41первообразныйкорень mod p 2̄ 2̄ 3̄ 2̄ 2̄ 3̄ 2̄ 2̄ 2̄ 3̄ 2̄ 7̄3.7. Существование поля изpn элементовТеперь можно вернуться к вопросу о существовании конечного поля заданного размера.
В этом разделе мы всюду полагаем q = pn , где p — простое. Мы докажем существование поляиз q элементов, откуда будет следовать и теорема 3.16 о существовании неприводимого многочлена степени n над полемGF (p). Более того, мы это сделаем двумя способами. Вначаледокажем существование поля из pn элементов, откуда выведем существование неприводимого многочлена степени n надGF (p). Затем мы рассмотрим другое рассуждение, котороевначале устанавливает существование неприводимого многочлена степени n над GF (p), откуда уже следует существованиеполя из pn элементов (факторкольца по модулю неприводимого многочлена степени n).Начнем с того, что построим поле характеристики p, надкоторым многочлен xq −x разлагается на линейные множители(т. е. имеет q корней). Будем строить цепочку полейF0 ⊂ F1 ⊂ . . .по следующему индуктивному правилу.
Поле F0 — это полевычетов GF (p). Пусть поле Fk уже построено. Если в разложении многочлена xq − x на неприводимые множители надFk встретился неприводимый множитель fk степени большей,чем 1, то строим новое поле Fk+1 = Fk [x]/(fk ). В противномслучае построение закончено.Заметим, что в разложении многочлена xq − x над полемFk+1 больше неприводимых множителей, чем в разложении3.7.Существование поля из pn элементов155над полем Fk . Значит, построенная выше цепочка конечна (поскольку число неприводимых множителей многочлена не превосходит его степени). Но тогда над последним в этой цепочкеполем Fm многочлен xq − x разлагается на линейные множители по построению.Корни многочлена xq − x в поле Fm образуют искомое подполе из q n элементов.Вначале разберемся, почему эти корни действительно образуют подполе. Отображение x 7→ xq является n-й итерациейавтоморфизма Фробениуса, который был описан выше в разделе 3.2.
Поэтому (x + y)q = xq + y q , (xy)q = xq y q . Отсюдаполучаем замкнутость множества корней многочлена xq − xотносительно сложения и умножения. 0 и 1 принадлежат множеству корней по очевидным причинам. Но тогда множествокорней замкнуто и относительно взятия обратных как по сложению, так и по умножению, поскольку поле конечно.Может ли так случиться, что у многочлена xq −x в поле Fmразличных корней меньше, чем q? Поскольку этот многочленразлагается на линейные множители, это означало бы наличиекратных корней, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
