Конечнопольная арифметика - Википедия - Finite field arithmetic

В математика, арифметика конечных полей является арифметика в конечное поле (а поле содержащий конечное число элементы ) в отличие от арифметики в поле с бесконечным числом элементов, например в поле рациональное число.

Хотя никакое конечное поле не является бесконечным, существует бесконечно много различных конечных полей. Их количество элементов обязательно имеет форму п^п куда п это простое число и п это положительное число, а два конечных поля одинакового размера - изоморфный. Премьер п называется характеристика поля и положительное целое число п называется измерение поля над своим основное поле.

Конечные поля используются во множестве приложений, в том числе в классических теория кодирования в линейные блочные коды Такие как Коды BCH и Исправление ошибок Рида – Соломона, в криптография алгоритмы, такие как Rijndael (AES ) алгоритм шифрования, при планировании турниров и в дизайн экспериментов.

Эффективное полиномиальное представление

Конечное поле с п^п элементов обозначается GF (п^п) и также называется Поле Галуа, в честь основателя теории конечных полей, Эварист Галуа. GF (п), куда п простое число, это просто звенеть целых чисел по модулю п. То есть можно выполнять операции (сложение, вычитание, умножение), используя обычную операцию с целыми числами, с последующей редукцией по модулю п. Например, в GF (5) 4 + 3 = 7 сводится к 2 по модулю 5. Деление - это умножение на обратное по модулю п, который может быть вычислен с использованием расширенный алгоритм Евклида.

Частным случаем является GF (2), где сложение Эксклюзивный или (XOR) и умножение И. Поскольку единственный обратимый элемент - 1, деление - это функция идентичности.

Элементы GF (п^п) можно представить как многочлены степени строго меньше, чем п над GF (п). Затем операции выполняются по модулю р куда р является неприводимый многочлен степени п над GF (п), например, используя полиномиальное деление в столбик. Сложение двух многочленов п и Q делается как обычно; умножение может быть выполнено следующим образом: вычислить W = п⋅Q как обычно, затем вычислите остаток по модулю р (есть способы сделать это лучше).

Есть и другие представления элементов GF (п^п), некоторые из них изоморфны полиномиальному представлению выше, а другие выглядят совершенно иначе (например, с использованием матриц).

Когда простое число равно 2, элементы GF принято выражать (п^п) в качестве двоичные числа, где каждый член полинома представлен одним битом в двоичном выражении соответствующего элемента. Фигурные скобки ("{" и "}") или аналогичные разделители обычно добавляются к двоичным числам или их шестнадцатеричным эквивалентам, чтобы указать, что значение является элементом поля. Например, следующие эквивалентные представления одного и того же значения в конечном поле характеристики 2:

Полиномиальный	Икс⁶ + Икс⁴ + Икс + 1
Двоичный	{01010011}
Шестнадцатеричный	{53}

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

Существует много неприводимых многочленов (иногда называемых приводящие многочлены), которые можно использовать для создания конечного поля, но не все они приводят к одному и тому же представлению поля.

А моник неприводимый многочлен степени $п$ с коэффициентами в конечном поле GF ( $q$ ), куда $q = п т$ для некоторых премьер $п$ и положительное целое число $т$ , называется примитивный многочлен если все его корни примитивные элементы ГФ ( $q п$ ).^[1]^[2] В полиномиальном представлении конечного поля это означает, что $Икс$ примитивный элемент. Существует хотя бы один неприводимый многочлен, для которого $Икс$ примитивный элемент.^[3] Другими словами, для примитивного полинома степени $Икс$ генерировать каждое ненулевое значение в поле.

В следующих примерах лучше не использовать полиномиальное представление, так как значение $Икс$ изменения между примерами. Унитарный неприводимый многочлен $Икс 8 + Икс 4 + Икс 3 + Икс + 1$ над GF (2) не примитивен. Позволять $λ$ - корень этого многочлена (в полиномиальном представлении это было бы $Икс$ ), то есть, $λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Сейчас же $λ 51 = 1$ , так $λ$ не является примитивным элементом GF (2⁸) и порождает мультипликативную подгруппу порядка 51.^[4] Тем не мение, $Икс 8 + Икс 4 + Икс 3 + Икс 2 + 1$ является примитивным многочленом.^[4] Рассмотрим элемент поля $λ + 1$ (в полиномиальном представлении это будет $Икс$ + 1). Сейчас же $(λ + 1) 8 + (λ + 1) 4 + (λ + 1) 3 + (λ + 1) 2 + 1 = λ 8 + λ 4 + λ 3 + λ + 1 = 0$ . Поскольку все корни этого примитивного многочлена являются примитивными элементами, $λ + 1$ является примитивным элементом GF (2⁸) ( $(λ + 1) 255 = 1$ и никакая меньшая мощность не делает). GF (2⁸) имеет 128 генераторов (см. Количество примитивных элементов ). Имея $Икс$ как генератор конечного поля полезен для многих вычислительных математических операций.

