Алгоритм Диксона — алгоритм факторизации, использующий в своей основе идею Лежандра, заключающуюся в поиске пары целых чисел и таких, что и

Метод Диксона является обобщением метода Ферма.

Предварительные вычисления

Пусть задано подмножество простых чисел , называемое факторной базой.

Каждому -гладкому числу сопоставляется вектор показателей из разложения , а также двоичный вектор, полученный из вектора приведением всех его координат по модулю 2,

.

Если теперь подобрать такое множество различных -гладких чисел , что выполнится линейное соотношение

то для произведения выполнится сравнение

где определяется как

Описание алгоритма

1. Выбирается случайное и вычисляется .
2. Проверка, факторизуют ли числа из факторной базы .
3. Если является -гладким числом, то есть:
   следует запомнить и . Повторять процедуру генерации чисел до тех пор, пока не будет найдено чисел чисел , являющихся -гладкими.
4. Найти линейную зависимость:

   .

   и положить:

   .

5. Проверить . Если это так, то повторить процедуру генерации. Если нет, то найдено нетривиальное разложение:

Вычислительная сложность

Среднюю временную арифметическую сложность алгоритма Диксона можно оценить выражением

,

где  — сложность решения системы из линейных уравнений от неизвестных. В данном случае .

Возьмем в качестве величину , где , тогда

Отсюда следует, что трудоемкость алгоритма Диксона оценивается следующим образом

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. 2003. Стр. 78-83.
• Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. 2002. Стр. 77-80.