Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Предложение II. 1. 8. Для любого q = р3' многочлен X4 — X разлагается в Fp[X] в произведение всех нормированных неприводимых многочленов степеней d, делящих f.
Доказательство. Если присоединить к Fp корень а любого нормированного неприводимого многочлена h(x) степени d\f, мы получаем копию Fpd, которая содержится в Fp/. Так как а — корень Xя - X, этот многочлен делится на h(x). Обратно, пусть h(x) — нормированный неприводимый многочлен, делящий Xя — X. Тогда корни h(x) лежат в F9 (поскольку там лежат все корни Xя — X). Поэтому степень h(x) делит /, согласно предложению П. 1.7, так как присо-
44
гл. ii. конечные поля и квадратичные вычеты
единение корня дает подполе в F9. Таким образом, нормированные неприводимые многочлены, делящие Xя — X, — это в точности те, степени которых делят /. Как мы видели, Xя — X не имеет кратных корней, и это означает, что Xя — X есть произведение всех таких неприводимых многочленов, что и требовалось доказать.
Следствие. Если / есть простое число, то в Fp[X] существует всего (// — p)l f неприводимых нормированных многочленов степени f.
Заметим, что (р* — р)/f при простом / — целое число, так как малая теорема Ферма гарантирует нам, что р1" = р (mod /). Пусть п — число неприводимых нормированных многочленов степени /. Co-
гласно предложению, многочлен X — X степени р есть произведение п многочленов степени / и р неприводимых многочленов X — а, а Є F, степени 1. Приравнивая показатели степеней, получаем равенство р^ = nf + р, из которого следует искомая формула для п.
Предположим теперь, что / — не обязательно простое число. Через nd обозначим число неприводимых нормированных многочленов степени d над Fp. Тогда имеем nj = (р^ — Е^п<*)//> где суммирование распространяется на все делители d числа f,d<f.
Мы распространим теперь временные оценки из главы I, касающиеся арифметики по модулю р, на конечные поля общего вида.
Предложение И. 1. 9. Пусть F9, где q = р*, есть конечное поле и F(X) — неприводимый многочлен степени / над Fp. Тогда два элемента из F9 можно перемножить или поделить за O(log q) двоичных операций. Если к — целое положительное число, то элемент поля F9 можно возвести в степень к за 0((log &)(log3 q)) двоичных операций.
Доказательство. Элемент F9 — это многочлен с коэффициентами из Fp = Ъ/рЪ, рассматриваемый по модулю F(X). Чтобы перемножить два таких элемента, мы сначала перемножаем многочлены. Это требует 0(f ) умножений целых чисел по модулю р (и последующего сложения целых чисел па модулю р, что занимает значительно меньше времени). Затем мы делим полученный многочлен на F(A'): остаток от деления и дает искомое произведение. Деление многочленов требует 0(f) делений целых чисел по модулю р и 0(f ) умножений целых чисел по модулю р. Так как умножение по модулю р требует О (log р) двоичных операций, а деление по модулю р (при использовании, например, алгоритма Евклида) — O(log3p) двоичных операций (см. следствие из предложения I. 2.2), общее число двоичных
2 2 3 3 3
операций равно 0(f log р + /log р) = 0((/logp) ) = O(log q). Что-
§ 1. КОНЕЧНЫЕ ПОЛЯ
45
бы установить такую же оценку для деления, достаточно показать, что обратный элемент можно найти за время 0(log q). Используя алгоритм Евклида для многочленов над полем Fp (см. упражнение 12 § 1.2), мы должны записать 1 как линейную комбинацию данного нам элемента из F9 (т.е. многочлена степени меньше /) и фиксированного многочлена F(X) степени /. Это включает в себя 0(f) делений многочленов степени меньше /, а каждое деление многочленов требует
2 2 3 2 3
0(f log р+ /log р) = 0(f log p) двоичных операций. Таким обра-
3 3 з
зом, общее время составляет 0(f log р) = O(log q). Наконец, возведение в к-ю степень можно производить методом повторного возведения в квадрат тем же способом, что и возведение в степень по модулю (см. конец §1.3). Для этого нужно O(\ogk) умножений (или возведений в квадрат) элементов из F9 и, следовательно, О ((log fc)(log3 q)) двоичных операций. Доказательство завершенно.
В заключение этого параграфа мы дадим пример вычислений с многочленами над конечными полями. Для иллюстрации мы выбрали пример над самым маленьким (но, быть может, наиболее важным) конечным полем — 2-элементным полем F2 = {0,1}. Многочлен в F2[X] — это просто сумма нескольких степеней X. В некотором смысле многочлены над Fp похожи на разложения целых чисел в р-ичной системе счисления: коэффициенты многочлена аналогичны значениям разрядов. Например, при бинарном разложении целое число записывается как сумма степеней 2 (с коэффициентами 0 или 1) — и точно так же многочлен над F2 — это сумма степеней X. Однако это сравнение может вводить в заблуждение. Например, сумма любого числа многочленов степени d есть многочлен степени не больше d. В то "же время сумма нескольких d-битовых чисел будет числом, имеющим более d двоичных разрядов.
Пример 3. Пусть f(X) = X4 + X3 + X2 + 1, д = Х3 + 1 є F2[X]. Найти НОД (/,#), используя алгоритм Евклида для многочленов, и представить этот НОД в виде и(Х)/(Х) + v(X)g(X).
