Обратно. Из (3) следует, что

ed-1=kj(N)=2^sr,

где r нечетное число и s³2, так как 4/j(N). Рассмотрим следующий алгоритм факторизации N.

Входные данные алгоритма. Натуральное число N = pq с неизвестной факторизацией. Число 2^sr кратное j(N) при нечетном r и s³2. Выходные данные алгоритма. Числа p, q.

ШАГ 1. Выбрать случайное aÎ(ℤ/N)*, вычислить b º a ^r (mod N).

ШАГ 2. Найти номер i, 1£ i£ s такой, что

, ≢ .

Если такой номер i найдется, то положить

.

Тогда p или q равно НОД(с-1, N). Алгоритм заканчивает работу. Если такое i не найдется, то перейти к шагу 1.

Это вероятностный алгоритм. Одним из параметров его эффективности является среднее число прохождений через шаг 2. Следующая теорема говорит об эффективности метода.

ТЕОРЕМА 1. Сложность вычислений ограничена величиной O(logN) арифметических операций по mod N. При случайном aÎ(ℤ/N)* вероятность того, что требуемый номер i найдется не меньше . Среднее число прохождений алгоритма через шаг 2 не больше 2.

ТЕОРЕМА 2. По N и j(N) можно найти p и q.

Действительно, имеем систему нелинейных уравнений относительно p и q:

pq=N, (p-1)(q-1)= j(N).