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

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

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

Пусть мы раскладываем на множители. Предположим, что после деления на все осталась некоторая не разложившаяся на множители часть . Ясно, что . Если окажется, что при этом , то  -- простое число. Тогда мы включаем в факторную базу и храним также найденное значение . Это увеличивает длину векторов .

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

2. Стратегия PS (метод Полларда -- Штрассена). В алгоритме Диксона можно использовать метод Полларда -- Штрассена, описанный в п. 12.2.3, для разложения на множители. А именно, мы полагаем , и находим наименьший простой делитель согласно теореме 3. Если  -- наименьший простой делитель , принадлежащий , то и, следовательно, делит . Поэтому является также наименьшим простым делителем . Таким образом, мы можем находить наименьшие простые делители, принадлежащие .

Можно показать, что при использовании стратегии PS в оценке сложности алгоритма Диксона (см. п. 12.3.1) вместо появится . В частности, при , получаем, что алгоритм Диксона со стратегией PS работает за арифметических операций.

3. Стратегия EAS (ранний обрыв). Пусть и  -- некоторые константы такие, что . В обычном алгоритме Диксона мы разлагали на . В алгоритме Диксона со стратегией EAS мы сначала разлагаем на простые множители, не превосходящие , и, если неразложившаяся часть больше, чем , то отбрасываем это значение и переходим к следующему. В работе [Pom82] приведен анализ этой стратегии. В частности, показано, что алгоритм Диксона со стратегией EAS при , , делает арифметических операций. При этом .

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

4. Методы поиска соотношений линейной зависимости. На этапе 4 алгоритма Диксона для нахождения соотношения линейной зависимости нужно решать разреженную систему линейных уравнений над полем . Метод гауссова исключения не является оптимальным для этой цели. В работах [Lanc], [CopW], [Wied], [Bril] описаны более совершенные способы решения разреженных систем линейных уравнений над полем . В частности, алгоритм Копперсмита -- Винограда решает систему линейных уравнений от неизвестных за арифметических операций.