Если известно, что N мало, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если N
меньше миллиона, то нужно включить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить значение d
168 = 1000 как заключительного члена для случая, когда число N окажется простым, большим 997
2). Такую таблицу можно получить при помощи короткой вспомогательной программы
.
Сложность алгоритма полного перебора возможных делителей равна O(N1/2). РО-алгоритм Полларда имеет сложность O(N1/4).
Метод непрерывных дробей, метод квадратичного решета и метод на основе
эллиптических кривых имеют сложность O(exp[c(ln(N)ln(ln(N)))1 / 2].В
настоящее время самым эффективным алгоритмом факторизации является метод
решета числового поля со сложностью O(exp[cln(N)1 / 3ln(ln(N))2 / 3]).