Курс теории чисел и криптографии - Коблиц Н.
Скачать (прямая ссылка):
Эта книга посвящена памяти студентов Вьетнама, Никарагуа и Сальвадора, отдавших свои жизни в борьбе против американской агрессии. Авторский гонорар от продажи книги будет использован на покупку научной литературы для университетов и институтов этих трех стран.
\
Глава VI
Сиэтл, май 1987 года
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
Вместе с возникновением в криптографии новых понятий и методов расширился и круг криптографических приложений теории чисел. В дополнение к элементарной и аналитической теории чисел все более широко используется алгебраическая теория чисел (тесты на простоту с применением сумм Гаусса и Якоби, криптосистемы, основанные на квадратичных полях, решето числового поля) и арифметическая алгебраическая геометрия (факторизация при помощи эллиптических кривых, криптосистемы, основанные на эллиптических и гиперэллиптических кривых и абелевых многообразиях). Некоторые из современных применений теории чисел в криптографии (наиболее значительное из них — способ разложения больших целых чисел на множители применением метода решета числового поля, разработанный после выхода первого издания) остались за пределами книги. Однако за счет небольшого увеличения объема книги удалось включить в нее некоторые новые темы, что позволило более полно отразить разнообразие применений теории чисел в этой увлекательной междисциплинарной области.
Следующий список суммирует основные изменения во втором издании.
— Внесены исправления и разъяснения, добавлены многочисленные ссылки.
— В главу VI добавлен раздел о доказательствах с нулевым разглашением и скрытой передаче.
— В главу V добавлен раздел о разложении на множители методом квадратичного решета.
— В главу VI включен раздел об использовании эллиптических кривых в тестах на простоту.
— Добавлено беглое обсуждение следующих вопросов: (п,/^-пороговые схемы, вероятностное шифрование, хеш-функции, рюкзачная криптосистема Чора-Райвеста и американский стандарт цифровой подписи DSS.
Сиэтл, май 1994 года
ГЛАВА I
НЕКОТОРЫЕ ВОПРОСЫ ЭЛЕМЕНТАРНОЙ ТЕОРИИ ЧИСЕЛ
Большинство понятий, рассматриваемых в настоящей главе, вероятно, хорошо известно читателям. Цель этой главы — напомнить те обозначения и факты из элементарной теории чисел, которые будут необходимы при работе с этой книгой. Большинство доказательств опускается, поскольку их можно найти почти в каждом учебнике по теории чисел. Одна тема, которая будет играть центральную роль далее, — оценивание числа двоичных операций, необходимых для решения различных теоретико-числовых задач на компьютере, — еще не вошла в стандартные курсы по элементарной теории чисел. Поэтому мы будем более детально рассматривать вопросы, связанные с оценками сложности, особенно в § 1.
§ 1. Временные оценки сложности арифметических операций
Числа в разных базах. Разложение неотрицательного целого числа п по основанию (базе) Ь представляет собой обозначение для п вида (dk_idk_2 . ¦ ¦ did())b, где d^ — цифры, т. е. символы целых чисел
к —1 к —2
от 0 до 6—1. Эта запись означает, что п = dk_ib +t4_26 +••¦ + dxb 4- d0. Если цифра первого разряда отлична от нуля, то число п
к — 1
называют /с-разрядным 6-ичным числом. Любое целое число от Ь
к
до 6 - 1 является /с-разрядным по основанию Ь. Мы будем опускать скобки и индекс (...)(, в случае десятичной системы счисления (6 = 10) и в тех случаях, когда основание системы счисления ясно из контекста, особенно в случае двоичной системы (6 = 2). Поскольку иногда удобно пользоваться системами, отличными от десятичной, приходится производить арифметические операции по произвольному основанию и переходить от одного основания к другому. Продемонстрируем это
2
ГЛ. I. ЭЛЕМЕНТАРНАЯ ТЕОРИЯ ЧИСЕЛ
на нескольких примерах.
Замечания. 1) Дробные числа также можно разлагать по любому основанию, т. е. представлять в виде
{dk-idk-2 ¦ ¦ ¦ did0, d_]d_2 . ¦ -)ь-
2) При b > 10 принято использовать буквы для выражения цифр, больших девяти. Можно вообще использовать буквы вместо цифр. Пример 1. a) (HOOlOOl)2 = 201.
Ь) При b = 26 будем использовать буквы латинского алфавита A-Z для записи цифр 0-25 соответственно. Тогда (BAD)26 = 679, тогда как (B5AD)26 = IgI6-.
Пример 2. Умножить 160 на 199 в системе счисления по основанию 7.
Решение:
316
403 1254 16030 161554
Пример 3. Разделить (HOOlOOl)2 на (10011I)2 и (HAPPY)26 на (SAD)26.
Решение:
11001001 1100111 HAPPY \SAD_
100111 101 GYBE KD
101101 COLY
100111 CCAJ
ПО (ост) MLP (ост)
Пример 4. Выразить 106 в системах счисления по основаниям 2, 7 и 26 (в последнем случае использовать буквенную запись).
Решение. Чтобы разложить число п по основанию 6, надо сначала получить младший разряд, разделив п на 6 и взяв остаток от деления. Потом п заменяется частным от деления, описанный процесс повторяется и дает второй от конца знак разложения и т. д. В данном случае получаем
106 = (1111010000100100000O)2 = (1133331I)7 = (CEXHO)26-
Пример 5. Выразить тг = 3,1415926... в двоичной системе счисления (выписывая 15 цифр после запятой) и по основанию 26 (выписывая 3 цифры после запятой).
