Теоретико-численные методы в криптографии

Автор(ы)

Кнауб Л.В, Новиков Е.А, Шитов Ю.А

Год

2011

Издательство

Сибирский федеральный университет

Язык

rus

ISBN

978-5-7638-2113-7

Библиографическая ссылка

Красноярск : Сибирский федеральный университет, 2011. – 160 с.

Теги

Математика Программирование

Аннотация

Теоретико-численные методы в криптографии Год издания : 2011 Авторы : Кнауб Л.В., Новиков Е.А., Шитов Ю.А. Жанр или тематика : Учебное пособие Издательство : Красноярск: БИК Сибирского фед. ун-та ISBN : 978-5-7638-2113-7 Язык : Русский Формат : PDF Качество : Издательский макет или текст (eBook) Интерактивное оглавление : Да Количество страниц : 160 Тираж : 100 экз. Описание : Излагаются некоторые элементы теории чисел, отношения сравнимости, модулярная арифметика, степенные вычеты, первообразные корни, индексы, алгоритмы дискретного логарифмирования, китайская теорема об остатках, простые числа и проверка на простоту, разложение чисел на множители и арифметические операции над большими числами. В прил. 1 описаны основы теории групп, колец и полей, а в прил. 2 приведены реализации некоторых алгоритмов, даны тексты программ на языке Borland C++, снабженные подробными комментариями. Для студентов, обучающихся по специальности 090102 «Компьютерная безопасность» и направлениям подготовки 090900 «Информационная безопасность» и 010200 «Математика и компьютерные науки». Примеры страниц Оглавление Введение 3 Некоторые элементы теории чисел 4 Вычисление наибольшего общего делителя 9 Алгоритм Евклида 9 Бинарный алгоритм Евклида 9 Расширенный алгоритм Евклида 10 Вариант расширенного алгоритма Евклида 10 Отношение сравнимости 14 Свойства сравнений 14 Модулярная арифметика 16 Вычисление a ͯ mod n 16 Классы 17 Полная и приведенная система вычетов 18 Функция Эйлера 19 Сравнения первой степени 24 Криптография с открытым ключом 27 Криптосистема RSA 28 Формирование системы RSA 30 Алгоритм шифрования 30 Алгоритм дешифрования 30 Цифровая подпись 30 Степенные вычеты 35 Первообразные корни 46 Индексы 47 Алгоритмы дискретного логарифмирования 53 Задача дискретного логарифмирования в конечном поле 53 ρ-метод Полларда 53 Схема Эль–Гамаля 55 Схема Шнорра 56 Китайская теорема об остатках 59 Сравнения степеней выше первого 63 Сравнения по составному модулю 70 Двучленные сравнения 72 Сравнения второй степени по простому модулю и квадратичные вычеты 76 Алгоритм вычисления символа Якоби 84 Вычисление квадратных корней по модулю 88 Случай простого модуля 88 Случай составного модуля 91 Вычисление квадратных корней по составному модулю 96 Цифровая подпись Фиата–Шамира 98 Простые числа 100 Проверка на простоту 102 Пробное деление 102 Решето Эратосфена 102 Тест на основе малой теоремы Ферма 103 Схема алгоритма на базе малой теоремы Ферма 103 Тест Соловея–Штрассена 104 Схема алгоритма на базе малой теоремы Ферма 104 Тест Рабина–Миллера 104 Схема алгоритма Рабина–Миллера 105 Построение больших простых чисел и детерминированные алгоритмы проверки чисел на простоту 106 Проверка чисел Мерсенна на простоту 107 Разложение чисел на множители 108 Метод пробного деления 108 Факторизация Ферма 109 ρ-метод Полларда 111 (р–1)-метод Полларда 113 Арифметические операции над большими числами 116 Сложение 116 Вычитание 117 Умножение 117 Деление 118 Модифициров