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


12.2.3 Метод Полларда -- Штрассена

Самым популярным среди алгоритмов факторизации целых чисел с экспоненциальной сложностью является метод Полларда -- Штрассена, имеющий детерминированную оценку сложности $ O\left(n^{1/4}\log^4n\right)$. Подробное описание метода можно найти в [Poll74], [Pom82], [Sch1], [Stra]. Он основан на следующей теореме:

Теорема 3.  Пусть $ z$ -- натуральное число, $ y=z^2$. Тогда для любого натурального $ t$ наименьший простой делитель числа $ (t,y!)$ может быть найден за $ O\left(z\ln ^2z\ln^2t\right)$ арифметических операций.

Для нахождения наименьшего простого делителя числа $ n$ по методу Полларда -- Штрассена нужно положить $ z=\left[n^{1/4}\right]+1$, $ y=z^2$, $ t=n$ и найти наименьший простой делитель $ (t,y!)$ за $ O\left(z\ln ^2z\ln^2t\right)=O\left(n^{1/4}\ln^4n\right)$ арифметических операций согласно теореме 3. Найденный делитель будет наименьшим простым делителем $ n$ ввиду следующих соображений. Если $ p$ -- наименьший простой делитель $ n$, то $ p\leqslant\sqrt n<y$ и, следовательно, $ p$ делит $ y!$. Поэтому $ p$ является также наименьшим простым делителем $ (n,y!)=(t,y!)$.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.2.4 Другие методы Вверх: 12.2 Факторизация чисел с экспоненциальной сложностью Назад: 12.2.2 Метод Полларда   Содержание   Предметный указатель

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