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


12.3.2 Методы ускорения алгоритма Диксона

На практике в алгоритме Диксона часто используют один или несколько описываемых ниже методов ускорения его работы.


1. Стратегия LP (использование больших простых). Впервые она предложена в работе [BrMor] и обычно используется на практике.

Пусть мы раскладываем $ Q(m)$ на множители. Предположим, что после деления на все $ p\in\pi$ осталась некоторая не разложившаяся на множители часть $ q$. Ясно, что $ q>L^a$. Если окажется, что при этом $ q\leqslant L^{2a}$, то $ q$ -- простое число. Тогда мы включаем $ q$ в факторную базу $ \pi$ и храним также найденное значение $ Q(m)$. Это увеличивает длину векторов $ v(m)$.

В работе [Pom82] показано, что теоретическая оценка сложности алгоритма Диксона с использованием стратегии LP не улучшается.


2. Стратегия PS (метод Полларда -- Штрассена). В алгоритме Диксона можно использовать метод Полларда -- Штрассена, описанный в п. 12.2.3, для разложения $ Q(m)$ на множители. А именно, мы полагаем $ y=\left(\left[L^{a/2}\right]+1\right)$, $ t=Q(m)$ и находим наименьший простой делитель $ (t,y!)$ согласно теореме 3. Если $ q$ -- наименьший простой делитель $ t$, принадлежащий $ \pi$, то $ q\leqslant L^a<y$ и, следовательно, $ q$ делит $ y!$. Поэтому $ q$ является также наименьшим простым делителем $ (t,y!)$. Таким образом, мы можем находить наименьшие простые делители, принадлежащие $ \pi$.

Можно показать, что при использовании стратегии PS в оценке сложности алгоритма Диксона (см. п. 12.3.1) вместо $ L^{\max\{a+b,3a\}}$ появится $ L^{\max\{a/2+b,3a\}}$. В частности, при $ a=3^{-1/2}$, $ b=a+1/2a$ получаем, что алгоритм Диксона со стратегией PS работает за $ L^{\sqrt3}$ арифметических операций.


3. Стратегия EAS (ранний обрыв). Пусть $ c$ и $ \theta$ -- некоторые константы такие, что $ 0<c,\theta<1$. В обычном алгоритме Диксона мы разлагали $ Q(m)$ на $ p\in\pi$. В алгоритме Диксона со стратегией EAS мы сначала разлагаем $ Q(m)$ на простые множители, не превосходящие $ L^{a\theta}$, и, если неразложившаяся часть $ Q(m)$ больше, чем $ n^{1-c}$, то отбрасываем это значение $ m$ и переходим к следующему. В работе [Pom82] приведен анализ этой стратегии. В частности, показано, что алгоритм Диксона со стратегией EAS при $ a=\sqrt{2/7}$, $ c=1/7$, $ \theta=1/2$ делает $ L^{\sqrt{7/2}}$ арифметических операций. При этом $ b=a+c/(2\theta
a)+(1-c)/(2a)$.

Можно также применять стратегию EAS с несколькими обрывами.


4. Методы поиска соотношений линейной зависимости. На этапе 4 алгоритма Диксона для нахождения соотношения линейной зависимости нужно решать разреженную систему линейных уравнений над полем $ \mathbb{Z}_2$. Метод гауссова исключения не является оптимальным для этой цели. В работах [Lanc], [CopW], [Wied], [Bril] описаны более совершенные способы решения разреженных систем линейных уравнений над полем $ \mathbb{Z}_2$. В частности, алгоритм Копперсмита -- Винограда решает систему линейных уравнений от $ r$ неизвестных за $ O\left(r^{2,495548}\right)$ арифметических операций.


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


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

TopList Rambler's Top100