М. И. Анохин, Н. П. Варновский, В. М. Сидельников, В. В. Ященко "КРИПТОГРАФИЯ В БАНКОВСКОМ ДЕЛЕ"

Геовикипедия
wiki.web.ru

Поиск

Главная страница

Конференции: Календарь / Материалы

Каталог ссылок

Словарь

Форумы

В помощь студенту

Последние поступления

Геология | Курсы лекций

Обсудить в форуме

Добавить новое сообщение

Вперед: 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. Пусть -- натуральные числа, удовлетворяющие условиям $1\leqslant r<s<n$ , $n^{1/3}<s$ , . Тогда существует не более 11 делителей числа , сравнимых с по модулю , и имеется алгоритм, который находит все эти делители за $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)$ .

Михаил Анохин

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