Нахождение простого делителя числа за полиномиальное время?

[max(Im)]

Правда ли, что найти какой-нибудь простой делитель числа натурального числа $n$ за полиномиальное время (от длины двоичной записи $n$) нельзя?

[Sonic86]

Народ вроде пытался, но ничего пока не вышло.
Поиск делителя (равносильно факторизации числа) даже вроде не NP-полная задача.
На этом факте невозбранно работает криптосистема RSA, гуглите.

[max(Im)]

Действительно. Так можно было бы быстро решить факторизацию... Не подумал..

Тогда еще такой вопрос. Известно, что существует полиномиальный алгоритм проверки числа на простоту. А можно ли быстро проверить, является ли число произведением двух простых чисел? Или это тоже из этой области?

[Sonic86]

max(Im) в сообщении #552904 писал(а):

А можно ли быстро проверить, является ли число произведением двух простых чисел?

Интересный вопрос! Я не знаю на него ответ.
Так, эвристически, если алгоритм AKS придумали не так давно, то для такой задачи, видимо, еще ничего не придумали (хотя кто знает).