Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 25
Текст из файла (страница 25)
Элементы {1}, {x}, . . . , {xn−1 } образуют базис GF (pn ).В частности, GF (pn ) — векторное пространство размерности n над полем GF (p).Доказательство. Любой остаток представим в виде линейной комбинации указанных векторов:{a0 + a1 x + · · · + an−1 xn−1 } = a0 {1} + a1{x} + · · · + an−1 {xn−1 }.И обратно, пустьb0 {1} + b1 {x} + · · · + bn−1 {xn−1 } = 0.Это означает, что многочлен b0 +b1 x+· · ·+bn−1 xn−1 делится намногочлен n-й степени f (x). Поскольку при умножении ненулевых многочленов их степени складываются, это возможнолишь при b0 + b1 x + · · · + bn−1 xn−1 = 0.
Значит, система {1},{x}, . . . , {xn−1 } линейно независима.Замечание 3.26. Разумеется, построение поля с помощьювычетов по модулю некоторого неприводимого многочлена ианалоги доказанных в этом разделе теорем справедливы нетолько в случае конечных полей. Например, возьмем поле действительных чисел и неприводимый над R многочлен x2 +1.
Построим поле R/(x2 + 1), оно является векторным пространством над R. Элементы {1}, {x} образуют базис этогопространства. Значит, каждый элемент можно представить3.5.Корни многочленов над конечным полем145в виде a{1} + b{x}. Легко проверить, что полученное полеизоморфно полю комплексных чисел C, один из возможныхизоморфизмов задается соответствием 1 7→ 1, {x} 7→ i.Лемма 3.27. Если поле GF (pn ) содержит поле GF (pk ), тоk делит n.Доказательство. Аналогично доказательству леммы 3.23.Если F1 ⊂ F2 , то элементы F2 можно умножать на элементыиз F1 , а также складывать. Поэтому F2 является векторнымпространством над полем F1 размерности d. Значит, в нем|F1 |d элементов. Таким образом pn = (pk )d , что и означаетделимость n на k.Замечание 3.28. Справедливо и обращение леммы 3.27. Оноследует из единственности поля GF (pn ) (см. ниже раздел 3.8)и существования неприводимого многочлена степени k над любым конечным полем (см.
второе доказательство теоремы 3.16на с. 159).3.5. Корни многочленовнад конечным полемТеперь будем решать уравнения в конечном поле. Рассмотрим поле GF (pn ), а в нём — какой-нибудь элемент β, и будеминтересоваться многочленами, для которых этот элемент является корнем.Определение 3.29. Многочлен m(x) называется минимальной функцией для β, если m(x) — нормированный1) многочленминимальной степени, для которого β является корнем.Другими словами, должны выполняться три свойства:а) m(β) = 0;б) f (β) 6= 0 при f (x) 6= 0, deg f (x) < deg m(x);в) коэффициент при старшей степени в m(x) равен 1.1) У нормированного многочлена старший коэффициент равен 1.
Всякий многочлен можно нормировать, умножив его на обратный к старшему коэффициенту, при этом множество корней не изменяется.146Глава 3.Конечные поля или поля ГалуаПример 3.30. Пусть поле представлено как кольцо классоввычетов по модулю неприводимого многочлена a(x) = a0 ++ a1 x + · · · + an xn . Для класса вычетов {x} полином an−1 a(x)является минимальной функцией. Действительно, {x} является его корнем:a0 {1} + a1 {x} + · · · + an {x}n = {a0 + a1 x + · · · + an xn } = {0},т. е. {x} — корень a(x), но тогда {x} является корнем и an−1 a(x).Докажем минимальность. Предположим, что существует многочлен b0 + b1 x + · · · + bn−1 xn−1 , для которогоb0 {1} + b1 {x} + · · · + bn−1 {x}n−1 == b0 {1} + b1 {x} + · · · + bn−1 {xn−1 } = {0}.Это равенство задает линейную зависимость между {1}, {x},{x2 }, .
. . {xn−1 }, которые образуют базис поля как векторногопространства над GF (p). Поэтому все bi = 0.Приведем несколько простых свойств минимальных функций.Утверждение 3.31. m(x) — неприводимый многочлен.Доказательство. Предположим, что m(x) = m1 (x) m2 (x),причем deg mi (x) > 0, поскольку многочлены нулевой степени — константы — образуют группу обратимых элементов вкольце многочленов над полем. Но m(β) = 0, поэтому хотя быодин из множителей m1 (β) или m2 (β) также должен равнятьсянулю (в поле делителей нуля нет).
Значит, один из сомножителей имеет корень β, а его степень меньше степени m(x). Этопротиворечит минимальности m(x).Утверждение 3.32. Пусть m(x) — минимальная функциядля β, и β также является корнем многочлена f (x). Тогдаf (x) делится на m(x).Доказательство. Разделим f (x) на m(x) с остатком: f (x) == u(x)m(x) + v(x), deg v < deg m. Подставляя в это равенствоβ, получаем 0 = f (β) = u(β)m(β)+v(β) = v(β).
Т. е. β являетсякорнем v(x), что противоречит минимальности m(x).Следствие 3.33. Для каждого β есть ровно одна минимальная функция.3.5.Корни многочленов над конечным полем147Действительно, пусть минимальных функций две. Они взаимно делят друг друга, а значит, различаются на обратимыймножитель (константу). Поскольку минимальная функциянормирована, эта константа равна 1, т.
е. функции совпадают.Утверждение 3.34. Для каждого β ∈ GF (pn ) существуетминимальная функция и ее степень не превосходит n.Доказательство. Рассмотрим следующие элементы поля: 1,β, β 2 , . . . , β n , их n + 1 штука, а размерность GF (pn ) как векторного пространства над GF (p) равна n. Значит, эти элементы линейно зависимы, т. е. существуют такие коэффициентыc0 , .
. . , cn , чтоc0 + c1 β + · · · + cn β n = 0.Следовательно, β — корень многочлена c0 +c1 x+· · ·+cn xn . Значит, минимальной функцией для β какой-нибудь будет нормированный неприводимый делитель этого многочлена.Теорема 3.35. Любой ненулевой элемент поля GF (pn ) являnется корнем многочлена xp −1 − 1.Доказательство. Ненулевые элементы поля образуют группу по умножению, порядок этой группы равен pn − 1. Порядок любого элемента (т. е. порядок циклической подгруппы,порожденной этим элементом) по теореме Лагранжа делитпорядок группы. Возьмем произвольный элемент α, обозначимего порядок через k.
Тогда pn −1 = kq, αk = 1, откуда получаемnαp−1− 1 = αkq − 1 = (αk )q − 1 = 1q − 1 = 0.Следствие 3.36. Все элементы поля GF (pn ), не исключаяnнуля, являются корнями многочлена xp − x.Доказательство. Вынесем x за скобку:nnxp − x = x(xp−1− x).У правого множителя корнями будут все ненулевые элементы,а у левого — 0.Теорема 3.37. Многочлен xn − 1 делится на xm − 1 тогда итолько тогда, когда n делится на m.148Глава 3.Конечные поля или поля ГалуаДоказательство.
Пусть n = mk. Сделаем замену переменных: xm = y. Тогда xn − 1 = y k − 1, а xm − 1 = y − 1. Делимостьочевидна, поскольку 1 является корнем y k − 1.Предположим, что n не делится на m, т. е. n = km + r,0 < r < m. Запишем тождествоxr (xmk − 1)(xm − 1)+ xr − 1 =xm − 1xr (xmk − 1) m=(x − 1) + xr − 1.xm − 1Последнее выражение задает результат деления xn −1 на xm −1с остатком, поскольку xmk −1 делится на xm −1 по доказанномувыше. Остаток xr − 1 6= 0 в силу сделанных предположений.Поэтому в этом случае xn − 1 не делится на xm − 1.xn − 1 =Эта теорема дает нам возможность раскладывать некоторые многочлены xn − 1.
Например, пусть мы работаем в характеристике 2 (где +1 = −1), разложим x15 + 1:x15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1).Продолжить это разложение помогает следующая теорема.Теорема 3.38. Все неприводимые многочлены n-й степениnнад GF (p) являются делителями xp − x.Доказательство. Если n = 1, то нужно проверить, что x − a,где a ∈ GF (p), является делителем xp − x. Это очевидно приa = 0. В остальных случаях нужно проверить, что a — кореньмногочлена xp−1 − 1, что уже сделано выше в теореме 3.35.При n > 1 строим по неприводимому многочлену f (x) степени n поле GF (pn ). Тогда многочлен f (x) имеет в GF (pn )корень {x} и, более того, нормированный f (x) является минимальной функцией для {x}, поскольку степени {x} образуютбазис в GF (pn ). C другой стороны, {x} является корнем уравnнения xp −1 −1.
По утверждению 3.32 о минимальной функцииnмногочлен xp −1 − 1 делится на f (x).Используя эту теорему, мы можем завершить разложениеx15 − 1:x15 +1 = (x+1)(x2 +x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1).3.5.149Корни многочленов над конечным полемТеорема 3.39. Любой неприводимый делитель многочленаnxp −1 − 1 имеет степень, не превосходящую n.Доказательство. Пусть ϕ — неприводимый многочлен стеnпени k, который является делителем xp − x. Кратные ϕ образуют максимальный идеал в кольце GF (p)[x], поэтому кольцовычетов по этому идеалу является полем. Поле можно рассматривать как векторное пространство над GF (p), базисомэтого пространства является набор степеней {1}, {x}, . .
. ,n{xk−1 }. Далее будем обозначать {x} = α. Поскольку xp − xделится на ϕ, то в кольце вычетов по модулю идеала (ϕ) поnлучаем αp − α = 0.Любой элемент построенного поля есть линейная комбинация базисных элементов:β = a0 + a1 α + · · · + ak−1 αk−1 .Возведем и левую, и правую части этого равенства в степеньpn , получимnnβ p = (a0 + a1 α + · · · + ak−1 αk−1 )p =nnnnn= ap0 + ap1 αp + · · · + apk−1 (αk−1 )p == a0 + a1 α + · · · + ak−1 αk−1 = β.nОтсюда получаем соотношение β p −β = 0, значит, β — кореньnуравнения xp − x = 0.
Но у этого уравнения не более чем pnразличных корней, а в построенном нами поле — pk элементов.Каждый элемент поля является корнем, следовательно pn >> pk , т. е. n > k.Утверждение 3.40. Пусть некоторый элемент β конечногополя имеет порядок ℓ, а минимальная функция m(x) этогоэлемента имеет степень k. Тогда pk − 1 делится на ℓ, а еслиr < k, то pr − 1 не делится на ℓ.Доказательство. По сути это прямое следствие только чтодоказанной теоремы.По неприводимому многочлену k-й степени m(x) можно построить поле из pk элементов. Ненулевые элементы этого поля,kв том числе и β, являются корнями уравнения xp −1 − 1 = 0,150Глава 3.kКонечные поля или поля Галуаkт.
е. β p −1 − 1 = 0, β p −1 = 1. Это доказывает первую частьутверждения.Вторая часть доказывается от противного. Предположим,что pr − 1 делится на ℓ и r < k. Тогда β — корень уравrнения xp − 1 = 0. Так как m(x) — минимальная функцияrдля β, то xp − 1 делится на m(x) (утверждение 3.32). Получается, что мы нашли неприводимый делитель многочленаrxp −1 степени k. Но k > r, что противоречит доказанной вышетеореме 3.39.Следующая теорема нужна нам для того, чтобы раскладывать многочлены на множители.Теорема 3.41.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
