Введение

Арифметика в поле с конечным числом элементов. В математике, арифметика конечного поля — это арифметика в конечном поле (поле, содержащее конечное число элементов), в отличие от арифметики в поле с бесконечным числом элементов, например, в поле рациональных чисел. Существует бесконечно много различных конечных полей. Количество элементов в них обязательно имеет вид pⁿ, где p — простое число, а n — положительное целое число, и любые два конечных поля одинакового размера изоморфны. Простое число p называется характеристикой поля, а положительное целое число n — размерностью поля над его простым полем. Конечные поля используются в различных областях, включая классическую теорию кодирования в линейных блочных кодах, таких как коды БЧХ и коррекция ошибок Рида — Соломона, в криптографических алгоритмах, например, в алгоритме шифрования Rijndael (AES), в составлении расписаний турниров и в планировании экспериментов.

Примитивные полиномы

Существует множество неприводимых многочленов (иногда называемых примитивными многочленами), которые могут быть использованы для создания конечного поля, но не все они приводят к одному и тому же представлению поля. Монический неприводимый многочлен степени n с коэффициентами в конечном поле GF(q), где 1=q = p^(t) для некоторого простого числа p и положительного целого t, называется примитивным многочленом, если все его корни являются примитивными элементами GF(q^(n)). В полиномиальном представлении конечного поля это означает, что x является примитивным элементом. Существует по крайней мере один неприводимый многочлен, для которого x является примитивным элементом. Иными словами, для примитивного многочлена степени n, степени x генерируют каждое ненулевое значение в поле. В следующих примерах лучше не использовать полиномиальное представление, так как значение x меняется между примерами. Монический неприводимый многочлен x^(8) + x^(4) + x^(3) + x + 1 над GF(2) не является примитивным. Пусть λ является корнем этого многочлена (в полиномиальном представлении это будет x), то есть λ^(8) + λ^(4) + λ^(3) + λ + 1 = 0. Теперь λ^(51) = 1, следовательно, λ не является примитивным элементом GF(2^(8)) и генерирует мультипликативную подгруппу порядка 51. Монический неприводимый многочлен x^(8) + x^(4) + x^(3) + x^(2) + 1 над GF(2) является примитивным, и все 8 корней являются генераторами GF(2^(8)). Все GF(2^(8)) имеют в общей сложности 128 генераторов (см. Количество примитивных элементов), и для примитивного многочлена 8 из них являются корнями примитивного многочлена. Использование x в качестве генератора для конечного поля полезно для многих вычислительных математических операций.

Умножение

Умножение в конечном поле — это умножение по модулю необратимого примитивного многочлена, используемого для определения этого конечного поля. (То есть, это умножение с последующим делением, где в качестве делителя используется примитивный многочлен, а остаток от деления является результатом умножения.) Символ "•" может использоваться для обозначения умножения в конечном поле.

Умножение без носителя

Для двоичных полей GF(2n) умножение в поле может быть реализовано с использованием умножения без переноса, например, набора инструкций CLMUL, который эффективен при n ≤ 64. Умножение включает в себя одно умножение без переноса для получения произведения (до 2n − 1 битов), другое умножение без переноса предварительно вычисленного обратного полевого полинома для получения частного = ⌊произведение / (полевой полином)⌋, умножение частного на полевой полином, а затем операцию XOR: результат = произведение ⊕ ((полевой полином) ⌊произведение / (полевой полином)⌋). Последние 3 шага (pclmulqdq, pclmulqdq, xor) используются в шаге восстановления Барретта для быстрого вычисления CRC с использованием x86 инструкции pclmulqdq.

Композитное поле

Когда k – составное число, существуют изоморфизмы из двоичного поля GF(2k) в расширенное поле одного из его подполей, то есть GF((2m)n), где k = m n. Использование одного из этих изоморфизмов может упростить математические вычисления, поскольку степень расширения меньше, но при этом элементы теперь представлены в большем подполе. Для уменьшения количества логических элементов в аппаратных реализациях процесс может включать множественное вложение, например, отображение из GF(28) в GF(((22)2)2). Существует ограничение реализации: операции в двух представлениях должны быть совместимы, поэтому требуется явное использование изоморфизма. Более точно, изоморфизм обозначается как map, это биекция, которая отображает элемент GF(2k) в GF((2m)n), удовлетворяя условиям: map(a + b) = map(a) + map(b) и map(a b) = map(a) map(b), где операции слева выполняются в GF(2k) до отображения, а операции справа – в GF((2m)n) после отображения. Изоморфизм обычно реализуется с помощью матрицы размером k x k, используемой для выполнения матричного умножения над GF(2) элемента GF(2k), рассматриваемого как матрица размером k x 1. Определим α как примитивный элемент GF(2k), а β – как примитивный элемент GF((2m)n). Тогда βj = map(αj) и αj = map−1(βj). Значения α и β определяют матрицу отображения и ее обратную. Поскольку фактические вычисления выполняются в GF((2m)n), примитивный многочлен для GF((2m)n) обычно является примитивным, и β = x в GF((2m)n). Для обеспечения совместимости операций сложения и умножения выполняется поиск, чтобы выбрать любой примитивный элемент α из GF(2k), удовлетворяющий этому условию. В случае, когда примитивный многочлен для GF(2k) является примитивным, возможен альтернативный метод отображения: 1-битные коэффициенты примитивного многочлена для GF(2k) интерпретируются как m-битные элементы 0 или 1 в GF(2m), и существует m примитивных факторов степени n, любой из которых можно использовать в качестве примитивного многочлена для GF((2m)n). Отображение в составное поле можно обобщить для отображения GF(pk) в составное поле, такое как GF((pm)n), для любого простого числа p.