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

12.2.2 Метод Полларда

Схема этого метода (называемого $ \rho$-методом и широко используемого) заключается в следующем.     1. Выбрать функцию $ f\colon\mathbb{Z}_n\to\mathbb{Z}_n$ (обычно $ f$ -- многочлен степени не ниже 2).

    2. Случайно выбрать $ x_0\in\mathbb{Z}_n$ и, вычисляя $ x_1,x_2,\ldots$ по формуле $ x_j=f(x_{j-1})\bmod
n$, проверять тест этапа 3.

    3. Проверить условие $ 1<(x_j-x_k,n)<n$ для номеров $ j,k$, выбранных по одному из следующих правил:

     1) $ k<j$;

     2) $ j=2k$;

     3) если $ 2^h\leqslant j<2^{h+1}$, то $ k=2^h-1$.

Если делитель не найден, то переходим к следующим $ j,k$.

Метод Полларда имеет эвристическую оценку сложности $ O\left(n^{1/4}\right)$.

Этим методом было разложено на множители число Ферма $ 2^{256}+1$ (см. [BP]). Сам метод впервые описан в [Poll75]; способ экономного использования памяти для хранения $ x_j$ можно найти в [SSY].

В книге [Kob] приведено обоснование оценки сложности метода с использованием правила 3 выбора $ j$ и $ k$.


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


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