Список статей

Мы в социальных сетях

       

Поля Галуа

Теория конечных полей

Аксиомы конечного поля

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

Конечное поле \(F\{a, \oplus, \circledast\}\), где \(\oplus\) - первая операция \(\circledast\) - вторая операция
Операция \(\oplus\):

  1. Замкнутость: \(\forall a, b \in F\) выполняется \(c = a \oplus b, c \in F\)
  2. Ассоциативность:\(\forall a, b, c \in F\) выполняется \((a \oplus b)\oplus c = a \oplus (b\oplus c)\)
  3. Коммутативность: \(\forall a, b \in F\) выполняется \((a \oplus b) = b \oplus a\)
  4. Нейтральный элемент: \(\theta | a\oplus\theta = a, a\in F\)
  5. Инверсия любого элемента: \(\forall a \exists a^{-1}, a\oplus a^{-1} = \theta \)

Операция \(\circledast\) отвечает тем же требованиям что и \(\oplus\). Однако для второй операции \(\circledast\) не существует инверсии для нейтрального элемента \(\theta \) первой операции. Например, если перва операция — \('+'\), а вторая \('\cdot'\), то фактически это означает что в полученом поле можно складывать, вычитать, умножать и делить. Но, поскольку \(\theta = 0\) (нейтральный элемент относительно \(+\)) и для нуля не существует мультипликативной инверсии, т.е. \(\theta \cdot\theta = 1\), то в конечном поле мы не можем делить на ноль.

В информационных технология один из удобных способов использовать поля Галуа — это определить полиномы (порядка \(n\)) с коэффициентами в поле \(GF(2)\) и интерпретировать их как числа. Например, полином \(x^3+x+1\) одновременно является числом \((1011)_{2} = (11)_{10}\). Как видно из примера степень икса определяет позицию в двоичном слове, а коэффициенты могут принимать значения \(1\) или \(0\).

Операция \(\oplus\) (сложения)

Стоит отметить, что операции над полиномами проходят в поле \(GF(2^n)\), а операции с коэффициентами в поле \(GF(2)\). Операции сложения не создают полинома, выходящего за пределы поля, чего нельзя сказать об умножении. В нашем случае, сложение двух полиномов (или же двоичных слов) есть побитовая операции xor. Нейтральный элемент для операции сложения есть нулевой полином (грубо говоря ноль). Аддитивная инверсия (обратный элемент) — это сам полином.

Операция \(\circledast\) (умножения)

Умножение двух полиномов — это умножение каждого элемента первого полинома на каждый элемент второго (прим. \(x^a \cdot x^b = x^{a+b}\)). Заметьте, что умножение коэффициентов происходит в поле \(GF(2)\). Как уже упоминалось выше, результат сумножения может быть полиномом степени, выше \(n\)Для того, что бы выполнялось условие замкнутости, произведение полиномов (вышедшее за рамки поля) следует взять остаток от деления на неприводимый полином степени \(n\). Неприводимый полином (многочлен) степени \(n\) — полином, который нельзя представить в виде произведения неконстантных полиномов степени ниже \(n-ой\). Таким образом, неприводимый полином выступает в качестве модуля (как простые числа выступают модулями для полей с целыми числами). В следующей статье рассматриваются алгоритмы генерации таких многочленов. Нейтральный элемент для операции умножения — это полином \(1\cdot x^0 = 1\). Мультипликативная инверсия находится с помощью расширенного алгоритма Евклида для полиномов.

Нет комментариев



ru |  en