Конечнопольная арифметика

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

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

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

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

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

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

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

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

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

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

Примитивные полиномы [ править ]

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

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

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

Сложение и вычитание [ править ]

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

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

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

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

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

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

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

Умножение [ править ]

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

Конечное поле Rijndael (AES) [ править ]

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

х ⁸ + х ⁴ + х ³ + х + 1.

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

	( х ⁶ + х ⁴ + х + 1) ( х ⁷ + х ⁶ + х ³ + х )
знак равно	( x ¹³ + x ¹² + x ⁹ + x ⁷ ) + ( x ¹¹ + x ¹⁰ + x ⁷ + x ⁵ ) + ( x ⁸ + x ⁷ + x ⁴ + x ² ) + ( x ⁷ + x ⁶ + x ³ + х )
знак равно	х ¹³ + х ¹² + х ⁹ + х ¹¹ + х ¹⁰ + х ⁵ + х ⁸ + х ⁴ + х ² + х ⁶ + х ³ + х
знак равно	х ¹³ + х ¹² + х ¹¹ + х ¹⁰ + х ⁹ + х ⁸ + х ⁶ + х ⁵ + х ⁴ + х ³ + х ² + х

и

	x ¹³ + x ¹² + x ¹¹ + x ¹⁰ + x ⁹ + x ⁸ + x ⁶ + x ⁵ + x ⁴ + x ³ + x ² + x по модулю x ⁸ + x ⁴ + x ³ + x ¹ + 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.

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

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

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

Этот алгоритм легко обобщается на умножение на другие поля характеристики 2, изменяя длину a , b и p и значение 0x1b соответствующим образом.

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

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

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

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

Уловки реализации [ править ]

Таблицы на основе генератора [ править ]

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

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

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

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

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

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

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

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

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

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

Умножение без ношения [ править ]

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

Составное поле [ править ]

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

Примеры программ [ править ]

Пример программирования на C [ править ]

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

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

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

Пример программирования D [ править ]

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

/ ** Умножение двух чисел в конечном поле GF (2 ^ 8), определяемом полиномом x ^ 8 + x ^ 4 + x ^ 3 + x + 1. * / ubyte  gMul ( ubyte  a ,  ubyte  b )  pure  nothrow  {  убайт  p  =  0 ; foreach  ( неизменяемый  счетчик убайт  ; 0 .. 8 ) { p ^ = - ( b & 1 ) & a ; автоматическая маска = - (( a >> 7 ) & 1 ); // 0b1_0001_1011 - это x ^ 8 + x ^ 4 + x ^ 3 + x + 1. a = ( a << 1 ) ^ ( 0b1_0001_1011 & mask ); b >> = 1 ; }                                  return  p ; }void  main ()  {  import  std . stdio ,  std . Конв ;  enum  width  =  ubyte . макс  +  1 ,  высота  =  ширина ; auto  f  =  файл ( "rijndael_finite_field_multiplication.pgm" ,  "wb" );  f . writefln ( "P5 \ n% d% d \ n255" ,  ширина ,  высота );  foreach  ( неизменяемый  y ;  0  ..  высота )  foreach  ( неизменный  x ;  0  ..  ширина )  {  неизменяемый  char  c  =  gMul ( x . to ! ubyte ,  y. к ! убайт );  f . написать ( с );  } }

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

См. Также [ править ]

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

Ссылки [ править ]

^ Корни такого многочлена должны лежать в поле расширения GF ( $q$ ), так как многочлен неприводим и, следовательно, не имеет корней в GF ( $q$ ).
^ Маллен и Panario 2013 , стр. 17
^ Дизайн и анализ экспериментов . John Wiley & Sons, Ltd. 8 августа 2005 г., стр. 716–720. DOI : 10.1002 / 0471709948.app1 .
^ a b Lidl & Niederreiter 1983 , стр. 553
^ Grošek, O .; Fabšič, Т. (2018), "Вычислительная мультипликативные инверсии в конечных полях по столбику" (PDF) , Журнал электротехники , 69 (5): 400-402, DOI : 10,2478 / Jee-2018-0059 , S2CID 115440420
^ «Быстрое вычисление CRC для общих полиномов с использованием инструкции PCLMULQDQ» (PDF) . www.intel.com . 2009 . Проверено 8 августа 2020 .
^ «Эффективные программные реализации Large FiniteFieldsGF (2n) для приложений безопасного хранения» (PDF) . www.ccs.neu.edu . Проверено 8 августа 2020 .
^ "bpdegnan / aes" . GitHub .
^ [1] ^{[ мертвая ссылка ]}

Источники [ править ]

Лидл, Рудольф; Нидеррайтер, Харальд (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. DOI : 10.1049 / эл: 19760508 .
da Rocha, VC; Маркарян, Г. (2006). «Простой способ найти след произвольного элемента конечного поля». Письма об электронике . 42 (7): 423–325. DOI : 10.1049 / эл: 20060473 .
Тренхольм, Сэм. «Поле Галуа А.Е.» .
Планк, Джеймс С. (2007). "Быстрая арифметическая библиотека поля Галуа на C / C ++" .
Викиверситет: Рид – Соломон для кодеров - Арифметика с конечным полем

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

[2] Маллен и Panario 2013 , стр. 17

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

[LN-4] Lidl & Niederreiter 1983 , стр. 553

[5] Grošek, O .; Fabšič, Т. (2018), "Вычислительная мультипликативные инверсии в конечных полях по столбику" (PDF) , Журнал электротехники , 69 (5): 400-402, DOI : 10,2478 / Jee-2018-0059 , S2CID 115440420

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

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

[8] "bpdegnan / aes" . GitHub .

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