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

12.2.4 Другие методы

Имеется алгоритм Ривеста -- Пинтера со сложностью $ O\left(n^{1/3}\right)$, но оценка нестрогая (см. [Voor]).

Алгоритм Ленстры со сложностью $ O\left((n^{1/3}\log
n\right)$ (см. [Len84]) основан на следующей теореме.

Теорема 4.  Пусть $ r,s,n$ -- натуральные числа, удовлетворяющие условиям $ 1\leqslant r<s<n$, $ n^{1/3}<s$, $ (r,s)=1$. Тогда существует не более 11 делителей числа $ n$, сравнимых с $ r$ по модулю $ s$, и имеется алгоритм, который находит все эти делители за $ O(\log n)$ арифметических операций.

Имеется также метод Лемера -- Пауэрса с эвристической оценкой сложности $ O\left(n^{1/4}\right)$, основанный на разложении $ \sqrt
n$ в непрерывную дробь. Из этого метода возник впоследствии популярный алгоритм Бриллхарта -- Моррисона, имеющий субэкспоненциальную сложность; мы обсудим его ниже.

Отметим также два метода, предложенных Шэнксом (см. [Scho]). Первый из них имеет сложность $ O\left(n^{1/4}\right)$. Сложность второго алгоритма в предположении расширенной гипотезы Римана есть $ O\left(n^{1/5+\varepsilon}\right)$.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.3 Факторизация чисел с субэкспоненциальной сложностью Вверх: 12.2 Факторизация чисел с экспоненциальной сложностью Назад: 12.2.3 Метод Полларда - Штрассена   Содержание   Предметный указатель


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