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