М.: МЦНМО, 2002. 104.
Пособие представляет собой краткое введение в область современной вычислительной теории чисел и ее приложений к криптографическим задачам.
Предназначено для студентов вузов, обучающихся по информационной безопасности, и всех желающих получить первоначальное представление о предмете. Содержание:
Оценка сложности арифметических операций.
Свойство функций оценки сложности.
Сложность арифметических операций с целыми числами.
Сложность алгоритма Евклида.
Сложность операций в кольце вычетв.
Использование модульной арифметики.
Вычисление с многочленами.
Дискретное преобразование Фурье.
Элементы теории чисел.
Непрерывные дроби и их свойства.
Квадратичные вычеты.
Теорема Чебышева о распределении простых чисел.
Арифметические алгоритмы.
Проверка простоты.
Решето Эратосфена.
Критерий Вильсона.
Тест на основе малой теоремы Ферма.
Свойства чисел Кармайкла.
Тест Соловея-Штрассена.
Тест Рабина-Миллера.
Полиномиальный тест распознавания простоты.
Построение больших простых чисел.
Критерий Люка.
Теорема Поклингтона.
Теорема Диемитко.
Метод Маурера.
Метод Михалеску.
(n+1)-методы.
Числа Мерсенна.
Алгоритмы факторизации целых чисел.
Метод Полларда.
Алгоритм Полларда-Штрассена.
Факторизация Ферма.
Алгоритм Диксона.
Алгоритм Брилхарта-Моррисона.
Метод квадратичного решета.
(p-1)-метод факторизации Полларда.
Криптографическая система RSA.
Выбор параметров системы RSA.
Взаимосвязь между параметрами системы RSA.
Условия на выбор чисел p и q.
Выбор параметров e и d.
Пособие представляет собой краткое введение в область современной вычислительной теории чисел и ее приложений к криптографическим задачам.
Предназначено для студентов вузов, обучающихся по информационной безопасности, и всех желающих получить первоначальное представление о предмете. Содержание:
Оценка сложности арифметических операций.
Свойство функций оценки сложности.
Сложность арифметических операций с целыми числами.
Сложность алгоритма Евклида.
Сложность операций в кольце вычетв.
Использование модульной арифметики.
Вычисление с многочленами.
Дискретное преобразование Фурье.
Элементы теории чисел.
Непрерывные дроби и их свойства.
Квадратичные вычеты.
Теорема Чебышева о распределении простых чисел.
Арифметические алгоритмы.
Проверка простоты.
Решето Эратосфена.
Критерий Вильсона.
Тест на основе малой теоремы Ферма.
Свойства чисел Кармайкла.
Тест Соловея-Штрассена.
Тест Рабина-Миллера.
Полиномиальный тест распознавания простоты.
Построение больших простых чисел.
Критерий Люка.
Теорема Поклингтона.
Теорема Диемитко.
Метод Маурера.
Метод Михалеску.
(n+1)-методы.
Числа Мерсенна.
Алгоритмы факторизации целых чисел.
Метод Полларда.
Алгоритм Полларда-Штрассена.
Факторизация Ферма.
Алгоритм Диксона.
Алгоритм Брилхарта-Моррисона.
Метод квадратичного решета.
(p-1)-метод факторизации Полларда.
Криптографическая система RSA.
Выбор параметров системы RSA.
Взаимосвязь между параметрами системы RSA.
Условия на выбор чисел p и q.
Выбор параметров e и d.