Алгоритм Диксона
В алгоритме Диксона мы будем обозначать через наименьший неотрицательный вычет , а через -- некоторую константу такую, что . Множество простых чисел, не превосходящих , мы будем называть факторной базой и обозначать через . Алгоритм Диксона заключается в следующем: 
    1. Выбрать случайное и вычислить . 
    2. Пробными делениями попытаться полностью разложить в произведение простых . 
    3. В случае успеха, т. е. если , где , запомнить , и вектор , показателей, приведенных по модулю 2. Делать перебор до тех пор, пока не будет найдено чисел, для которых полностью разлагаются в факторной базе. 
    4. Найти (например, с помощью гауссова исключения) некоторое соотношение линейной зависимости между вычисленными на предыдущем этапе векторами : 
    5. Найденное на предыдущем этапе соотношение означает, что является квадратом натурального числа, которое мы обозначим через . С другой стороны, . Поэтому для имеем . Теперь если для некоторого , то  -- искомый нетривиальный делитель . 
Доказано, что если составное, то для случайно построенной пары , удовлетворяющей условию , вероятность того, что для некоторого , не меньше 1/2. 
Показано, что если в алгоритме Диксона перебрано случайных значений и на этапе 4 использовано гауссово исключение, то сложность этого алгоритма составляет арифметических операций. Согласно этой же работе, для нахождения нужного количества чисел таких, что Q(m) полностью разлагаются в факторной базе, достаточно перебрать случайных значений , где . В частности, при и сложность алгоритма Диксона составляет арифметических операций.