Конструкция конечного поля из p² элементов

Поле из $p^2$ элементов, где $p$ — нечетное простое число, является квадратичным расширением поля $\mathbb{Z}_p$. Как известно, оно является факторкольцом кольца многочленов $\mathbb{Z}_p[x]$ от одной переменной над полем $\mathbb{Z}_p$ по главному идеалу, порожденному любым неприводимым многочленом степени 2. Естественно в качестве такого многочлена выбрать многочлен $$ f(x) = x^2 - r, $$ где $r$ — любой элемент кольца $\mathbb{Z}_p$, не являющийся квадратом.

Хорошо известно, что группа ненулевых элементов любого конечного поля является циклической. Следовательно, все ненулевые элементы поля $\mathbb{Z}_p$ являются степенями одного элемента $a\in\mathbb{Z}_p$, который порождает циклическую группу порядка $p-1$: $$ \forall b\in \mathbb{Z}_p,\ b\ne 0\quad b = a^k $$ для некоторого $k\in\mathbb{Z}$, $k\ge 0$. При этом, как легко видеть, элемент $b$ является квадратом тогда и только тогда, когда $k$ четное. Отсюда, а также из Малой теоремы Ферма, легко выводится следующее утверждение.

Предложение. Элемент $r\in\mathbb{Z}_p$ является квадратом в поле $\mathbb{Z}_p$ (т.е. $r = x^2$ для некоторого $x\in \mathbb{Z}_p$) тогда и только тогда, когда $$ r^{(p - 1)/2} \equiv 1 \pmod{p}. $$

Это предложение вместе с алгоритмом быстрого возведения в степень дает нам алгоритм проверки, является ли элемент $r$ квадратом в поле $\mathbb{Z}_p$. Поскольку среди ненулевых элементов квадратов столько же, сколько и не квадратов (элементы $a^k$ для четных и нечетных $k$, где $a$ — порождающий элемент циклической группы ненулевых элементов поля $\mathbb{Z}_p$ по умножению), то не квадратов очень много, и, перебирая по порядку числа $0 < r < p$, мы быстро найдем элемент $r\in\mathbb{Z}_p$, не являющийся квадратом. Это значит, что многочлен $$ f(x) = x^2 - r $$ не имеет корней в $\mathbb{Z}_p$, т.е. является неприводимым. Следовательно, факторкольцо $\mathbb{Z}_p[x]/\text{Ideal}(f(x))$ является полем. Это факторкольцо содержит $p^2$ элементов. Каждый элемент факторкольца представляется многочленом степени 1 вида $$ g(x) = ax + b, \quad a,b\in \mathbb{Z}_p. $$ Операции сложения и вычитания определяются естественным образом. Умножаются подобные многочлены с помощью следующего сравнения по модулю идеала, порожденного $f(x)$: $$ x^2 \equiv r \pmod{f(x)}. $$ Отсюда получаем: $$ \begin{array}{l} (ax + b)(cx + d) = acx^2 + (ad + bc)x + bd \equiv \\ \equiv acr + (ad + bc)x + bd = (ad + bc)x + (acr + bd) \pmod{f(x)}. \end{array} $$

Для определения операции деления вычислим обратный элемент к элементу $g(x) = ax + b$, где $a\ne 0$. Имеем: $$ (ax + b)(ax - b) = a^2 x^2 - b^2 \equiv a^2 r - b^2 \pmod{f(x)}. $$ Из того, что $r$ не является квадратом в $\mathbb{Z}_p$, вытекает, что $$ h = a^2 r - b^2 \not\equiv 0 \pmod{p} $$ (иначе получилось бы $r \equiv (b/a)^2 \pmod{p}$). Значит, элемент $h$ обратим в $\mathbb{Z}_p$. Тогда, как легко видеть, элемент $$ h^{-1}(ax - b) $$ будет обратным элементом к элементу $g(x) = ax + b$.

Пример

