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

Зафиксируем любое кольцо Rс единицей е и рассмотрим множество M_rвыражений вида а₀ + a₁x¹+ а₂х² + ... + а_пх^п,    где a₀, a₁,..., а_п ÎR. Выражение вида а₀ + a₁x¹+ а₂х² + ... + а_пх^п называется многочленомот x над кольцом Rи обозначается в виде а(х). Множество всех многочленов от x над кольцом Rобозначается через R[x].

Многочлены а(х), b(х) над полем Р наазывалются сравнимыми по многочлену , если они при делении на  дают одинаковые остатки. Обозначение: .

Для сравнений многочленов имеют место все свойства для сравнения целых чисел по модулю, сравнения многочленов можно почленно складывать, вычитать и умножать.

Отношение сравнимости по многочлену  является отношением эквивалентности на множестве , и потому последнее разбивается на попарно непересекающиеся классы. В одном классе содержатся все многочлены, дающие при делении на один и тот же остаток. Класс, содержащий многочлен , обозначим в виде , а множество всех классов — через . На множестве  введем операции сложения и умножения, положив:

Теорема 1. Множество с определенными выше операциями сложения и умножения является коммутативным кольцом с единицей .

Теорема 2. Кольцо является полем в том и только в том случае, когда многочлен  неприводим над полем Р.

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

.

Таким образом, каждому классу сопоставлен многочлен вида , причем разным классам сопоставлены разные такие многочлены), и все такие многочлены оказались занятыми. Иначе говоря, между множествами классов и многочленов вида  установлено взаимно однозначное соответствие, и потому вместо классов можно оперировать многочленами вида указанного вида. При этом операциям + и × над классами будут соответствовать операции Å и Ä над соответствующими многочленами. Для нахождения результатов операций Å и Ä над многочленами вида  в кольце достаточно соответственно сложить или умножить их как многочлены в , а затем взять остаток от деления полученного многочлена на .

Из представления элементов кольца многочленами вида  легко заметить, что если поле Р — бесконечно, то бесконечно и кольцо . Если же Р конечно и |Р| = q, то .

В частности, если в качестве Р взять знакомое нам поле вычетов Z/p по простому модулю р, а в качестве  неприводимый над полем Р многочлен степени n, то получим поле из  элементов. Это поле называют полем Галуаиз  элементов и обозначают в виде GF(pⁿ). Отметим без доказательства, что любые два поля порядка р^п изоморфны и полями вида GF(pⁿ) исчерпываются с точностью до изоморфизма все конечные поля.

Пример. Построить поле Галуа GF(8).

Так как 8 = 2³, то в качестве исходного поля Р можно взять GF(2) = {0, е}, а в качестве  — неприводимый многочлен степени п = 3, например

.

Тогда элементами исходного поля можно считать многочлены:

.