Факторизацией натурального числа называется разложение этого числа в произведение простых сомножителей. Эта задача имеет большую вычислительную сложность. Один из самых популярных методов криптографии с открытым ключом, метод RSA, основан на трудоемкости задачи факторизации длинных целых чисел. Другими важными проблемами теории чисел, имеющими важные приложения на практике, являются проблемы проверки простоты целого числа и построения больших простых чисел.
В этой книге мы даем описание наиболее известных методов проверки простоты натуральных чисел и факторизации, включая самые быстрые на сегодняшний день метод эллиптических кривых Х. Ленстры, метод квадратичного решета К. Померанца и метод решета числового поля Д. Полларда.
Решето Эратосфена и критерии простоты.
Очевидно, что любое простое число, не равное 2, является нечетным. Существуют признаки делимости целых чисел на различные простые числа, например, чтобы число в десятичном виде делилось на 3 и 9 достаточно, чтобы сумма его цифр делилась на 3 и 9 соответственно. Чтобы число делилось на 5, достаточно, что его последняя цифра была 0 или 5.
Такие частные признаки делимости можно использовать, если нужно уменьшить множество кандидатов проверки на простоту или отсечь заведомо составные числа. Альтернативным способом получения простых чисел является решето Эратосфена, приписываемое древнегреческому ученому Эратосфену Киренскому, жившему примерно в 276 - 194 г. до н.э.
Для нахождения множества простых до заранее выбранной верхней границы B мы сначала выписываем последовательность всех нечетных чисел от 3 до 6 . Затем выбираем первое число в списке, т.е. тройку, и оставляя его в списке, вычеркиваем все кратные 3, начиная с 6. Потом переходим ко второму числу списка (пятерке) и вычеркиваем его кратные, оставив саму пятерку и т.д., пока не дойдем до конца списка. В оставшемся списке будут только простые числа.
Содержание.
Введение.
1. Простые числа.
2. Простые алгоритмы факторизации.
3. Эллиптические кривые и их приложения в криптографии.
4. Метод квадратичного решета.
5. Метод решета числового поля.
А. Приложение. Алгебраические числовые поля.
Список литературы.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Методы факторизации натуральных чисел, Ишмухаметов Ш.Т., 2011 - fileskachat.com, быстрое и бесплатное скачивание.
Скачать файл № 1 - pdf
Скачать файл № 2 - rtf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу
Скачать - pdf - Яндекс.Диск.
Скачать - rtf - Яндекс.Диск.
Дата публикации:
Теги: факторизация :: Ишмухаметов :: 2011
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
- Модели и алгоритмы для интеллектуальных систем управления, Богуславский А.А., Боровин Г.К., Карташев В.А., 2019
- Математическое моделирование электромагнитных и гравитационных явлений по методологии механики сплошной среды, Бычков В.Л., Зайцев Ф.С., 2019
- Как разгадать код да Винчи и еще 34 удивительных способа применения математики, Элвс Р., Пан А., 2016
- Комбинаторные задачи на графах, Ильев В.П., 2013
Предыдущие статьи:
- Начальный курс топологии в листочках, задачи и теоремы, Вербицкий М.С., 2017
- Алгебра, Толстых О.Д., Тунгалаг Д., 2016
- Задачи по теории вероятностей, Симушкин С.В., Пушкин Л.Н., 2011
- Задачи по стереометрии, Прасолов В.В., 2010