Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13. Методы построения больших простых чисел Вверх: 12. Задача факторизации больших целых чисел Назад: 12.3.5 Другие методы   Содержание   Предметный указатель


12.4 Метод решета числового поля

В работе [LLMP] описан метод факторизации чисел $ n$ вида $ n=r^e\pm s$, где $ r$ и $ s$ невелики, с эвристической оценкой сложности $ e^{\left((c+o(1))(\ln n)^{1/3}(\ln\ln n)^{2/3}\right)}$, где $ c=2(2/3)^{2/3}$. Этот метод называется методом решета числового поля. С его помощью было разложено на множители число $ 2^{457}+1\simeq 10^{138}$. Суть метода заключается в том, что мы переходим в некоторое алгебраическое расширение $ \mathbb{Q}(\xi)$ поля рациональных чисел $ \mathbb{Q}$ и перебором $ a,b\in\mathbb{Z}$, $ (a,b)=1$, ищем элементы $ a+\xi b$, которые разлагаются на множители в некоторой факторной базе. Перебор $ a$ и $ b$ делается с помощью специального просеивания, наподобие метода квадратичного решета. Затем с помощью одного из методов исключения находят соотношение $ x^2\equiv y^2\mkern5mu({\rm mod}\,\,n)$. Тогда если $ 1<(x-\varepsilon y,n)<n$ для некоторого $ \varepsilon\in\{-1,1\}$, то $ (x-\varepsilon y,n)$ -- искомый нетривиальный делитель $ n$.

Имеется также препринт [BuhLP], в котором описан алгоритм факторизации произвольного $ n$ со сложностью $ e^{\left((\alpha+o(1))(\ln n)^{1/3}(\ln\ln
n)^{2/3}\right)}$ арифметических операций.

Имеются и другие работы в этом направлении (см. [Adl91]).


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13. Методы построения больших простых чисел Вверх: 12. Задача факторизации больших целых чисел Назад: 12.3.5 Другие методы   Содержание   Предметный указатель


Проект осуществляется при поддержке:
Геологического факультета МГУ,
РФФИ
   

TopList Rambler's Top100