Конечное поле

Общеизвестными примерами полей являются поля рациональных, вещественных и комплексных чисел. Конечное поле, или, как его называют, поле Галуа , отличается от указанных лишь тем, что оно состоит из конечного числа элементов.

Как доказывается в высшей алгебре, число элементов конечного поля всегда удовлетворяет условию

(П. 18)

где — простое число, а .

Другими словами, если число b элементов некоторого множества не удовлетворяет условию (П. 14), то для этого множества элементов невозможно определить операции сложения <и умножения с указанными свойствами. Так, например, невозможно образовать поле с числом элементов, равным 6, 10, 12, 14 и т. д., но можно построить поле с числом элементов, равным 2, 3, 4, 5, 7, 8, 9, 11 и т. д.

Наиболее просто операции умножения и сложения выполняются в поле с числом элементов, равным простому числу . Здесь они определяются как операции сложения и умножения по модулю , а сами элементы образуют последовательность чисел

(П. 19)

Такое поле иногда называют полем наименьших неотрицательных вычетов по модулю . Операции сложения здесь имеют вид

(П. 20)

и читается: сумма и сравнима с по модулю . Аналогично для умножения можно записать

(П.21)

(читается: произведение и сравнимо с по модулю .

В (П.20)-(П. 21), и — это некоторые числа из множества (П. 19).

Операции сложения и умножения по модулю определяются и соответственно выполняются чрезвычайно просто.

Для любых двух чисел и из (П.19) их сумма по модулю находится следующим образом:

(П.22)

где сложение и вычитание проводится по обычным правилам арифметики.

Произведение любых двух чисел (П.19) по модулю находится по правилу:

(П.23)

где умножение и деление проводятся по обычным правилам арифметики.

В общем случае сумма по модулю равна

(П.24)

В (П.24) умножение, сложение и деление проводятся по обычным правилам арифметики.

Табл. (П.1) представляет собой таблицы сложения и умножения для поля из двух элементов (0, 1), а табл. (П.2) —для поля из пяти элементов (0, 1, 2, 3, 4).

Таблица (П.1)

Здесь в каждой таблице на пересечении строки и -го столбца записан соответственно результат сложения или умножения чисел, стоящих в строке самого левого столбца и столбце самой верхней строки.

Следует обратить внимание на то, что в поле GF (2) каждый элемент является отрицанием самого себя (П.24) , а обратным элементом единицы является сама единица (П.16)

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

Таблица П.2

Сложнее обстоит дело с выполнением этих операций в поле когда . Прежде всего сделаем несколько замечаний о структуре таких полей (их иногда называют полями расширения). Обозначим элементы ноля расширения через

(П.25)

где — нуль поля; — единица поля, a

Предположим, что для элементов (П.25) определены правила сложения и умножения, которые заданы в виде таблиц типа П.1, П.2. Тогда, как доказывается в высшей алгебре, среди элементов (П.25) всегда можно таких, которые сами образуют поле относительно указанных операций сложения и умножения в поле При этом указанные операции совпадают с операциями, определенными над полем из элементов. Такое подмножество элементов (П.25) называют подполем поля .

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

Указанное обстоятельство существенно облегчает метод построения таблиц сложения и умножения для поля

Пример. Пусть требуется найти таблицы сложения и умножения для поля из четырех элементов(0, 1, 2, 3) (табл. (П.3).

Таблица П.3

В данном случае поле содержит подполе , причем последнее состоит из 0 и 1. Поэтому четыре элемента, находящиеся в левом верхнем углу каждой табл. П.3, в соответствии со сказанным полностью совпадают с соответствующей табл. П.1.

Займемся сначала таблицей сложения. Прежде всего в силу П.4 можно сразу заполнить верхнюю строку (левый столбец) таблицы сложения. Следовательно, остается определить только следующие соотношения: (напомним, что согласно закону коммутативности и т.д.

Операция сложения однозначна, поэтому в каждой строке элементы 0, 1, 2, 3 должны встречаться только по одному разу. Следовательно, сумму элементов можно полагать равной либо 2, либо 3. Но из равенства вытекает, что , что невозможно. Таким образом, и .

Аналогично может равняться 0 или 1. Чтобы выяснить истинное значение этой суммы, заметим, что в поле элемент совпадает со своим отрицанием.

Действительно, так как в поле

(П.25)

то это равенство должно выполняться и в любом поле . С другой стороны, согласно определению единичного элемента для любого из поля получили

(П.27)

или, с учетом (VI.25),

(П.28)

что справедливо для любого элемента поля . Теперь легко достроить таблицу сложения, полагая и в силу (П.28), а по причине однозначности операции сложения.

Из полученной таблицы легко усмотреть для любого а из поля GF (4). Это не случайно. В общей теории полей доказывается, что 0 для любого а из . Это еще одно примечательное свойство числа , которое вообще играет большую роль в теории конечных полей и называется характеристикой поля .

Обратимся теперь к таблице умножения. Соотношения (П.5)(П.6) полностью определяют первую и вторую строки (два левых столбца) этой таблицы.

Следовательно, остается только определить следующие произведения: .

В силу однозначности операции умножения в каждой строке таблицы умножения элементы 0, 1, 2, 3 должны встречаться только по одному разу. Поэтому может равняться либо 3, либо 1. Допустим, что , но , поэтому . Воспользуемся теперь дистрибутивным законом и раскроем скобки: . Так как , то отсюда (в силу единственности 1) получаем , что невозможно. Таким образом, и , что и приводит к указанной таблице умножения в поле .

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

(П.29)

Это примечательное равенство справедливо в силу условия , на что уже обращалось внимание ранее.

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