Введение в теорию конечных полей

кодирование программный алгоритм преобразование

Математическое понятие конечного поля является ключевой категорией теории кодирования, и знакомство с ним начнем с определения поля.

Полем называется множество элементов, замкнутое относительно двух операций, называемых сложением и умножением (обозначаемых привычными знаками «+» и «» (или точкой)). Замкнутость операций означает, что результаты сложения или умножения также являются элементами поля : если , то .

Операции сложения и умножения удовлетворяют следующим аксиомам:

. Сложение и умножение коммутативно:

;

. Сложение и умножение ассоциативно:

;

. Существует нейтральный элемент по сложению и умножению, не изменяющий значения любого элемента поля в этих операциях. Нейтральный элемент по сложению называется нулем и обозначается символом «0», а нейтральный элемент по умножению - единицей и обозначается как «1»:

;

4. Для любого элемента существует единственный обратный или противоположный по сложению (обозначаемый, как «») элемент такой, что

;

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

;

. Сложение и умножение подчиняется дистрибутивному закону:

.

Непосредственно из вышеприведенных аксиом следует, что в любом поле наряду со сложением определена операция вычитания, а с умножением - деление:

, а для - .

Простейшими примерами полей являются числовые поля (поле рациональных и вещественных чисел), имеющих бесконечной число элементов.

Теория кодирования в основном оперирует с конечными полями, состоящими из конечного числа элементов. Общепринятым обозначением конечного поля является (Galois field - в честь французского математика Эвариста Галуа), где - порядок конечного поля, т.е. число элементов поля. Нетрудно доказать, что существуют конечные поля только порядка, равного целой степени простого числа: , где - простое, а - натуральное числа. Конечное поле простого порядка называется простым полем и обозначается . Любое подобное поле может трактоваться как множество остатков от деления натуральных чисел на с операциями сложения и умножения по модулю .

Расширенные конечные поля (порядка , где ) не могут быть построены на основании арифметики по , и их более сложная структура будет рассмотрена несколько позже.