Метод Шермана — Лемана

Алгоритм Шермана — Лемана детерминированно раскладывает n на множители за O(n^{1 / 3}) арифметических операций.

Алгоритм

Пусть n нечетно и n > 8.

Шаг 1. Для $a=2,\;3,\;\ldots,\;[n^{1/3}]$ проверить условие $a\mid n$. Если на этом шаге мы не разложили n на множители, то переходим к шагу 2.

Шаг 2. Если на шаге делитель не найден и n — составное, то n = pq, где $p,\;q$ — простые числа, и $n^{1/3}<p\leqslant q<n^{2/3}$. Тогда для всех $k=1,\;2,\;\ldots,\;[n^{1/3}]$ и всех $d=0,\;1,\;\ldots,\;\left[\frac{n^{1/6}}{4\sqrt{k}}\right]+1$ проверить, является ли число $\left(\left[\sqrt{4kn}\right]+d\right)^2-4kn$ квадратом натурального числа. Если является, то для $A=\left[\sqrt{4kn}\right]+d$ и $B=\sqrt{A^2-4kn}$ выполнено сравнение $A^2\equiv B^2\pmod{n}$.

В этом случае проверить условие $1<(A\pm B,\;n)<n$. Если это условие выполнено, то мы разложили n на два множителя и алгоритм останавливается. Если алгоритм не нашел разложение n на два множителя, то n — простое число.

Источники: Институт проблем информационной безопасности МГУ «Информационная безопасность: криптография»