Алгоритм Шермана -- Лемана
Этот алгоритм имеет оценку сложности и заключается в следующем. 
    1. Считая, что , последовательно проверяем делимость исходного числа на . 
    2. Если на этапе 1 делитель не найден и составное, то , где и  -- простые числа, причем . Тогда для каждых и полагаем и проверяем, является ли число квадратом натурального числа. Если да, то , где , поэтому если для некоторого , то  -- искомый нетривиальный делитель . 
Теорема 2.  Если алгоритм Шермана -- Лемана закончил работу и не нашел делителя , то  -- простое число. 
Отметим, что в алгоритме Шермана -- Лемана возможны параллельные вычисления.