Коблиц Н. Курс теории чисел и криптографии. - М.: Научное изд-во ТВП, 2001,- 254 с.
Цель данной книги — ввести читателя в те области арифметики, как классические, так и самые современные, которые находятся в центре внимания приложений теории чисел, особенно криптографии. Предполагается, что знание высшей алгебры и теории чисел ограничено самым скромным знакомством с их основами; по этой причине излагаются также необходимые сведения из этих областей математики. Авторами избран алгоритмический подход, причем особое внимание уделяется оценкам эффективности методов, предлагаемых теорией. Особенностью книги является изложение совсем недавно разработанных приложений теории эллиптических кривых. Перевод на русский язык осуществлен с оригинала второго издания, существенно пересмотренного по сравнению с первым изданием и снабженного обновленным списком литературы. Каждая глава включает в себя тщательно составленную подборку задач, как правило, снабженных подробными указаниями и решениями.
Все это позволяет рекомендовать книгу не только в качестве ценного пособия для общетеоретической подготовки специалистов по защите информации, но и как полезный источник примеров практической применимости целого ряда абстрактных разделов математики и кибернетики. Книга прекрасно подходит и для самообразования.
СОДЕРЖАНИЕ
Предисловие V
Предисловие ко второму изданию vii
Глава I. Некоторые вопросы элементарной теории чисел 1
§ 1. Временные оценки сложности арифметических операций 1
§ 2. Делимость и алгоритм Евклида 13
§ 3. Сравнения 20
§ 4. Некоторые применения к разложению на множители 30
Глава II. Конечные поля и квадратичные вычеты 34
§ 1. Конечные ПОЛЯ 36
§ 2. Квадратичные вычеты и закон взаимности 47
Глава III. Криптография 61
§ 1. Некоторые простые криптосистемы 61
§ 2. Шифрующие матрицы 73
Глава IV. Открытый ключ 91
§ 1. Суть криптографии с открытым ключом 91
§ 2. Криптосистема RSA 101
§ 3. Дискретное логарифмирование 107
§ 4. Задача о рюкзаке 123
§ 5. Протоколы с нулевым разглашением и скрытая передача 130
Глава V. Простота и факторизация 139
§ 1. Псевдопростые числа 140
§ 2. Ро-метод 155
§ 3. Факторизация Ферма и факторные базы 160
§ 4. Метод цепных дробей 174
§ 5. Метод квадратичного решета 180
Глава VI. Эллиптические кривые 188
§ 1. Основные факты 188
§ 2. Криптосистемы на эллиптических кривых 200
§ 3. Критерий простоты, использующий эллиптические кривые 212
§ 4. Разложение на множители при помощи эллиптических кривых 217
Ответы к упражнениям 227
Предметный указатель 255
