Конечные поля многочленов.
Возьмем в кольце многочленов Zp[x] некоторый неприводимый многочлен f(x)=akxk + … + a1x + a0 и построим полную систему наименьших вычетов по модулю f(x) так же, как строили полную систему наименьших неотрицательных вычетов в Z. В эту систему войдут все многочлены из Zp[x], чья степень меньше k, а таких ровно pk штук. Получившееся множество вместе с операциями сложения и умножения полиномов с коэффициентами из Zp по модулю f(x) обозначим как Zp[x]\f(x). Эта конструкция будет полем мощности pk, в котором единичным элементом является 1, а нулевым – 0.
В дальнейшем будем обозначать Zp[x]\f(x) как GF(pk) (поле Галуа).
Заметим, что GF(pα) имеет характеристику p, и GF(p) (то есть Zp) является подполем GF(pα) для соответствующего p.
Каждый ненулевой элемент поля обратим, и обратный элемент можно найти с помощью расширенного алгоритма Евклида.
Пример.
Построим в Z2[x] поле GF(23)=Z2[x]\f(x), где f(x)=x3+x2+1 – неприводимый многочлен.
GF(23)={0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1}. Мощность построенного множества составляет 23=8 элементов.
Продемонстрируем процедуры сложения, умножения многочленов и отыскание обратного элемента в Z2[x]\f(x) на примере:
(x+1)+(x2+x+1)= x2.
(x+1)·(x2+x+1)=(x3+x2+x+x2+x+1) mod f(x) = (x3+1) mod f(x) = x2.
Отыщем обратный к (x+1) по модулю f(x):
x3+x2+1=x2(x+1)+1 1=f(x)—x2(x+1) (x+1)-1=(—1 mod 2) x2 =x2.
Проверка: x2(x+1)mod f(x)=1. Решение верно.
Поскольку GF(pα) является конечным полем, то, как известно из алгебры, мультипликативная группа его ненулевых элементов является циклической, а значит в нем существует порождающий элемент. Если многочлен f(x) степени m неприводим, и порождающим элементом мультипликативной группы ненулевых элементов поля Zp[x]\f(x) является многочлен g(x)=x, то f(x) называют примитивным многочленом.
Например, нетрудно проверить, что многочлены x3+x2+1 и x3+x+1 являются примитивными над Z2.
Теорема 1
Неприводимый многочлен f(x) из Zp[x] степени m примитивен f(x)\(xk—1) для всех k ≥ pm—1.
Теорема 2
Для любого m≥1 существует φ(pm—1)/m примитивных многочленов степени m над полем Zp.
Заметим, что не существует эффективного детерминированного алгоритма нахождения примитивных многочленов. Проще всего генерировать многочлен заданной степени случайным образом и проверять, не является ли он примитивным, например, с помощью критерия Эйзенштейна.
Для конечных полей многочленов, так же как и для Zp, определено понятие дискретного логарифма.
Дата добавления: 2018-11-26; просмотров: 713;