Ишмухаметов Ш.Т. Методы факторизации натуральных чисел

Учебное пособие по криптографии и теории чисел. — Казань: КФУ, 2011. — 190 с. Факторизацией натурального числа называется разложение этого числа в произведение простых сомножителей. Эта задача имеет большую вычислительную сложность. Один из самых популярных методов криптографии с открытым ключом, метод RSA, основан на трудоемкости задачи факторизации длинных целых чисел. Другими важными проблемами
теории чисел, имеющими важные приложения на практике, являются проблемы проверки простоты целого числа и построения больших простых чисел.
В этом учебное побии дается описание наиболее известных методов проверки простоты натуральных чисел и факторизации, включая самые быстрые на сегодняшний день метод эллиптических кривых Х. Ленстры, метод квадратичного решета К. Померанца и метод решета числового поля Д. Полларда. Содержание
Введение
Простые числа
Простые алгоритмы факторизации
Эллиптические кривые и их приложения в криптографии
Метод квадратичного решета
Метод решета числового поля
Алгебраические числовые поля
Список литературы