Сложение и вычитание

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

В конечном поле с характеристикой 2 сложение по модулю 2, вычитание по модулю 2 и XOR идентичны. Таким образом,

Полиномиальный	(Икс⁶ + Икс⁴ + Икс + 1) + (Икс⁷ + Икс⁶ + Икс³ + Икс) = Икс⁷ + Икс⁴ + Икс³ + 1
Двоичный	{01010011} + {11001010} = {10011001}
Шестнадцатеричный	{53} + {CA} = {99}

При регулярном сложении полиномов сумма будет содержать член 2Икс⁶. Этот член становится 0Икс⁶ и сбрасывается, когда ответ уменьшается по модулю 2.

Вот таблица с нормальной алгебраической суммой и характеристической суммой конечных полей 2 нескольких полиномов:

п₁	п₂	п₁ + п₂ под…
п₁	п₂	К [х]	GF (2^п)
Икс³ + Икс + 1	Икс³ + Икс²	2Икс³ + Икс² + Икс + 1	Икс² + Икс + 1
Икс⁴ + Икс²	Икс⁶ + Икс²	Икс⁶ + Икс⁴ + 2Икс²	Икс⁶ + Икс⁴
Икс + 1	Икс² + 1	Икс² + Икс + 2	Икс² + Икс
Икс³ + Икс	Икс² + 1	Икс³ + Икс² + Икс + 1	Икс³ + Икс² + Икс + 1
Икс² + Икс	Икс² + Икс	2Икс² + 2Икс	0

В приложениях информатики операции упрощаются для конечных полей характеристики 2, также называемых GF (2^п) Поля Галуа, что делает эти поля особенно популярными для приложений.

Умножение

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

Конечное поле Риджндала (AES)

Rijndael (стандартизованный как AES) использует характеристическое 2 конечное поле с 256 элементами, которое также можно назвать полем Галуа GF(2⁸). Он использует следующий приводящий полином для умножения:

Икс⁸ + Икс⁴ + Икс³ + Икс + 1.

Например, {53} • {CA} = {01} в поле Rijndael, потому что

	(Икс⁶ + Икс⁴ + Икс + 1)(Икс⁷ + Икс⁶ + Икс³ + Икс)
=	(Икс¹³ + Икс¹² + Икс⁹ + Икс⁷) + (Икс¹¹ + Икс¹⁰ + Икс⁷ + Икс⁵) + (Икс⁸ + Икс⁷ + Икс⁴ + Икс²) + (Икс⁷ + Икс⁶ + Икс³ + Икс)
=	Икс¹³ + Икс¹² + Икс⁹ + Икс¹¹ + Икс¹⁰ + Икс⁵ + Икс⁸ + Икс⁴ + Икс² + Икс⁶ + Икс³ + Икс
=	Икс¹³ + Икс¹² + Икс¹¹ + Икс¹⁰ + Икс⁹ + Икс⁸ + Икс⁶ + Икс⁵ + Икс⁴ + Икс³ + Икс² + Икс

и

	Икс¹³ + Икс¹² + Икс¹¹ + Икс¹⁰ + Икс⁹ + Икс⁸ + Икс⁶ + Икс⁵ + Икс⁴ + Икс³ + Икс² + Икс по модулю Икс⁸ + Икс⁴ + Икс³ + Икс¹ + 1
=	(11111101111110 мод 100011011)
=	{3F7E mod 11B} = {01}
=	1 (десятичный)

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

                   11111101111110 (мод) 100011011 ^100011011               01110000011110          ^100011011               0110110101110           ^100011011               010101110110            ^100011011               00100011010              ^100011011                 000000001

