Введение 2
Постановка задачи 4
Глава 1. Анализ 5
Выбор кривой в зависимости от простоты числа 22
Метод нахождения подсемейства с большим рангом 23
Построение индивидуальных кривых с кручением Z/4Z ф Z/8Z 24
Глава 2. Реализация и экспериментальные оценки 25
Заключение 28
Листинг 29
Купить

Факторизация целого числа - это процедура разложения этого числа в произведение простых сомножителей. Факторизация является сложной вычислительной задачей, требующей значительных вычислительных ресурсов. На сложности решения этой задачи построен известный метод шифрования в криптографии - метод RSA.
Самый быстрый метод факторизации больших чисел - это решета числового поля(НБЗ), изобретенный Поллардом в 1991 году. С тех пор он был существенно усовершенствован (была создана “специальная” форма, которая используется только для факторизации числа, близкого к идеальной степени, таких как числа Ферма).
С помощью решета числового поля в алгоритме RSA были успешно разложены числа 663 бита Бахром, Франком в 2005 году. Время, необходимое для реализации факторизации b-битного RSA модуля, обеспечивает верхнюю границу безопасности b-битного RSA.
Для того чтобы факторизовать большое число N NFS требует разложения большого числа целых чисел средних размеров, созданных во время выполнения, возможно размером 200 бит. Такие цифры могут постоянно корректироваться за небольшое количество времени. Даже небольшие улучшения сделают значительную разницу в том, насколько большое число мы можем факторизовать.
Метод факторизации эллиптических кривых (ECM) (который является основным предметом этой работы) является субэкпоненциальным алгоритмом. Это означает, что асимптотически он работает быстрее, чем все другие известные методы (кроме квадратичного решета и решета числового поля). Кроме того, его сложность определяется размером наименьшего делителя, а не размером факторизуемого числа, поэтому он может находить делители у огромных чисел специального вида. ECM является лучшим методом для выполнения факторизации целых чисел в 200-битном диапазоне с простыми множителями примерно до 40 бит.
Данная работа посвящена изучению задачи определения сходимости метода в случае одновременной работы нескольких кривых. Эта задача связана с распределением гладких чисел.
Решение этой проблемы связано с изучение распределения гладких чисел, что является известной научной проблемой, а также и разработкой модели применения этой теории к методу Ленстры.
Постановка задачи
Изучить и реализовать алгоритм Ленстры для факторизации целых чисел с использованием кривых Эдвардса. Найти улучшения для оптимизации времени работы программы. Выполнить теоретические и практические оценки сходимости на числах разной длины и при различных входных параметрах. Реализовать новый метод для умножения эллиптической точки на число. Построить кривые с большим кручением и положительным рангом над числовыми полями.

Купить