Кроме простого перебора есть что-нибудь?

Почему сложно факторизовать большие числа? Проблема в долгом переборе? Или в долгом делении?

wiki:Факторизация_целых_чисел
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора (класс BQP).

Спасибо!

Был на этой странице, но не дочитав первого абзаца, перешёл по гиперссылке)

(2) Вопрос не совсем понятен.
Если взять 100 значное число, и тупо проверять делимость на числа до корня из него - нужно количество операций из 99 знаков.
Вопрос в (0) то в чем?

виноват, из 50