While detecting prime numbers is computationally fast ($O(\log^3 n)$), the fastest known algorithms to split a composite number into its prime factor are very slow (RSA cryptography relies on this assumption). Even the best known algorithms like the number field sieve all run in subexponential time. (Shor's algorithm actually provides a polynomial time algorithm, but on quantum computers.)
I know it is believed that no fast (classical) algorithm exists, but is there a "feeling" as to what could be the optional running time? Often there is a heuristic as to how far you can push the performance long before anybody actually achieves it.