Метод Полларда -- Штрассена
Самым популярным среди алгоритмов факторизации целых чисел с экспоненциальной сложностью является метод Полларда -- Штрассена, имеющий детерминированную оценку сложности . Он основан на следующей теореме: 
Теорема 3.  Пусть  -- натуральное число, . Тогда для любого натурального наименьший простой делитель числа может быть найден за арифметических операций. 
Для нахождения наименьшего простого делителя числа по методу Полларда -- Штрассена нужно положить , , и найти наименьший простой делитель за арифметических операций согласно теореме 3. Найденный делитель будет наименьшим простым делителем ввиду следующих соображений. Если  -- наименьший простой делитель , то и, следовательно, делит . Поэтому является также наименьшим простым делителем .