(Элементы {53} и {CA} являются мультипликативные обратные друг друга, поскольку их продукт 1.)

Умножение в этом конкретном конечном поле также может быть выполнено с использованием модифицированной версии "крестьянский алгоритм ". Каждый полином представлен с использованием той же двоичной записи, что и выше. Восемь битов достаточно, потому что в терминах каждого (сокращенного) полинома возможны только степени от 0 до 7.

В этом алгоритме используются три переменные (в смысле компьютерного программирования), каждая из которых содержит восьмибитное представление. а и б инициализируются множителями; п накапливает продукт и должен быть инициализирован 0.

В начале и конце алгоритма, а также в начале и в конце каждой итерации это инвариантный правда: а б + п это продукт. Очевидно, что это верно, когда алгоритм запускается. Когда алгоритм завершается, а или же б будет ноль, поэтому п будет содержать продукт.

Выполните следующий цикл восемь раз (один раз на бит). Это нормально остановиться, когда а или же б равен нулю перед итерацией:
1. Если крайний правый бит б установлено, исключая ИЛИ продукт п по стоимости а. Это сложение полиномов.
2. Сдвиг б на один бит вправо, отбрасывая крайний правый бит и устанавливая нулевое значение самого левого бита. Это делит многочлен на Икс, отбрасывая Икс⁰ срок.
3. Следите за тем, чтобы крайний левый бит а установлен в единицу и называют это значение нести.
4. Сдвиг а на один бит влево, отбрасывая крайний левый бит и делая новый крайний правый бит нулевым. Это умножает многочлен на Икс, но нам все равно нужно учитывать нести который представляет собой коэффициент Икс⁷.
5. Если нести имел значение один, исключающее или а с шестнадцатеричным числом 0x1b (00011011 в двоичном формате). 0x1b соответствует неприводимому многочлену с удаленным старшим членом. Концептуально старший член неприводимого многочлена и нести прибавляем по модулю 2 к 0.
п теперь есть продукт

Этот алгоритм легко обобщается на умножение на другие поля характеристики 2, изменяя длины а, б, и п и ценность 0x1b соответственно.

Мультипликативный обратный

Смотрите также Алгоритм инверсии Ито – Цуджи.

В мультипликативный обратный для элемента а конечного поля можно вычислить несколькими способами:

Умножая а на каждое число в поле, пока продукт не станет единицей. Это перебор.
Поскольку ненулевые элементы GF (п^п) образуют конечная группа относительно умножения, а^{п^п−1} = 1 (за а ≠ 0), таким образом, обратное а является а^{п^п−2}.
Используя расширенный алгоритм Евклида.
Сделав логарифм и возведение в степень таблицы для конечного поля, вычитая логарифм из п^п−1 и возведя результат в степень.
Сделав модульный мультипликативный обратный таблица для конечного поля и поиск.
Сопоставляя с составное поле где инверсия проще, а отображение обратно.
Построив специальное целое число (в случае конечного поля простого порядка) или специальный многочлен (в случае конечного поля непростого порядка) и разделив его на а.^[5]

Уловки реализации

Таблицы на основе генератора

При разработке алгоритмов вычисления поля Галуа на небольших полях Галуа общий подход оптимизации производительности заключается в нахождении генератор грамм и используйте идентификатор:

{ displaystyle ab = g ^ { log _ {g} (ab)} = g ^ { log _ {g} (a) + log _ {g} (b)}}

для реализации умножения как последовательности поиска в таблице журнала_грамм(а) и грамм^у функции и операция сложения целых чисел. При этом используется то свойство, что каждое конечное поле содержит генераторы. В примере поля Rijndael многочлен Икс + 1 (или {03}) является одним из таких генераторов. Необходимым, но недостаточным условием того, что многочлен является образующим, является несводимый.

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

Эту же стратегию можно использовать для определения мультипликативной обратной с тождеством:

{ displaystyle a ^ {- 1} = g ^ { log _ {g} left (a ^ {- 1} right)} = g ^ {- log _ {g} (a)} = g ^ {| g | - log _ {g} (а)}}

Здесь порядок генератора, |грамм|, - количество ненулевых элементов поля. В случае GF (2⁸) это 2⁸ − 1 = 255. То есть для примера Rijndael: (х + 1)²⁵⁵ = 1. Таким образом, это может быть выполнено с помощью двух таблиц поиска и целочисленного вычитания. Использование этой идеи для возведения в степень также приносит пользу:

