Факторизация чисел с экспоненциальной сложностью
Пусть дано натуральное число , . Простейший алгоритм разложения на простые множители имеет следующий вид. Будем последовательно проверять делимость на . Если делители не найдены, то  -- простое число. Если же  -- первый найденный делитель числа , то есть наименьший простой делитель числа . В этом случае полагаем и повторяем вышеописанный процесс для , начиная не с , а с найденного , т. е. последовательно проверяем делимость на . Полное разложение на простые множители будет найдено за арифметических операций. 
Описано несколько подобных алгоритмов со сложностью . Например, метод Олвея для нечетного и нечетного находит наименьший нечетный делитель числа такой, что , либо доказывает, что такого не существует. Преимущество метода в том, что поиск делителей происходит без использования операции деления; на каждом шаге алгоритма делается лишь несколько сложений и вычитаний. Там же описан метод Ферма, который по заданному (также без деления) находит наибольший множитель , не превосходящий . 
Теперь рассмотрим алгоритмы факторизации со сложностью , . Многие из них подробно описаны. Мы приводим только процедуры нахождения нетривиального делителя числа (о нахождении разложения на простые множители см. введение).