📄Работа №77185
Тема: Факторизация целого числа
Тип работы
Дипломные работы, ВКР
Предмет
Информатика и вычислительная техника
Объем:
45 листов
Год:
2017
Просмотров:
316
4225
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 2
Постановка задачи 4
Глава 1. Анализ 5
Выбор кривой в зависимости от простоты числа 22
Метод нахождения подсемейства с большим рангом 23
Построение индивидуальных кривых с кручением Z/4Z ф Z/8Z 24
Глава 2. Реализация и экспериментальные оценки 25
Заключение 28
Листинг 29
Постановка задачи 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 бит.
Данная работа посвящена изучению задачи определения сходимости метода в случае одновременной работы нескольких кривых. Эта задача связана с распределением гладких чисел.
Решение этой проблемы связано с изучение распределения гладких чисел, что является известной научной проблемой, а также и разработкой модели применения этой теории к методу Ленстры.
Постановка задачи
Изучить и реализовать алгоритм Ленстры для факторизации целых чисел с использованием кривых Эдвардса. Найти улучшения для оптимизации времени работы программы. Выполнить теоретические и практические оценки сходимости на числах разной длины и при различных входных параметрах. Реализовать новый метод для умножения эллиптической точки на число. Построить кривые с большим кручением и положительным рангом над числовыми полями.
Самый быстрый метод факторизации больших чисел - это решета числового поля(НБЗ), изобретенный Поллардом в 1991 году. С тех пор он был существенно усовершенствован (была создана “специальная” форма, которая используется только для факторизации числа, близкого к идеальной степени, таких как числа Ферма).
С помощью решета числового поля в алгоритме RSA были успешно разложены числа 663 бита Бахром, Франком в 2005 году. Время, необходимое для реализации факторизации b-битного RSA модуля, обеспечивает верхнюю границу безопасности b-битного RSA.
Для того чтобы факторизовать большое число N NFS требует разложения большого числа целых чисел средних размеров, созданных во время выполнения, возможно размером 200 бит. Такие цифры могут постоянно корректироваться за небольшое количество времени. Даже небольшие улучшения сделают значительную разницу в том, насколько большое число мы можем факторизовать.
Метод факторизации эллиптических кривых (ECM) (который является основным предметом этой работы) является субэкпоненциальным алгоритмом. Это означает, что асимптотически он работает быстрее, чем все другие известные методы (кроме квадратичного решета и решета числового поля). Кроме того, его сложность определяется размером наименьшего делителя, а не размером факторизуемого числа, поэтому он может находить делители у огромных чисел специального вида. ECM является лучшим методом для выполнения факторизации целых чисел в 200-битном диапазоне с простыми множителями примерно до 40 бит.
Данная работа посвящена изучению задачи определения сходимости метода в случае одновременной работы нескольких кривых. Эта задача связана с распределением гладких чисел.
Решение этой проблемы связано с изучение распределения гладких чисел, что является известной научной проблемой, а также и разработкой модели применения этой теории к методу Ленстры.
Постановка задачи
Изучить и реализовать алгоритм Ленстры для факторизации целых чисел с использованием кривых Эдвардса. Найти улучшения для оптимизации времени работы программы. Выполнить теоретические и практические оценки сходимости на числах разной длины и при различных входных параметрах. Реализовать новый метод для умножения эллиптической точки на число. Построить кривые с большим кручением и положительным рангом над числовыми полями.
✅ Заключение
В результате, благодаря введенным улучшениям: переходу к проективным координатам и применению кривых Эдвардса, мною было показано, что метод Ленстры работает достаточно быстро. Время факторизации зависит от границы первого этапа алгоритма B, случайного выбора кривой, который не всегда удачен, что значительно может ухудшить результаты, и количества этих кривых. Благодаря анализу входных параметров были найдены оптимальные данные. Были показаны конкретные теоретические и практические оценки сходимости на числах различной длины.
Также был предложен новый метод умножения эллиптической точки на число. Показаны теоретические и экспериментальные оценки. Я показала, что данное улучшение также снизило время выполнения работы алгоритма.
Также был предложен новый метод умножения эллиптической точки на число. Показаны теоретические и экспериментальные оценки. Я показала, что данное улучшение также снизило время выполнения работы алгоритма.
ИЛИ
Поиск аналога
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.