Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число на множители за арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году.^[1]

Алгоритм

Пусть нечетно и .

Шаг 1. Для проверить условие . Если на этом шаге мы не разложили на множители, то переходим к шагу 2.

Шаг 2. Если на шаге 1 делитель не найден и — составное, то , где — простые числа, и . Тогда для всех и всех проверить, является ли число квадратом натурального числа. Если является, то для и выполнено сравнение:

или .

В этом случае для проверяется неравенство . Если оно выполнено, то — разложение на два множителя.

Если алгоритм не нашел разложение на два множителя, то — простое число.

Примечания