Prime factorization difficulty

Question

From Wikipedia:

Not all numbers of a given length are equally hard to factor. The hardest instances of these problems (for currently known techniques) are semiprimes, the product of two prime numbers.

There are no references to this claim.

Why is a prime factorization harder than a not-prime factorization?

Answer 1

When the best factoring algorithms are analyzed, their runtimes turn out to be a function of the size of the smallest prime factor of the number being factored. We define "harder to factor" as requiring longer runtimes for factorization algorithms. So to maximize the runtime of the algorithm, you need to maximize the size of the smallest prime factor. This hapopens when you have a semiprime with 2 factors, both of which are of similar magnitudes.

Answer 2

Crudely:

If $N$ is prime, it will take you some time to conclusively establish that.

But maybe $N=pq$ (both prime). Along the way while you are exploring whether or not $N$ is prime, you will discover one of these factors and you can terminate the investigation as to whether or not $N$ is prime. You now have two smaller numbers to investigate whether or not they are prime if you wish to fully factor $N$.

But maybe $N=pqr$ (all three prime). Now the same thing happens as with two prime factors, except there are more possibilities for discovering that $N$ is not prime. You (on average) discover this earlier. You again have two smaller numbers to investigate whether or not they are prime, and you reached this point faster than in the previous case.

And so on.

So discovering a factor of $N$ takes less effort (on average) when there are more prime factors in the first place. And once you break $N$ into two factors, continuing the process to factor those factors further is (on average) an order of magnitude faster, so can be ignored, even in the aggregate to reach the complete factorization of $N$.