{ displaystyle a ^ {n} = g ^ { log _ {g} left (a ^ {n} right)} = g ^ {n log _ {g} (a)} = g ^ {n log _ {g} (а) { pmod {| g |}}}}

Для этого требуется два просмотра таблицы, целочисленное умножение и целочисленная операция по модулю. Опять тест для частного случая а = 0 должно быть выполнено.

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

Умножение без переноски

Для двоичных полей GF (2 ^п), умножение полей может быть реализовано с использованием умножения без переноса, такого как CLMUL_instruction_set, что хорошо для п <= 64. При умножении используется одно умножение без переноса для получения произведения (до 2п-1 бит), другое умножение без переноса предварительно вычисленного обратного полинома поля для получения частного = ⌊ product / (полинома поля) ⌋, умножения частного на полином поля, затем xor: result = product ⊕ ((полевой полином) ⌊ product / (полевой полином) ⌋). Последние 3 шага (pclmulqdq, pclmulqdq, xor) используются на этапе редукции Барретта для быстрого вычисления CRC с помощью инструкции pclmulqdq X86. ^[6]

Составное поле

Когда $k$ это составное число, будет существовать изоморфизмы из двоичного поля GF (2^k) в поле расширения одного из его подполей, то есть GF ((2^м)^п) куда k = м п. Использование одного из этих изоморфизмов может упростить математические соображения, поскольку степень расширения меньше с учетом того, что элементы теперь представлены в более крупном подполе.^[7] Чтобы уменьшить количество вентилей для аппаратных реализаций, процесс может включать множественное вложение, такое как отображение из GF (2⁸) в GF (((2²)²)²).^[8]. Существует ограничение реализации, операции в двух представлениях должны быть совместимы, поэтому необходимо явное использование изоморфизма. Точнее, изоморфизм обозначим map (), это биекция который отображает элемент из GF (2^k) в GF ((2^м)^п), удовлетворяющие: map (a + b) = map (a) + map (b) и map (a b) = map (a) map (b), где операции слева происходят в GF (2^k) перед отображением, а операции в правой части выполняются в GF ((2^м)^п) после отображения.^[9] Изоморфизм обычно реализуется с помощью k к k битовая матрица, используемая для выполнения матричного умножения на GF (2) элемента GF (2^k) рассматривается как k на 1 матрицу. Определим α как примитивный элемент GF (2^k), а β как примитивный элемент GF ((2^м)^п). Тогда β^j = карта (α^j) и α^j = карта⁻¹(β^j). Значения α и β определяют матрицу отображения и ее обратную. Поскольку фактическая математика выполняется в GF ((2^м)^п) приводящий многочлен для GF ((2^м)^п) обычно примитивен и β = Икс в ГФ ((2^м)^п). Чтобы удовлетворить ограничение совместимости для сложения и умножения, выполняется поиск, чтобы выбрать любой примитивный элемент α из GF (2^k), который будет соответствовать ограничению. Отображение в составное поле можно обобщить для отображения GF (п^k) в составное поле, такое как GF ((п^м)^п), за п простое число больше 2, но на практике такие поля обычно не используются.

Примеры программ

Пример программирования на C

Вот некоторые C код, который будет складывать и умножать числа в конечном поле характеристики 2 порядка 2⁸, используемый, например, алгоритмом Rijndael или Рида – Соломона, используя Алгоритм умножения русских крестьян:

