Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 111

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 105 106 107 108 109 110 < 111 > 112 113 114 115 116 117 .. 125 >> Следующая


§11.1

1.

простое р
2
3
5
7
11
13
17

наименьший образующий
1
2
2
3
2
2
3

число образующих
1
1
2
2
4
4
8

2. а) При gv~l = 1 (mod р2) заменить д на (1 + р)д и показать, чтс*Jgv~x = 1 + SiP> ГДЄ зі и р взаимно просты. Далее, если д> = 1 (mod ра), то сначала показать, что (р — l)|j, т. е. j = (p-l)ji и, таким образом, (1 + gip):i =l(modp°). Пользуясь равенством (l + <7ip)jl = l+Jigip + кратные р2, показать, что Ji делится на ра~1. б) Первая часть — см. упражение 20 к §1.3; вторая часть (сводящаяся к доказательству того, что 5J не сравнимо с 1 по модулю 2™, если только 2™-2 не делит j) аналогична части а).

3. 56.

4. 2 для d = 1: -Y, .Y + 1; 1 для d = 2: X2 + X + 1; 2 для d = 3: X3 + Л"2 + 1, .Y3 + X + 1; 3 для d = 4: X4 + X3 + 1, X4 + X + 1, X4 + X3 + X2 + X + 1; 6 для d = 5: X5 + X3 + 1, Xs + X2 + 1, X5 + Xі + X3 + X2 + 1, Хъ + X4 + X3 + X + 1, Xs+ X4 + X2 + X+ 1, X5 4-Х3 + X2 + X + 1; 9 для d = 6: Х6 + Х5 + 1, Х6 + Х3 + 1, Xе+ X+ 1, Х6 + Х5 + Х4 +Х2 + 1, Х6 + Х5 +Х4 + Х + 1, Xе +X5+ X3+ X2 + 1, X6 + X5 + X2 + X + 1, X6 + X4 + X3 + X + 1, X6 + X4 + X2 + X + 1.

5. 3 для d = 1: X, X ± 1; 3 для d = 2: X2 + 1, X2 ± X + 1; 8 для d = 3: X3 + X2 ± (X - 1), X3 - X2 ± (X + 1), X3 ± (X2 - 1), X3 - X ± 1; 18 для d = 4; 48 для d = 5; 116 для d = 6.

6. (pf -pf")/f.

ОТВЕТЫ К УПРАЖНЕНИЯМ

233

7. а) НОД = 1 = X2 + (X + 1)/. б) НОД = X3 + Xі + 1 = / + (X2 + Х)д.

в) НОД= 1 = (Х-1)/-(Х2-Х + 1)3. г) НОД = Х + 1 = (X- 1)/-(X3-X2 + I)3. д) НОД = .Y + 78 = (5OX + 20)/ + (51,Y3 + 26Х2 + 27Х + 4)д.

8. Так как НОД (/, /') = X"2 + 1, кратные корни — это ±а2, где а — образующий элемент Fg.

9. а) Возвести обе части 0 = a2 + ba + с в р-ю степень и, используя равенства bp = b и ср = с, получить (ар)2 -\-bap + с = 0. б) Два различных корня многочлена равны а и а?. Следовательно, а — это взятая с минусом сумма, а 6 — произведение этих корней, в) (са + d)p + l = (сар + d)(ca + d); далее результат получается перемножением элементов в скобках с использованием б), г) (2 + 3i)5(19 + 1)+1 = (22 + 32)5(2 + Зі) = 14(2 + Зг) = 9 + 4г

10. При каждом делении многочленов (сначала / на д, далее Tj на tj + \) сначала нужно находить обратный по модулю р к старшему коэффициенту г/ + і (на это требуется 0(log3 р) двоичных операций), а затем нужно осуществить 0(d2) умножений целых чисел по модулю р, каждое из которых производится за 0(log2 р) двоичных операций. Таким образом, на каждое деление уходит 0(log3 р + d2 log2 р) двоичных операций, а на весь алгоритм Евклида — 0(d)0(log2 p(logp + d2)) = 0(d log2 p(log p + d2)) двоичных операций. (Это выражение можно упростить, записав его как 0(dlog3p), если d растет не быстрее, чем \Aog р, или 0(d3log2p), если р растет не быстрее, чем ed .)

11. а) Пусть а — корень X2 + X + 1 =0, т.е. три последовательные степени а — это а, а + 1 и 1. б) Пусть а — корень Х3 + Х +1 = 0; тогда 7 последовательных степеней а — это а,а2 ,а + 1, а2 + а,а2 + а + 1, а2 + 1, 1. в) Пусть а — корень X3 — X — 1 =0; тогда 26 последовательных степеней а — это а,а2,а + 1,а2 + q,q2 + а + 1,а2 — a + 1,—q2 — се + 1,—q2 — 1, — а + 1,—а2 + а,а2 —а — 1,—а2 + 1,-1 и далее те же 13 элементов, в которых все « + » заменены « —» и наоборот.

г) Пусть а — корень X2 — X + 2 = 0; тогда 24 последовательные степени а — это а, а — 2, —а — 2, 2а + 2, —а +1,2, затем те же 6 элементов, умноженные на 2, затем умноженные на —1, затем умноженные на —2, — итого все 24 степени а.

12. 0(f2^). Действительно, для каждой из 0(2-') степеней а нужно каждое предыдущее выражение в виде многочлена от а умножить на а и, если возникнет Ot^, то заменить его в полученном выражении, добавив к оставшимся членам многочлен, выражающий Ot^ через более низкие степени а; все это составляет 0(/) двоичных операций.

13. а) р = 2 и 2-ї — 1 — простое число Мерсенна (см. пример 1 и упражнение 2 к §1.4). б) Ясно, что условия выполняются в случае а), а также когда р = 3 и (3-' — 1)/2 — простое число (требуется, как в п. а), чтобы / было простым числом, однако этого недостаточно, как показывает пример / = 5) или когда р = 2р' + 1 при / = 1 и р' простом. Впрочем, неизвестно, является ли бесконечным число простых полей, удовлетворяющих условиям пунктов а) или б) (хотя предполагают, что это именно так). Простые р', для которых 2р' + 1 — такое простое, называются «простыми Жермен» по имени Софи Жермен, которая в 1823 г. доказала, что большая теорема Ферма справедлива, если в показателе — такое простое число.

14. Выбрать последовательность п;- так, чтобы ip(tij)/rij —> 0 при j —> оо (см. упражнение 23 к §1.3) и р не делило никакое Uj, и положить /;- равным порядку р по модулю jij, т.е. наименьшему числу, для которого р?і = 1 (mod п;).

15. Любой многочлен, в котором Xі встречается с ненулевым коэффициентом лишь при p\j.

16. Свести к случаю j = d, показав, что если ff'(а) = а и cr-f (а) = а, то и ffd(a) = а (см. доказательство предложения 1.4.2). Заметить, что поле Fpd,

которое есть поле разложения Xpd — X, содержится в F,, так как любой корень этого многочлена также удовлетворяет уравнению X4 — X (чтобы заметить это, нужно f/d раз возвести обе части равенства ор = а в степень pd).
Предыдущая << 1 .. 105 106 107 108 109 110 < 111 > 112 113 114 115 116 117 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed