Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
465
І Іриложение З
Нейтральный элемент кольца относительно операции “+” называют нулем кольца и обозначают через 0. При умножении на 0 любого элемента кольца будет получаться 0.
Можно отдельно рассмотреть множество всех ненулевых элементов кольца с операцией умножения Для этого
множества можно ввести понятия нейтрального и обратного элементов относительно операции умножения Нейтральный элемент кольца относительно операции называют единицей кольца и обозначают через 1.
Единица существует не в любом кольце. Например, в кольце четных целых чисел единица отсутствует. Если в кольце существует единица, то в общем случае обратные элементы определены не для всех элементов кольца.
Полем называется коммутативное кольцо с единицей, отличной от нуля, в котором любой ненулевой элемент обратим.
Кольцо вычетов целых чисел по модулю п является полем в том и только в том случае, когда п — простое число. Другими примерами полей являются хорошо известные множества рациональных, действительных и комплексных чисел с обычными операциями сложения и умножения.
Группы подстановок
Подстановкой непустого множества M называют любое биективное (взаимно однозначное) отображение множества M в себя. Множество всех подстановок на множестве M обозначают через S(M).
Множество S(M) относительно операции суперпозиции отображений образует группу. Если M — конечное множество мощности и, то говорят, что S(M) — симметрическая группа подстановок степени п.
Группа S(M) является коммутативной только в случае п< 2.
Заметим, что, перенумеровав элементы множества M некоторым фиксированным образом: M= {х}9х29...,хп } и ото-466
Элементы алгеЬры и теории чисел
ждествив элементы х, с их номерами /, вместо группы S(M) можно рассматривать группу S(Q), где Q = {1,2,...,и}. Обычно группу S(Q) обозначают через Sw.
Любая подгруппа G группы Sn (подмножество группы Sn, которое само является группой) называется группой подстановок степени п.
Конечные ПОЛЯ
Число элементов конечного поля равно р для некоторого простого числа р и натурального числа t. Обычно поле из р* элементов обозначается GFipt). Пусть q^p1.
Сформулируем основные свойства конечных полей.
1. Все элементы поля GF(q) являются корнями многочлена
Xq - X .
2. Любой многочлен / (х) степени т. неприводимый над по-
т
лем GF(q\ является делителем многочлена хч -х. (В частности, все корни многочлена Дх) содержатся в поле GF(qm\ то есть оно является полем разложения этого многочлена.)
т і
3. Любой делитель многочлена хч -1, неприводимый над полем GF(q), имеет степень, делящую значение т.
4. В поле GF(q) существует примитивный элемент а такой, что все ненулевые элементы поля представляются в виде его степеней, то есть мультипликативная группа конечного поля является циклической.
В прикладных целях обычно используются задания конечных полей в виде кольца вычетов целых чисел по простому модулю р (поле GF(p)) либо в виде фактор-кольца кольца многочленов над полем GF(p) по модулю неприводимого многочлена (поля GF(p% t> I).
В последнем случае для задания поля GF(pl) рассматриваются многочлены над полем GF(p). Для них вводится поня-
467
/ Іриложение З
тие деления с остатком: разделить многочлен а(х) на многочлен Ь(х) степени 5 — это значит представить многочлен а(х) в виде
а(х) = q(x) • b(x) + г(х),
где степень многочлена г(х) строго меньше s.
По аналогии с целыми числами вводятся понятия вычета по модулю многочлена Ь(х), сравнимости многочленов и операции сложения и умножения по модулю многочлена.
Роль полной системы вычетов по модулю многочлена р(х) выполняет множество всех возможных остатков от деления многочленов над полем GF(p) на р(х). Другими словами, полную систему вычетов по модулю многочлена р(х) степени s образует множество многочленов
{г(х) = г0 + + г0,.eGF(p)}.
Множество вычетов по модулю фиксированного многочлена р(х) степени s с операциями сложения и умножения образует коммутативное кольцо. Это кольцо является полем в том и только в том случае, когда многочлен р(х) неприводим (т.е. не раскладывается над GF(p) в произведение многочленов меньших степеней).
Наличие в конечном поле примитивного элемента а позволяет ввести понятие логарифма для ненулевых элементов этого поля. Логарифм элемента /3 по основанию а определяется как наименьшее целое неотрицательное число к, удовлетворяющее равенству P = ct. В настоящее время задача вычисления логарифма в конечном поле в общем случае не имеет достаточно эффективных алгоритмов решения и по этой причине, наряду с задачей разложения на множители, используется при построении стойких криптографических алгоритмов и протоколов.
468
Литература
[Ано97]
[Арш83]
[Баб97]
[Бер92]
[Бил69]
[Бол86]
[Бра99]
[Вар95]
[ВарОО]
[Вар96]
[Г ай94]
Анохин М. ИВарновский Н. П., Сиделъников
B. М., Ященко В. В. Криптография в банковском деле. —М.: Изд-во МИФИ, 1997.
Аршинов М. H., Садовский JI. Е. Коды и математика. — М.: Наука, 1983.