/ * Добавляем два числа в конечное поле GF (2 ^ 8) * /uint8_t тупица(uint8_t а, uint8_t б) {	возвращаться а ^ б;}/ * Умножаем два числа в определенном конечном поле GF (2 ^ 8)  * на многочлен x ^ 8 + x ^ 4 + x ^ 3 + x + 1 = 0 * с использованием алгоритма умножения русских крестьян * (другой способ - умножение без переноса с последующим модульным сокращением) */uint8_t гмуль(uint8_t а, uint8_t б) {	uint8_t п = 0; / * произведение умножения * /	пока (а && б) {            если (б & 1) / * если b нечетное, то добавляем соответствующий a к p (конечный продукт = сумма всех a, соответствующих нечетным b) * /                п ^= а; / * поскольку мы находимся в GF (2 ^ m), сложение - это XOR * /            если (а & 0x80) / * GF по модулю: если a> = 128, тогда он будет переполняться при сдвиге влево, поэтому уменьшите * /                а = (а << 1) ^ 0x11b; / * XOR с примитивным многочленом x ^ 8 + x ^ 4 + x ^ 3 + x + 1 (0b1_0001_1011) - вы можете изменить его, но он должен быть неприводимым * /            еще                а <<= 1; / * эквивалент * 2 * /            б >>= 1; / * эквивалент b // 2 * /	}	возвращаться п;}

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

Пример программирования на D

Этот D программа будет умножать числа в конечном поле Риджндала и генерировать PGM изображение:

/**Умножьте два числа в конечном поле GF (2 ^ 8), определенномна многочлен x ^ 8 + x ^ 4 + x ^ 3 + x + 1.*/убайт gMul(убайт а, убайт б) чистый ничто {    убайт п = 0;    для каждого (неизменный убайт прилавок; 0 .. 8) {        п ^= -(б & 1) & а;        авто маска = -((а >> 7) & 1);        // 0b1_0001_1011 - это x ^ 8 + x ^ 4 + x ^ 3 + x + 1.        а = (а << 1) ^ (0b1_0001_1011 & маска);        б >>= 1;    }    возвращаться п;}пустота главный() {    импорт стандартное.stdio, стандартное.Конв;    перечислить ширина = убайт.Максимум + 1, высота = ширина;    авто ж = Файл("rijndael_finite_field_multiplication.pgm", "wb");    ж.writefln("P5  n% d% d  n255", ширина, высота);    для каждого (неизменный у; 0 .. высота)        для каждого (неизменный Икс; 0 .. ширина) {            неизменный char c = gMul(Икс.к!убайт, у.к!убайт);            ж.записывать(c);        }}

В этом примере не используются какие-либо ветки или поиск в таблице, чтобы избежать побочных каналов, и поэтому он подходит для использования в криптографии.

Смотрите также

Логарифм Зеха

Источники

Лидл, Рудольф; Нидеррайтер, Харальд (1983), Конечные поля, Эддисон-Уэсли, ISBN 0-201-13519-1 (переиздано в 1984 г. издательством Cambridge University Press ISBN 0-521-30240-4).
Mullen, Gary L .; Панарио, Даниэль (2013), Справочник конечных полей, CRC Press, ISBN 978-1-4398-7378-6

внешняя ссылка

Гордон, Г. (1976). «Очень простой способ найти минимальный многочлен произвольного ненулевого элемента конечного поля». Письма об электронике. 12 (25): 663–664. Дои:10.1049 / el: 19760508.
да Роша, В. С .; Маркарян, Г. (2006). «Простой способ найти след произвольного элемента конечного поля». Письма об электронике. 42 (7): 423–325. Дои:10.1049 / el: 20060473.
Тренхольм, Сэм. "Поле Галуа А.Е.".
Планк, Джеймс С. (2007). "Библиотека быстрой арифметики поля Галуа на C / C ++".
Викиверситет: Рид – Соломон для кодеров - Арифметика с конечным полем

[1] Корни такого многочлена должны лежать в поле расширения ГФ ( $q$ ), поскольку многочлен неприводим и, значит, не имеет корней в GF ( $q$ ).

[2] Mullen & Panario 2013, п. 17

[3] Планирование и анализ экспериментов. John Wiley & Sons, Ltd. 8 августа 2005 г., стр. 716–720. Дои:10.1002 / 0471709948.app1.

[LN-4] а ^б Lidl & Niederreiter, 1983 г., п. 553

[5] Grošek, O .; Фабшич, Т. (2018), «Вычисление мультипликативных обратных в конечных полях делением в столбик» (PDF), Журнал электротехники, 69 (5): 400–402, Дои:10.2478 / jee-2018-0059, S2CID 115440420

[6] «Быстрое вычисление CRC для общих многочленов с использованием инструкции PCLMULQDQ» (PDF). www.intel.com. 2009. Получено 2020-08-08.

[7] «Эффективные программные реализации Large FiniteFieldsGF (2n) для приложений безопасного хранения» (PDF). www.ccs.neu.edu. Получено 2020-08-08.

[8] "bpdegnan / aes". GitHub.

[9] [1]^{[мертвая ссылка ]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]