Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Решение. Деление многочленов дает нам приведенную ниже последовательность равенств, которая приводит к заключению: НОД (f,g) = X + 1. Другая последовательность равенств позволяет нам, действуя в обратном направлении, выразить X + 1 в виде линейной комбинации / и д. (Заметим, кстати, что в поле характеристики 2 сложение эквивалентно вычитанию: a — b = a + b — 2b = a-\-b.) Имеем
/ = (Х + 1)<7 + Х2 + Х, д = (X+ I)(X2 + X) + (X+ 1), X2 +X = X(X+ 1),
46
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
и затем
X + 1 = д + (X + i)(a'2 + X) =
= д+ (X+1)(/+(X+I)9) =
= (X+l)f + (X2)g. УПРАЖНЕНИЯ
1. Для р = 2, 3, 5, 7, 11, 13, 17 найти наименьшее положительное целое число, которое порождает F*, и определить, сколько среди чисел I1 2, 3,. .., р — 1 образующих.
2. Пусть (Z/paZ)* обозначает множество всех обратимых (т. е. не делящихся на р) вычетов по модулю ра. Внимание: следует различать множество вычетов Z/paZ (в котором ра — pa_1 обратимых элементов) и поле Fp<* (в котором каждый ненулевой элемент обратим). Они совпадают лишь при а = 1.
а) Пусть р > 2 и д — целое число, порождающее F*. Пусть а — любое целое число, большее 1. Показать, что либо д, либо (р+1)д порождают (Z/ра Z)*. Таким образом, (Z/paZ)* — циклическая группа.
б) Показать, что при а > 2 группа (Z/2aZ)* нециклическая, однако число 5 порождает подгруппу, состоящую из половины ее элементов, а именно, из элементов, сравнимых с 1 по модулю 4.
3. Сколько элементов в наименьшем расширении Fs, содержащем все корни многочленов А'2 + X + 1 и .Y3 + X + 1?
4. Для каждой степени d ^ 6 найти число всех неприводимых многочленов над F2 степени d и построить их список.
5. Для каждого d ^ 6 найти число нормированных неприводимых многочленов над F3 степени d и для A ^ 3 построить их список.
6. Предположим, что / есть степень простого числа I. Найти простую формулу для числа нормированных неприводимых многочленов над Fp.
7. При помощи обобщения алгоритма Евклида на многочлены (см. упражнение 12 к § I. 2) найти НОД (/, д) для f,g Є Fp[X] в каждом из следующих примеров. В каждом случае выразить НОД (/, д) как комбинацию / и д, т. е. в виде d(X) = U(X)I(X)+ V(X)9(X).
а) / = .Y3 + .Y 4- I1 д = ,Y2 + X + I1 р = 2;
б) / = .Y6 + Л'5 + Xа + X3 + X2 + X + I1 д = Xі + .Y2 +Х-г1,р = 2;
в) / = X3 - X 4- 1, д = X2 + 1, р = 3;
г) / = X5 + X4 + X3 - X2 - X + 1, д = X3 + X2 + X + 1,р = 3;
д) / = X5 + 88Х4 -(- 73Х3 + 83Х2 + 51Х + 67, д = X3 + 97Х2 + 4OX + 38, р = 101.
8. Вычислив НОД (/, /') (см. упражнение 13 к § I. 2), найти все кратные корни /(X) = X7 -(- X5 + X4 - X3 - X2 - X + 1 Є F3[X] в его поле разложения.
9. Предположим, что а Є Fp2 удовлетворяет уравнению X2 + оХ -(-6 = 0, где а,Ъ Є Fp.
а) Доказать, что ар также удовлетворяет этому уравнению.
б) Доказать, что если а ? Fp, то о = —а — ар и Ъ = ар + 1. в) Доказать, что если a ? Fp1 а с, d Є Fp1 то (ас + d)v + l = d2 — acd + be2 Є Fp.
г) Пусть і — квадратный корень из —1 в Flg2. Использовать пункт в), чтобы найти (2 + Зг)101 (т. е. представить его в виде о + Ы, а, Ъ Є Fig).
§ 2. КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ЗАКОН ВЗАИМНОСТИ
47
10. Пусть d — максимум степеней двух многочленов f,g Є Fp[X]. В терминах d и р оценить число двоичных операций, необходимых для вычисления НОД (/, д) по алгоритму Евклида.
11. Для каждого из следующих полей Fg, где q = pf, найти неприводимый многочлен с коэффициентами из простого поля, корень которого а был бы примитивен (т.е. порождал бы FJ), и выписать все степени а в виде многочленов от а степени меньше /. a) F4. б) Fs- в) F27- г) F25-
12. Пусть F(X) Є F2[vY] есть примитивный неприводимый многочлен степени /. Это означает, что если а — его корень, то степенями а исчерпываются все элементы F*f. Используя обозначение О-большое, оценить (в терминах /) число двоичных операций, необходимое для записи каждой степени а в виде многочлена от а степени меньше /.
13. а) При каких условиях на р и / каждый элемент Fp/ , кроме 0 и 1, является образующим F*f?
б) При каких условиях каждый элемент, отличный от 0 и 1, является либо образующим, либо квадратом образующего?
14. Доказать, что для любого фиксированного р существует такая последовательность qj = pf' степеней р, что случайный элемент Fg1 является образующим F*^ с вероятностью, стремящейся к 0 при j —* 00.
15. Какие многочлены в Fp[X] имеют тождественно нулевую производную?
16. Пусть а — автоморфизм поля F, из предложения П. 1.5. Доказать, что множество элементов, остающихся неподвижными при действии а1, — это поле Fpd, где d — НОД О',/).
17. Доказать, что если Ь — образующий F*„ и d\n, то б(Р"_1)/(Р^-1) — образующий F*d.
§ 2. Квадратичные вычеты и закон взаимности
Корни из единицы. Во многих ситуациях полезно знать решения уравнения Хп = 1. Предположим, что мы работаем в конечном поле F9. Мы сейчас найдем ответ на вопрос: сколько корней гг-й степени из единицы содержится в F9?
Предложение II. 2.1. Пусть g — образующий элемент поля F9. Элемент gJ является корнем п-й степени из единицы тогда и только тогда, когда nj = 0 (mod q — 1). Число корней п-й степени из единицы есть НОД (n,g— 1). В частности, F9 содержит примитивный корень п-й степени из единицы (т. е. такой элемент ?, что степени ? пробегают все корни п-й степени из единицы) тогда и только тогда, когда n|(g — 1). Если ? — примитивный корень п-й степени из единицы в F9, то E,3 — также примитивный корень п-й степени из единицы тогда и только тогда, когда НОД (j,n) = 1.
