Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
(=>-). Любой элемент а € Fg«, удовлетворяющий условию ад = а, должен быть корнем уравнения xq — х — 0. Степень этого полинома равна с, и, следовательно, в поле F9" у него существует не больше q корней, включая нуль. Из пункта 2 следует, что поле F является подполем поля Fgn, которое уже содержит корни уравнения xq — х = 0. Ни один другой элемент поля Fgn не может быть корнем полинома xq — х. о
Создавая поле Fgn над полем F, состоящим из q элементов, мы не требовали, чтобы число q было простым. Иначе говоря, поле F не обязательно является простым. Следующая теорема раскрывает взаимосвязи между полем F и полем Fgn, построенным над полем F, а также описывает природу числа о.
Теорема 5.10 (Критерий подполя). Пусть р — простое число. Поле F является подполем поля Fp« тогда и только тогда, когда поле F состоит из рт элементов, где т — положительный делитель числа п.
Доказательство. (=>) Пусть F — подполе поля Fpn. В этом случае варианты F = Fp или F - Fp« являются тривиальными. Предположим, что поле F является собственным подполем поля Fpn, отличным от поля Fp. Тогда по теореме 5.9.1
Глава 5. Алгебраические основы
203
характеристика поля Fpn равна р. Следовательно, характеристика поля F также равна р. Итак, поле Fp является подполем поля F, которое построено по базису мюля Fp. Этот базис состоит их т элементов, где 1 ^ т ^ п. Требуется лишь роказать, что т | п. Две мультипликативные группы F*n и F* состоят из рп — 1 и рт — 1 элементов соответственно. Поскольку группа F* является подгруппой группы Fpn, из теоремы Лагранжа (теорема 5.1) следует, что рт — 1 | рп — 1. Это условие выполняется, только если тп \ п.
{<=) Пусть тп — положительный собственный делитель числа п, а поле F состоит из рт элементов. Поскольку п/т — положительное целое число, полином степени п/тп, неприводимый над полем F, порождает поле, состоящее из (pm)n/m = рп элементов. Обозначим это поле Fpn. По теореме 5.9.2 поле F является подполем поля Fpn. ?
Пусть f(x) — неприводимый полином произвольной степени п над полем Fp. Из теоремы 5.6 следует, что поле Fpn изоморфно полю Fp[a;]f. Несмотря на то что изоморфные поля не различаются, одно из них иногда оказывается намного удобнее другого. Действительно, ярким подтверждением этого факта является критерий подполя для поля Fpr«. Рассмотрим еще один пример.
Пример 5.19 (Поле F2e).
Разбирая пример 5.18, мы убедились, что поле ?2\х]хв+х4+хз+х+1 представляет собой множество всех полиномов по модулю неприводимого полинома х8 + х4 + + х3 + х + 1 над полем F2 и содержит 28 элементов. Теперь нам известно, что множество F28 также является полем, состоящим из 28 элементов, и может быть представлено в виде векторного пространства
{Ь707 + Ь6в6 + Ь595 + Ь404 + Ь3в3 + Ь2в2 + Ьгв + Ьо},
где в — корень уравнения х8 + х4 + х3 + х +1 = 0, а скаляры 67, be, 65,64,63,62» &i и Ьо е F2. Очевидно, эти поля изоморфны. В частности, элемент поля F2s можно представить в виде байта.
Как указывалось в примере 5.18, умножение элементов в поле ^2 Hi8+i4+i3+:i;+i представляет собой довольно сложную операцию, и для ее выполнения приходится прибегать к делению полиномов с помощью алгоритма Евклида. Умножение элементов в поле F*8, построенном с помощью полиномиального базиса, осуществляется намного проще: путем непосредственного умножения двух элементов и представления результатов в виде линейной комбинации элементов 1, в,..., в7.
Для примера вычислим произведение '57' ¦ '83'.
{в6 + в4 + в2 + в + 1) • (в7 + в + 1) = в13 + вп+в9 + в8 + в6 + в5 + в4 + в3 + 1.
204
Часть II. Математические основы
Поскольку
08 + 04 + 03
+ 0 + 1 = 0,
получаем следующие линейные комбинации:
04 + в3 + 0 + 1,
05 + 04 + в2 + 0, 07 + 06 + 04 + 03, 0s + 08 + 06 + 05.
Следовательно,
0ГЗ+011 +09 + 08+0б+е5 + 04 + 03 + 1 = е7 + 0б + 1
Итак, '57'-'83' = 'СГ.
о
Примечание 5.2. Мы изучили два метода построения конечных полей: поле по неприводимому полиномиальному модулю (5.4.2) и поле, построенное с помощью полиномиального базиса (5.4.3). Б ходе изложения поле, построенное с помощью второго метода, обозначалось как ?q. Однако два изоморфных поля, состоящих из одинакового количества элементов, отождествляются. Это позволяет нам в дальнейшем обозначать через Fg любое конечное поле, состоящее из q элементов, где q — простая степень. п
5.4.4 Первообразные корни
В разделе 4.5 указывалось, что при проверке простоты числа п с помощью эффективного детерминированного алгоритма полная факторизация числа п — 1 порождает "вспомогательную информацию" (т.е. дополнительную информацию для верификации задачи из класса MV). Это утверждение легко доказать, используя факты из теории конечных полей.
Теорема 5.11. Мультипликативная группа (Fpn)* поля Fpn является циклической.
Доказательство. По теореме 5.9.3 множество корней уравнения хрП — 1 = 0 образует группу (Fp«)*. Однако множество корней этого полинома содержит рп — 1 разных (нетривиальных) корней единицы, распределенных на единичной окружности. Итак, существует (рп — 1)-й корень единицы, порождающий группу (Fpn)*. Следовательно, группа (Fpn)* является циклической. п
