[valw]

> factoring prime numbers

factoring into prime numbers ;-) (factoring a prime number is trivial, that's why it's called prime)

[psyc]

It's only trivial if you already know it's prime. Determining that is non-trivial enough that a tractable deterministic algorithm wasn't devised until 2002, and its time complexity is thought to be the sixth power of log(n = digits).