12.3.1 Алгоритм Диксона

В алгоритме Диксона мы будем обозначать через наименьший неотрицательный вычет , а через -- некоторую константу такую, что . Множество простых чисел, не превосходящих , мы будем называть факторной базой и обозначать через . Алгоритм Диксона заключается в следующем:     1. Выбрать случайное и вычислить .

    2. Пробными делениями попытаться полностью разложить в произведение простых .

    3. В случае успеха, т. е. если , где , запомнить , и вектор , показателей, приведенных по модулю 2. Делать перебор до тех пор, пока не будет найдено чисел, для которых полностью разлагаются в факторной базе.

    4. Найти (например, с помощью гауссова исключения) некоторое соотношение линейной зависимости между вычисленными на предыдущем этапе векторами :

    5. Найденное на предыдущем этапе соотношение означает, что является квадратом натурального числа, которое мы обозначим через . С другой стороны, . Поэтому для имеем . Теперь если для некоторого , то  -- искомый нетривиальный делитель .

В работе [Dix] доказано, что если составное, то для случайно построенной пары , удовлетворяющей условию , вероятность того, что для некоторого , не меньше 1/2.

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