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

Название: Методы факторизации натуральных чисел
Автор: Ишмухаметов Ш.Т.
Жанр: Монография
Издательство: Казанский ун-т
Год выпуска: 2011
Страниц: 190
Язык: Русский
Формат: rtf, pdf
Размер: 26 Mb