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

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

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


16. а) Повторное возведение в квадрат требует 0(log3 р) двоичных операций, в то время как для алгоритма Евклида может быть доказана оценка 0(log2 р). б) Повторное возведение в квадрат, по-прежнему, требует времени 0(log3 р), а когда мы выполним первый шаг алгоритма Евклида — деление р на а (что потребует O(logploga) двоичных операций) — оставшаяся часть алгоритма Евклида потребует 0(log2 а) двоичных операций. Таким образом, алгоритм Евклида действует быстрее, особенно при очень малых по сравнению с р числах а.

п 90 91 92 93 94 95 96 97 98 99 100

17.

tp(n) 24 72 44 60 46 72 32 96 42 60 40 18. Не существует такого п, для которого ф(п) является нечетным числом,

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

231

большим 1; v(ra) = 1 для га = 1 или 2; tp(n) = 2 для га — 3,4,6; ip(n) = 4 для га = 5, 8, 10, 12; ч>(п) = 6 для п = 7,9, 14, 18; tp(n) = 8 для га = 15, 16, 20, 24, 30; ip(n) = 10 для га = 11,22; tp(n) = 12 для га = 13,21,26,28,36,42. Чтобы доказать, например, что здесь перечислены все га, для которых ч>(п) = 12, сравним все допустимые разложения 12 на множители (в которых разрешается использовать множитель 1, но не 3) с формулой 4>{\~[ра) = П(ра ~Ра~1)- Получим 1 ¦ 2 • 6, 1 • 12, 2 • 6, 12. Первое произведение дает 2-3-7, второе дает 2 • 13, третье дает (3 или 4)-7 и 4 ¦ 9 и, наконец, четвертое дает 13.

19. Число га не может быть простым, так как в этом случае ifi(n) = га — 1. По предположению п не является квадратом простого числа. Если га не является произведением двух различных простых чисел, то оно должно быть произведением не менее трех простых (не обязательно различных) чисел. Пусть р — наименьший из сомножителей. Тогда р ^ га1'3, и <^(га) ^ га(1 — р-1 ) ^ га(1 — га-1/3) = п — га2/3, что противоречит условию.

20. Показать, что квадрат любого нечетного числа сравним с 1 по модулю 8, а затем воспользоваться индукцией, как это сделано в первой части доказательства предложения I. 3. 5.

21. а) Заметим, что 360 кратно функции <р(ра) для каждого pa||m. В соответствии с замечанием перед примером 3 в тексте это означает, что 6647362 = 66472 = 44182609 (mod тп). (Здесь мы используем тот факт, что НОД (6647, m) = 1, так как 6647 = 172 • 23.) б) Возведем а в степень 359 по модулю тп методом повторного возведения в квадрат. Так как m = (101100111)2, то нам понадобится 8 возведений в квадрат и 5 умножений (целых чисел, имеющих не более 63 двоичных разрядов). Каждая из этих операций сопровождается делением (в худшем случае 126-разрядного целого на 63-разрядное). Таким образом, число двоичных операций не превосходит 13 • 63 • 63 + 13 • 64 ¦ 63 = 104013.

22. а) Показать, что если х = j ¦ то х порождает Sj тогда и только тогда, когда НОД (x,d) = 1. Заметим, что j принимает значения 0,1,..., d— 1. б) Разобьем множество элементов Z/raZ на подмножества в соответствии с тем, какие множества Sj эти элементы порождают. Согласно п. а) подмножество, порождающее данное Sd, содержит ip(d) элементов.

23. а) Представим каждый член произведения в виде суммы геометрической прогрессии (1 + j + j\ + + ¦ ¦ ¦)- При перемножении таких скобок получаются все возможные дроби со знаменателями вида P11P^2 ...ргг- В силу основной теоремы арифметики каждое натуральное число га имеет единственное разложение такого вида. Следовательно, рассматриваемое произведение является суммой гармонического ряда YIn = I „і который, как известно, расходится, б) Сначала докажите, что х > — i- log (1 — х) при х ^ 1/2 (см. график логарифма). Примените это неравенство к х = 1/р и сравните ^TJ ~ с логарифмом произведения из пункта а), в) Для каждой последовательности простых чисел га, стремящейся к бесконечности, = і _ L _> і а для каждой последовательности чисел га, делящихся на все возрастающее число последовательных простых (например, для nj = }\), имеем ^ = ПрІпС1 - \) — Пвсе р(1 - = 0 на основании пункта а).

24. а) Сообщить і-му генерал-лейтенанту р,- и вычет числа TV по модулю р; и воспользоваться китайской теоремой об остатках, б) Выбрать каждое р,- большим, чем но значительно меньшим, чем

232

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

§1.4

3. Рассуждая так же, как при доказательстве последнего предложения, показать, что bd = ±1 (mod т). Но так как (bd)a/d = -1 (mod m), то bd = -1 (mod m) и a/d нечетно.

4. Использовать упражнение Зса = пис = (р — 1)/2.

5. a) 28 + 1 = 257. б) Воспользоваться упражнением 4. с) m = 97 • 257 • 673.

6. 2 • II2 • 13 ¦ 4561, 25 ¦ 5 • 7 ¦ 13 ¦ 41 -73-6481.

7. 24 ¦ З2 ¦ 7 • 13 • 31 • 601.

8. З2 ¦ 41 • 271, З3 • 7 ¦ 11 ¦ 13 ¦ 37, З2 • 11 • 73 • 101 ¦ 137.

9. 7 ¦ 23 • 89 • 599479; 72 • 127 ¦ 337 (этот пример показывает, что для простого p\(bd — 1) в предложении I. 4. 3 число 4" — 1 может делиться на р в большей степени, чем bd - 1).

10. 7 -31 ¦ 151, З2 • 7- 11 -31 • 151 -331, З2 •52 - 7- 11 • 13 -31 -41 -61 • 151 -331 • 1321.

11. а) Применить одновременно алгоритм Евклида для нахождения НОД (ат — 1, ап — 1) и НОД (т, п). Заметить, что на каждом шаге остаток в первом применении алгоритма Евклида имеет вид аТ — 1, где г — остаток во втором применении алгоритма Евклида. В частности, на первом шаге при делении ат — 1 на а" — 1 получается остаток аг — 1, где г — остаток от деления m на п. б) Согласно части а) и китайской теореме об остатках никакие два числа в промежутке от 0 до Д(2т' — 1) не могут иметь два одинаковых набора остатков. Это произведение больше, чем 2r'/2 > 22* > ab. При оценке времени получаем г умножений чисел, имеющих не более I цифр в двоичной записи. Это дает 0(rl2) = O(kl) двоичных операций, что в г раз лучше, чем дает обычное умножение а на 4, требующее 0(к2) операций.
Предыдущая << 1 .. 104 105 106 107 108 109 < 110 > 111 112 113 114 115 116 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed