РЕШАЕМ МАТЕМАТИКУ ВМЕСТЕ!
 
СТУДЕНТАМ:    Учебники     Решебники    Шпаргалки    Контрольные работы   Видео уроки

ШКОЛЬНИКАМ:  ГДЗ - 1 класс  2 класс  3 класс  4 класс  5 класс  6 класс  7 класс  8 класс  9 класс  10 класс  11 класс

Главная » Файлы » Учебные материалы » Теория чисел
Маховенко Е. Б. Теоретико-числовые методы в криптографии: Учебное пособие / Е. Б. Маховенко.

25.01.2012, 16:30
В учебном пособии излагаются методы решения алгебраических и теоретико-числовых задач, возникающих при разработке и исследовании криптографических методов и средств защиты информации. Изучаются алгоритмы арифметики больших целых чисел и полиномов, проверки чисел на простоту и разложения на множители. Исследуется безопасность криптосистем Я8А, Диффи-Хеллмана, ранцевых криптосистем. 
Приведены примеры практических заданий по реализации ряда алгоритмов. 
Для студентов, обучающихся по специальности «Компьютерная безопасность».

ОГЛАВЛЕНИЕ

Введение 3

Глава 1. Делимость в кольце целых чисел 5
1.1. Делимость в кольце целых чисел 7
1.2. Наибольший общий делитель и наименьшее общее кратное 11
1.3. Вычисление наибольшего общего делителя 16
1.3.1. Алгоритм Евклида 16
1.3.2. Бинарный алгоритм Евклида 20
1.3.3. Расширенный алгоритм Евклида 22
1.4. Простые числа 27
1.4.1. Свойства простых чисел 27
1.4.2. Распределение простых чисел 30
Упражнения к главе 1 32
Литература к главе 1 33

Глава 2. Сравнения с одним неизвестным 34
2.1. Отношение сравнимости 34
2.2. Решение сравнений 40
2.2.1. Сравнение первой степени 41
2.2.2. Китайская теорема об остатках 45 
2.2.3. Сравнение произвольной степени по простому модулю 48
2.3. Сравнения второй степени 50
2.3.1. Символы Лежандра и Якоби 50
2.3.2. Случаи простого модуля 62
2.3.3. Случаи составного модуля 67
Упражнения к главе 2 79
Литература к главе 2 81

Глава 3. Основы теории непрерывных дробей 82
3.1. Определение непрерывной дроби 82
3.2. Подходящие дроби 86
3.3. Квадратичные иррациональности 99
3.4. Использование непрерывных дробей для решения задач 103
3.4.1. Простейшие диофантовы уравнения и сравнения первой степени 104
3.4.2. Уравнение Пелля 105
3.4.3. Представление числа в виде суммы квадратов 111
3.5. Разложение функции в непрерывные дроби 113
Упражнения к главе 3 116
Литература к главе 3 117

Глава 4. Арифметические операции над целыми числами и полиномами 118
4.1. Сложение и вычитание 118
4.2. Умножение 121
4.2.1. Умножение в «столбик». Возведение в квадрат 121
4.2.2. Умножение в метод Карацубы-Офмана 124
4.2.3. Умножение в классах вычетов 125
4.3. Умножение с помощью быстрого преобразования Фурье 130
4.3.1. Дискретное преобразование Фурье 130
4.3.2. Алгоритм быстрого преобразования Фурье 140
4.3.3. Алгоритм Шенхаге-Штрассена для умножения целых чисел 146
4.4. Модульное умножение 150
4.4.1. Метод Монтгомери 150
4.4.2. Модульное возведение в степень 154
4.5. Целочисленное деление с остатком 157
4.5.1. Схема Горнера 158
4.5.2. Деление на 2m-c 160
4.5.3. Общий случай 161
Упражнения к главе 4 166
Литература к главе 4 167

Глава 5. Проверка чисел на простоту 169
5.1. Вероятностные алгоритмы проверки чисел на простоту 169
5.1.1. Тест Ферма 171
5.1.2. Тест Соловэя-Штрассена 179
5.1.3. Тест Миллера-Рабина 183
5.1.4. Генерация простого числа 192
5.2. Детерминированные алгоритмы проверки чисел на простоту 193
5.2.1. Проверка чисел Мерсенна 194
5.2.2. Проверка с использованием разложения числа n-1 200
Упражнения к главе 5 203
Литература к главе 5 205

Глава 6. Разложение чисел на множители и криптосистема RSA 207
6.1. Метод пробного деления 207
6.2. p-Метод Полларда 209
6.3. (p-1)-Метод Полларда 213
6.4. Метод квадратов 216
6.4.1. Метод непрерывных дробей 219
6.4.2. Метод квадратичного решета 222
6.5. Криптографическая система RSA 225
6.5.1. Принцип действия 226
6.5.2. Безопасность криптосистемы RSA и задача разложения на множители 227
6.5.3. Безопасность криптосистемы RSA, не требующие разложения 229
Упражнения к главе 6 236
Литература к главе 6 237

Глава 7. Дискретное логарифмирование в конечном поле 239
7.1. Задача дискретного логарифмирования в конечном поле 239
7.1.1. p-Метод Полларда 240
7.1.2. Методы Гельфонда и Сильвера-Полига-Хеллмана 242
7.1.3. Метод встречи посередине 246
7.1.4. Методы базы разложения 247
7.2. Протокол Диффи-Хеллмана 249
Упражнения к главе 7 253
Литература к главе 7 254

Глава 4. Элементы теории решеток 256
8.1. Процесс ортогонализации Грама-Шмидта 256
8.2. Алгоритм Ленстры-Ленстры-Ленстры-Ловаша и его применение 259
8.3. Задача об укладке ранца 273
8.3.1. Способы решения 274
8.3.2. Ранцевые алгоритмы шифрования с открытым ключом 278
Упражнения к главе 8 283
Литература к главе 8 284

Приложение 286
Лабораторная работа 1. Вычисление наибольшего общего делителя 287
Лабораторная работа 2. Вероятностные алгоритмы проверки чисел на простоту 290
Лабораторная работа 3. Разложение чисел на множители 296
Лабораторная работа 4. Дискретное логарифмирование в конечном поле 299
Лабораторная работа 5. Алгоритм Ленстры-Ленстры-Ловаша и его применение 303
Ответы и указания к упражнениям 308




Размер файла: (2.84Mb)

Категория: Теория чисел | Добавил: ZeXeDeR | Теги: теория чисел, математика
Просмотров: 4447 | Загрузок: 1295 | Рейтинг: 5.0/2


Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]



ВЫБОР ПО КАТЕГОРИЯМ:

Аналитическая геометрия и алгебра [0]
Высшая алгебра [52]
История математики [55]
Математика для технарей [21]
Математика для экономистов, юристов и т.д.. [5]
Математическая логика и теория алгоритмов [40]
Теория вероятностей и мат. статистика [28]
Теория чисел [33]
Учебники по математике [46]



При полном или частичном использовании материалов
активная ссылка на портал VMATE.RU обязательна


Высшая математика онлайн - всё бесплатно, наш портал создан специально для студентов кому интересна высшая математика. У нас на портале возможно скачать бесплатно учебники по высшей математике, книги по математике или сделать заказ учебных пособий, скачать контрольные по высшей математике, заказать, задачники по высшей математики и решебники. Оставить запрос по предмету - аналитическая геометрия или задать вопрос - справочная по математике Заказать решение и т.д. Высшая математика онлайн - математический портал и здесь собраны шпаргалки по высшей математике и видео уроки. Добро пожаловать! Вход