Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
ЛИТЕРАТУРА к § 5 ГЛАВЫ IV
1. Bellare M., Micali S. Non-interactive oblivious transfer and applications. — In: Advances in Cryptology: Crypto'89. Heidelberg etc.: Springer, p. 547-557.
2. Ben-Or M., Goldreich 0., Goldwasser S., Hastad J., Kilian J., Micali S., Roga-way P. Everything provable is provable in zero-knowledge. — In: Advances in Cryptology: Crypto'88. Heidelberg etc.: Springer, 1990, p. 37-56.
3. Blum M., Feldman P., Micali S. Non-interactive zero-knowledge proofs and their applications. — In: Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988.
4. Chaum D., Evertse J.-H., van de Graaf J., Peralta R. Demonstrating possession of a discrete logarithm without revealing it. — In: Advances in Cryptology: Crypto'86. Heidelberg etc.: Springer, 1987, p. 200-212.
5. Garey M. R., Johnson D. S. Computers and intractability: A Guide to the Theory of NP-completeness. San-Francisco: W. H. Freeman, 1979. (Русск. ne-рев. — ГэриМ., Джонсом Д. С. Вычислительные машины и труднорешаемые задачи. M.: Мир, 1982.)
6. Goldwasser S., Micali S., Rackoff С. The knowledge complexity of interactive proof systems. — SIAM J. Comput., 1989, v. 18, p. 186-208.
7. Kilian J. Founding cryptography on oblivious transfer. — In: Proceedings of the 20th ACM Symposium on the Theory of Computing, 1988, p. 20--31.
8. Rabin M. How to exchange secrets by obvilious transfer. — Techn. Report TR-81. Aiken Computation Laboratory, Harvard University, 1981.
9. Shamir A. The search for provably secure identification schemes. — In: Proceedings of the International Congress of Mathematicians, 1986, p. 1488-1495.
ГЛАВА V
ПРОСТОТА И ФАКТОРИЗАЦИЯ
Во многих случаях требуется выяснить, является ли большое число п простым. Например, в системе открытого ключа RSA и различных системах, основанных на задаче дискретного логарифмирования в конечных полях, нам нужно найти большое «случайное» простое число. Один из подходов к этому заключается в том, чтобы выбрать большое нечетное целое число По, используя генератор случайных чисел, и затем проверять Ti0, Ti0 +2,... на простоту до тех пор, пока мы не найдем первое простое число, большее или равное п0. Другой тип использования тестов на простоту — выяснение того, является ли некоторое число весьма специального типа простым. Например, нас может интересовать, является ли число 2^ — 1 для данного большого числа / простым числом Мерсенна: в поле из 2^ элементов, как мы видели (см. упражнение 13 а) к §11.1) все элементы, отличные от 0 и 1, являются образующими F2/ в том и только том случае, когда 2^ — 1 есть простое число.
Тест на простоту представляет собой критерий того, что число п не является простым. Если п «проходит» этот тест, ТО ОНО, возможно, простое число. Если оно «проходит» целый набор тестов на простоту, то весьма вероятно, что оно действительно является простым. С другой стороны, если п не проходит хотя бы одного теста на простоту, то оно совершенно определенно является составным. Однако при этом остается нерешенной трудная задача нахождения простых делителей числа п (задача факторизации). В общем случае для разложения на множители большого числа, о котором известно, что оно составное (поскольку оно не прошло теста на простоту), требуется гораздо больше времени, чем для нахождения простого числа того же порядка величины. (Это — эмпирическое утверждение, а не теорема; ни одного утверждения такого рода не доказано). Надежность криптосистемы RSA основывается на том предположении, что значительно
140
ГЛ. V. ПРОСТОТА И ФАКТОРИЗАЦИЯ
легче найти два чрезвычайно больших простых числа ряд, чем, зная п = pq, но не р или q, найти делители числа п. После рассмотрения тестов на простоту в § 1 мы опишем три различных метода факторизации в §§ 2-5.
§ 1. Псевдопростые числа
Замечали ли вы, что не делается попыток найти большие числа, которые не являются простыми? Было бы вам интересно услышать в выпуске новостей сообщение о том, что «Сегодня Отдел вычислительных наук в Вашингтонском университете объявил,
„58,111,625,031 ,0 гл г-
что 2 + в — четное число. Это — самое большое не
простое число, известное ныне»
— надпись в душевой комнате Вашингтонского университета.
«Явление, вероятность которого Ю-50, так никогда бы и не проявилось, или, во всяком случае, никогда бы не было замечено»
— Э. Борель Вероятность и жизнь.
Пусть п — большое нечетное число, и мы хотим определить, является ли п простым. Простейший тест на простоту — «пробы делением». Это значит, что вы берете нечетное целое число т и проверяете, делится ли п на т. Если m ф 1, тп ф п и тп\п, то п — составное; в противном случае п проходит тест на простоту «деление на тп». Если по мере того, как тп пробегает одно за другим нечетные числа, начиная с 3, число п проходит все пробы делением, то становится все более и более вероятным, что п — простое число. Мы полностью убедимся в простоте п, если тп достигнет значения ,/п. Конечно, это чрезвычайно неэффективный способ проверки простоты числа п. Другие тесты, описанные в этом параграфе, значительно быстрее.
