Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
20. Пусть т = р"1 ¦¦•ртг — разложение на простые множители целого нечетного числа т. Предположим, что а — целое число, взаимно простое с т и являющееся квадратом по модулю т. Ваша цель — найти такое целое х, что X2 = a (mod m). Предположим, что для каждого j мы знаем некоторый невычет по модулю pj, т.е. такое целое и;-, что (-^1:) = ~ 1-
а) Для каждого j = 1, . . . , г фиксируем р = Pj и a = otj. Предположим, что, пользуясь методом § П.2, мы нашли такое хо, что х2 = a (mod р). Показать, как можно найти такое х = хо + х\р + хчр2 + ¦ • • + xa-\pa~l, что х2 = a (mod ра).
б) Описать, как найти затем такое х, что х2 = a (mod m). Метод, описанный в этом упражнении, называется «подъемом» квадратного корня от ТР} (1 ^ j ^ г) до Z/mZ.
21. Выше мы видели, что если п — нечетное простое число, и НОД (6, и) = 1,
то
6(n-l)/2 = ^ (mod п) W
Цель этого упражнения — показать, что если п — нечетное составное число, то соотношение (*) не выполняется не менее чем для 50% таких 6, что НОД (6, и) = 1.
а) Доказать, что если соотношение (*) выполняется для Ъ\ и не выполняется для 62, то оно не выполняется для Ь\Ъ2- Используя это, показать, что если (*) не выполняется хотя бы для одного 6, то число элементов 6, для которых (*) не выполняется, не меньше числа элементов, для которых оно справедливо.
б) Пусть п делится на квадрат простого числа р. Показать, как найти такое целое число Ь, взаимно простое с п, что 6^"-1^2 ^ ±1 (mod и).
в) Пусть п — произведение различных простых чисел и р — одно из них, а 6 удовлетворяет условиям: (^) = —1 и b = 1 (mod n/p). Доказать, что для b соотношение (*) не выполняется. Показать, что такое 6 всегда существует.
22. Объяснить, почему следующий вероятностный алгоритм дает квадратный корень из а по модулю р. Выбираем ( Є Fp случайно до тех пор, пока не окажется,
60
ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ
что t2 — а является невычетом по модулю р. Пусть a = y/t2 - а обозначает элемент в квадратичном расширении Fp2. Затем вычисляем 6 = (i + а)(р + 0/2_ Показать, что 6 Є Fp и что Ь2 = а.
23. Предположим, что р — простое число, р = 1 (mod 4) и известен квадратичный невычет п по модулю р. Описать алгоритм, дающий представление р = с2 + d2 и имеющий временную оценку 0(log3p).
ЛИТЕРАТУРА к ГЛАВЕ II
1. Adleman L., Manders К., Miller G. On taking roots in finite fields. — In: Proceedings of the 20th Annual Symposium on the Foundations of Computer Science, 1979, p. 175-178.
2. Berlekamp E. R. Factoring polynomials over large finite fields. — Math. Сотр., 1970, v. 24, p. 713-735.
3. Blake I., Gao X., Menezes .4., Mullen R., Vanstone S., Yaghoobian T. Applications of Finite Fields. Dordrecht etc.: Kluwer Acad. Publ., 1992.
4. Gauss C. F. Disquisitiones Arithmeticae. London-New Haven: Yale Univ. Press, 1966.
5. Grosswald E. Topics from the Theory of Numbers. 2nd ed. Basel: Birkhauser, 1984.
6. Herstein I. N. Topics in Algebra. 2nd ed. N.Y.-Chichester: Wiley, 1975.
7. Ireland K., Rosen M. I. A Classical Introduction to Modern Number Theory. 2nd ed. Heidelberg etc.: Springer, 1990.
8. Лене С. Алгебра. M.: Мир, 1968.
9. Лидл Р., Нидеррайтер Г. Конечные поля. M.: Мир, 1988.
10. Pless V. Introduction to the Theory of Error-Correcting Codes. N.Y.-Chichester: Wiley, 1982.
11. Shanks D. Solved and Unsolved Problems in Number Theory. 3rd ed. N.Y.: Chelsea Publ. Co., 1985.
12*. Виноградов U.M. Основы теории чисел. M.: Наука, 1972.
13*. Боревич 3. Я., Шафаревич И. Р. Теория чисел. M.: Наука, 1985.
* Добавлено при переводе. — Прим. ред.
ГЛАВА III
КРИПТОГРАФИЯ § 1. Некоторые простые криптосистемы
Основные обозначения. Криптография изучает методы пересылки сообщений в замаскированном виде, при которых только намеченные отправителем получатели могут удалить маскировку и прочитать сообщение. Предназначенное для пересылки сообщение называется открытым текстом, а замаскированное сообщение — шифрованным текстом или кратко шифртекстом. Открытый текст и шифртекст записываются в некоторых алфавитах; обычно, но не всегда, эти алфавиты совпадают и состоят из некоторого числа N букв. Термин «буква» (или «символ») может относится не только к обычным буквам, но также к цифрам, к пробелам, к знакам пунктуации и ко всяким другим символам, используемым при записи сообщения. (Если мы не включим, например, пробелы, то все слова слипнутся и сообщение будет трудно читать.) Процесс преобразования открытого текста в шифртекст называется шифрованием (или зашифрованием), а обратная процедура называется дешифрованием (или расшифрованием).
Открытый и шифрованный тексты разбиваются на элементарные сообщения («элементы»). Элементом может быть отдельная буква, пара букв (биграмма), тройка букв (триграмма) или даже блок из 50 букв. Шифрующее преобразование является функцией, которая преобразует элемент открытого текста в элемент шифртекста. Другими словами, это — отображение / из множества V всех возможных элементов открытого текста в множество С всех возможных элементов шифртекста. Будем всегда предполагать, что это отображение взаимно однозначное, т. е. для одного элемента шифртекста существует один и только один элемент открытого текста, из которого элемент шифртекста получается при шифровании.- Дешифрующее преобразование действует в обратном направлении, это — функция / , вое-
