Если известно, что N мало, резонно иметь таблицу всех необходимых простых чисел как часть программы. Например, если N меньше миллиона, то нужно вклю­чить 168 простых чисел, меньших 1000 (к этому списку нужно еще добавить зна­чение d168 = 1000 как заключительного члена для случая, когда число N окажется простым, большим 9972). Такую таблицу можно получить при помощи короткой вспомогательной программы.

Сложность алгоритма полного перебора возможных делителей равна 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]).