АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Какое влияние оказывают начальные и конечные параметры пара на термический КПД основного цикла паросиловых установок

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

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

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

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

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

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

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

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

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

{ r (x) = r 0 + r 1 x +... + rs - 1 xs - 1, r 0,..., rs - 1GF (p)}.

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

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


1 | 2 | 3 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)