Постороим поле $\text{GF}(7^2)$, содержащее 49 элементов. Это поле является квадратичным расширением поля $\mathbb{Z}_7$. Найдем элемент, не являющийся квадратом по модулю 7. Элемент $$ r = 3 $$ подходит, т.к. $$ 3^{(7 - 1)/2} = 3^3 = 27 \equiv -1 \pmod{7}. $$ Следовательно, многочлен $$ f(x) = x^2 - 3 $$ неприводим на полем $\mathbb{Z}_7$. Поэтому факторкольцо $\mathbb{Z}_7[x]/\text{Ideal}(f(x))$ является полем, содержащим $7^2 = 49$ элементов. Его элементы представляются линейными многочленами вида $$ ax + b,\quad a, b\in \mathbb{Z}_7. $$ Умножение определяется с помощью сравнения $$ x^2 \equiv 3 \pmod{f(x)}. $$

Для примера перемножим два элемента факторкольца: $5x + 3$ и $2x + 1$. Имеем $$ (5x + 3)(2x + 1) = 10x^2 + (5 + 6)x + 3 \equiv \\ \equiv 3x^2 + 4x + 3 \equiv 3\cdot 3 + 4x + 3 \equiv 4x + 5 \pmod{f(x)}. $$

Теперь найдем обратный элемент к элементу $5x + 3$. Обозначим $$ h \equiv (5x + 3)(5x - 3) \equiv 25x^2 - 9 \equiv \\ \equiv 4x^2 - 2 \equiv 4\cdot 3 - 2 \equiv 10 \equiv 3 \pmod{f(x)}. $$ Вычислим обратный к $h$ элемент в поле $\mathbb{Z}_7$. Имеем $$ h^{-1} = 3^{-1} \equiv 5 \pmod{7}. $$ Следовательно, $$ (5x + 3)^{-1} \equiv h^{-1}(5x - 3) \equiv 5(5x - 3) \equiv \\ \equiv 25x - 15 \equiv 4x + 6 \pmod{f(x)}. $$

Проверим, не ошиблись ли мы и действительно ли элемент $4x + 6$ является обратным к элементу $5x + 3$. Имеем: $$ (5x + 3)(4x + 6) \equiv 20x^2 + (30 + 12)x + 18 \equiv \\ \equiv 6x^2 + 4 \equiv 6\cdot 3 + 4 \equiv 22 \equiv 1 \pmod{f(x)}. $$ Всe верно.

Реализация арифметики в поле $\mathbb{Z}_p$

Программная реализация поля $\text{GF}(p^2)$ подразумевает, что мы умеем работать с элементами поля $\mathbb{Z}_p$, т.е. с целыми числами, рассматриваемыми по модулю простого числа $p$. При этом в практических приложениях (например, в криптографии) простое число $p$ может быть очень большим (например, 200-значным десятичным), и тупые алгоритмы перебора, к примеру, при нахождении обратного элемента, для таких больших чисел не работают. В теории чисел есть два замечательных алгоритма, которые надо использовать: 1) алгоритм быстрого возведения в степень и 2) расширенный алгоритм Евклида. Оба эти алгоритма являются настоящими жемчужинами среди множества алгоритмов, известных человечеству. В нашем случае алгоритм быстрого возведения в степень по модулю $p$ позволяет проверить, является ли число $r\in\mathbb{Z}$ квадратом по модулю $p$; расширенный алгоритм Евклида позволяет для числа $h\in\mathbb{Z}$, $h\not\equiv 0 \pmod{p}$ вычислить его обратный элемент по модулю $p$. Как вариант, для нахождения обратного элемента можно возвести $h$ в степень $p-2$ по модулю $p$, поскольку $h\cdot h^{p-2} = h^{p-1} \equiv 1 \pmod{p}$ по Малой теореме Ферма; следовательно, $h^{-1} \equiv h^{p-2} \pmod{p}$.

Подробное описание этих алгоритмов содержится в статье Теория чисел и кодирование с открытым ключом.