Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
18. а) Используя обозначение О-большое, оценить число двоичных операций в ситуации, когда тест Миллера-Рабина применяется столько раз, что вероятность прохождения составного числа п через эти тесты меньше 1/ш (пит очень велики).
б) Предполагая справедливой обобщенную гипотезу Римана, оценить число двоичных операций в ситуации, когда тест Миллера-Рабина применяется столько раз, сколько необходимо для достаточной уверенности в том, что прошедшее все тесты число п является простым.
19. а) Доказать, что если п — псевдопростое по основанию 2, то TV = 2" — 1 является сильно псевдопростым и эйлеровым псевдопростым по основанию 2.
б) Доказать, что существует бесконечно много сильно псевдопростых и эйлеровых псевдопростых по основанию 2.
20. Доказать, что если п — сильно псевдопростое по основанию 6, то оно сильно псевдопростое также по основанию Ьк для любого целого к.
21. Пусть п — число Кармайкла 561.
а) Найти число оснований 6 Є (Z/561Z)*, для которых 561 — эйлерово псевдопростое.
б) Найти число оснований, для которых 561 — сильно псевдопростое. Привести их список.
22. Доказать, что если п = р" есть степень простого числа, где а > 1, то п — сильно псевдопростое по основанию Ь тогда и только тогда, когда оно — псевдопростое по основанию Ь.
154
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
23. а) Показать, что 65 — сильно псевдопростое число по основанию 8 и по основанию 18, однако не является таковым по основанию 14 = 8 • 18 (mod 65).
б) Для любого нечетного составного числа п пусть (*) обозначает утверждение: если п — сильно псевдопростое по основанию 6i и по основанию 62, то оно — сильно псевдопростое по основанию 61O2 (другими словами, свойство сильной простоты сохраняется при перемножении оснований). Доказать, что (*) справедливо тогда и только тогда, когда п — либо степень простого числа, либо делится на простое число, сравнимое с 3 по модулю 4.
24. а) Доказать, что если найдется такое Ь, что п — псевдопростое число по основанию 6. но не является сильно псевдопростым по Ь, то можно быстро найти нетривиальный делитель числа п.
б) Объяснить, как можно защититься от этого при выборе п = pq в криптосистеме RSA.
Замечание. Во многих тестах на простоту оказывается, что если составное п проходит начальный тест, но не проходит какого-либо из последующих, полученная информация не только доказывает, что п — составное число, но и позволяет легко найти его нетривиальный множитель. Упражнение 24 — тому пример: если п проходит тест на псевдопростоту по основанию 6, а затем не проходит тест на сильную псевдопростоту по основанию 6, то можно найти делитель п. Однако это не означает, что тесты на простоту можно использовать в задаче факторизации. Если п — большое составное число (например, произведение больших случайно выбранных простых чисел р и q), то очень маловероятно, что мы найдем основание 6, по которому п — псевдопростое (упражнение 5 а) дает представление о вероятности выбора такого Ь). Таким образом, различные изощренные тесты на псевдопростоту позволяют лишь подтвердить простоту действительно простого числа. На практике составное число, которое мы хотим разложить на множители, не будет проходить любой отдельный тест на простоту, но сами тесты не помогут нам найти его множители. х
ЛИТЕРАТУРА к § 1 ГЛАВЫ V
1. Adleman L. M., Ротегапсе С, Rumely R. S. On distinguishing prime numbers from composite numbers. — Ann. Math., 1983, v. 117, p. 173-206.
2. Cohen Я., Lenstra H. W., Jr. Primality testing and Jacobi sums. — Math. Сотр., 1984, v. 42, p. 297-330.
3. Dixon J. D. Factorization and primality tests. — Amer. Math. Monthly, 1984, v. 91, p. 333-352.
4. Kranakis E. Primality and Cryptography. N.Y. etc.: Wiley, 1986.
5. Lenstra A. Primality testing. — Crypt. Comput. Number Theory, Proc. Symp. Appl. Math., 1990, v. 42, p. 13-25.
6. Miller G. L. Riemann's hypothesis and test for primality. — In: Proceedings of the 7th Annual ACM Symposium on the Theory of Computing, p. 234-239.
7. Ротегапсе С. Recent developments in primality testing. — Math. Intelligencer, 1981, v. 3, p. 97-105.
8. Ротегапсе С. The search for prime numbers. — Sei. American, 1982, v. 247, p. 136-147.
9. Rabin M. O. Probabilistic algorithms for testing primality. — J. Number Theory, 1980, v. 12, p. 128-138.
§ 2. po-метод
155
10. Solovay R., Strassen V. A fast Monte Carlo test for primality. — SIAM J. Comput., 1977, v. 6, p. 84-85; erratum: 1978, v. 7, p. 118.
11. Wagon S. Primality testing. — Math. Intelligencer, 1986, v. 8, № 3, p. 58-61.
§ 2. Po-метод
Предположим, что нам известно, что некоторое большое нечетное число п составное. Например, оно не прошло один из тестов на простоту из § 1. Как уже упоминалось, это не значит, что мы имеем какое-либо представление о его делителях. Из рассмотренных нами методов проверки простоты лишь самый медленный — последовательное деление п на простые числа, меньшие у/п, — одновременно с установлением непростоты конкретно указывает делитель числа п. Все более быстрые алгоритмы проверки простоты лишь устанавливают факт существования делителей числа п, но не дают о них информации.
