Вычисления в конечных полях и кольцах

Пусть / - натуральное число и F — произвольное конечное поле. Примером такого поля может служить множество.

определенное для любого простого числа р.

Рассмотрим конечное кольцо.

многочленов степени, не превосходящей 1 — 1, коэффициенты которых принимают значения из поля F.

Зафиксируем произвольный многочлен д (х) = Хц=о 9г^х1 степени /, где до,. • , gi € F, и определим на множестве (7.11) операции сложения и умножения следующим образом. Пусть.

тогда.

где операции сложения и умножения коэффициентов ао,.

6о,… bi-1 выполняются в поле F.

Если многочлен д (х) неприводим над полем F, то операция умножения на многочлен Ь{х) обратима для любого отличного от нуля многочлена Ь (х) и множество i?/(F) образует поле. Данное поле принято называть конечным расширением поля F степени /. В случае когда F = F_p, такое конечное расширение принято обозначать символом F_pi, если же F = F_рк для некоторого к, то для конечного расширения используют обозначение F_ры.

Далее нам потребуется еще одна операция, а именно операция взятия обратного элемента в кольце i?/(F). Мы определим многочлен а^-1(х), обратный к многочлену а (х), равенством.

Если многочлен д (х) неприводим над полем F, то сравнение (7.14) разрешимо относительно многочлена а~¹(х) для любого отличного от нуля многочлена а (х). Если же многочлен д (х) приводим, то сравнение (7.14) может быть неразрешимо.

Для вычисления обратного многочлена в общем случае можно воспользоваться расширенным алгоритмом Эвклида^[1] и найти пару многочленов и (х) и г;(х), удовлетворяющих равенству.

Тогда а (х)и (х) = 1 (mod д (х)) и а^-1(.х) = и (х).

Скажем несколько слов о реализации рассмотренных операций.

1. Операция сложения многочленов реализуется просто — это всего лишь покоординатное сложение коэффициентов многочленов а (х) и Ь (х). В случае когда характеристика поля F равна двум, то есть F = F₂fc для некоторого натурального к ^ 1, операции сложения и вычитания в поле F эквиваленты и.

2. При реализации операции умножения многочлена а (х) на многочлен Ь (х) нам необходимо сначала вычислить произведение многочленов, а после произвести его приведение по модулю многочлена д (х). Данная операция является достаточно медленной, поэтому мы опишем алгоритм, позволяющий свести операцию умножения с приведением, но модулю многочлена д (х) к нескольким операциям вычитания многочленов из Я/(Р).

Действительно, найдется такая последовательность многочленов со (х),…, c/_i (x) G Ri (F), что выполнено равенство.

где bi € F — коэффициенты многочлена b (x) € Ri (F).

Обозначим со (ж) = сод + содж + •? • со,*_1Ж^г₁, со (ж) € i?/(F) и положим со (ж) — а (ж). Далее определим.

Как видно из (7.16), умножение многочлена из Ri (?) на многочлен х сводится либо к сдвигу коэффициентов многочлена от меньших разрядов к старшим (при co./_i = 0), либо к сдвигу и однократному вычитанию многочлена д (х) (при co./-i ^ 0). В полях характеристики два операция вычитания, как мы говорили ранее, превращается в операцию сложения ®.

Далее, используя соотношения, аналогичные (7.16), определим многочлены.

тогда.

Данное равенство позволяет предложить эффективный алгоритм умножения двух многочленов из Ri (F).

Упражнение 7.5.1. Реализуйте на ЭВМ алгоритм сложения двух многочленов, а также алгоритм умножения двух многочленов из Ri (F), основанный на равенстве (7.15).

Равенство (7.15) может быть записано в матричной форме, то есть a (x)b (x) — d (x) — Фж^г> где.

и все операции выполняются в поле F. Именно матричная форма записи используется в тексте стандарта FIPS 197, содержащем описание алгоритма AES.

В заключение отметим, что каждый элемент множества F2 может быть естественным образом представлен как элемент множества /?/(IF2) — Действительно, любому вектору 6, записанному в виде Ь = Ьо|| • • • |где Ьо, • • •? bi-i е {0,1}, соответствует многочлен b (x) е 7?/(F'2) вида b (x) = Yli=obiX^l. При этом представление существенно зависит от многочлена д (х) — один и тот же элемент может принадлежать различным множествам: если многочлен д (х) неприводим, то элемент b принадлежит полю, если же д (х) приводим, то b принадлежит кольцу.

• [1] См. Нестеренко Л. Ю. Теоретико-числовые алгоритмы в криптографии. -М.:МИЭМ. — 2012 г.