12.3 Факторизация чисел с субэкспоненциальной сложностью

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

Перейдем к описанию алгоритмов. Далее мы будем предполагать, что:     1) составное; это легко обнаружить с помощью тестов на псевдопростоту типа теста Соловея -- Штрассена (об этих тестах см. обзор [Вас]);

    2) не делится на простые числа , не превосходящие ; это легко проверить пробными делениями за шагов.

• 12.3.1 Алгоритм Диксона
• 12.3.2 Методы ускорения алгоритма Диксона
• 12.3.3 Алгоритм Бриллхарта - Моррисона
• 12.3.4 Метод квадратичного решета
• 12.3.5 Другие методы