Конечные поля

Число q элементов конечного поля равно p^t для некоторого простого числа р и натурального числа t. Обычно поле из p^t элементов обозначается GF (p^t). Пусть q = p^t.

Сформулируем основные свойства конечных полей.

1. Все элементы поля GF (q) являются корнями многочлена х^q - х.
2. Любой многочлен f (x) степени т, неприводимый над полем GF (q), является делителем многочлена х^qm - х. (В частности, все корни многочлена f (x) содержатся в поле GF (q^m), то есть оно является полем разложения этого многочлена.)
3. Любой делитель многочлена х^{qm - 1} -1, неприводимый над полем GF (q), имеет степень, делящую значение т.
4. В поле GF (q) существует примитивный элемент α такой, что все ненулевые элементы поля представляются в виде его степеней, то есть мультипликативная группа конечного поля является циклической.

В прикладных целях обычно используются задания конечных полей в виде кольца вычетов целых чисел по простому модулю р (поле GF (p)) либо в виде фактор-кольца кольца многочленов над полем GF (p) по модулю неприводимого многочлена степени t
(при этом получаются поля GF (p^t), t > 1).

В последнем случае для задания поля GF (p^t) рассматриваются многочлены над полем GF (p). Для них вводится понятие деления с остатком: разделить многочлен а (х) на многочлен b (х) степени s – это значит представить многочлен а (х) в виде

а (х) = q (x) ∙ b (x) + r (x),

где степень многочлена r (х) строго меньше s.

По аналогии с целыми числами вводятся понятия вычета по модулю многочлена b (х), сравнимости многочленов и операции сложения и умножения по модулю многочлена.

Роль полной системы вычетов по модулю многочлена р (х) выполняет множество всех возможных остатков от деления многочленов над полем GF (p) на р (х). Другими словами, полную систему вычетов по модулю многочлена р (х) степени s образует множество многочленов

{ r (x) = r ₀ + r ₁ x +... + r_{s - 1} x^{s - 1}, r ₀,..., r_{s - 1} ∈ GF (p)}.

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

Наличие в конечном поле примитивного элемента α позволяет ввести понятие логарифма для ненулевых элементов этого поля. Логарифм элемента β по основанию α определяется как наименьшее целое неотрицательное число k, удовлетворяющее равенству β = α^k.
В настоящее время задача вычисления логарифма в конечном поле в общем случае не имеет достаточно эффективных алгоритмов решения и по этой причине, наряду с задачей разложения на множители, используется при построении стойких криптографических алгоритмов и протоколов.

Поиск по сайту: