|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О выборе двух нелинейных многочленов в алгоритме решета числового поля.дипломная работа (Специалист)
- Научный руководитель: Уланский Е.А.
- Автор: Гарба Владимир Николаевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2011
- Аннотация: В настоящее время наиболее эффективным алгоритмом факторизации больших чисел является метод решета числового поля (The Number Field Sieve, NFS). При разложении на множители числа N первым шагом алгоритма NFS является поиск двух неприводимых над полем рациональных чисел многочленов с целыми коэффициентами, имеющих общий корень по модулю N. Этот шаг существенно влияет на время выполнения оставшейся части алгоритма. Кроме того, сам этот шаг очень трудоемкий. Например, при разложении числа RSA-768 (оно состоит из 232 цифр) с использованием 80 компьютеров на поиск подходящих многочленов ушло примерно полгода. Обычно один многочлен имеет степень 6, а второй - линейный. Для таких степеней разработаны эффективные методы выбора многочленов. Однако за исключением метода Монтгомери выбора двух многочленов второй степени, не существует хороших аналогов построения двух нелинейных многочленов. В дипломной работе рассмотрены методы поиска нелинейных многочленов одинаковой степени. Главной целью в направлении выбора двух нелинейных многочленов является построение оптимальных многочленов, то есть многочленов, результант которых имеет порядок O(N).
- Добавил в систему: Уланский Евгений Александрович