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?

  • $\begingroup$ What is a "not-prime-factorization" ? $\endgroup$ – Peter May 3 '16 at 8:57

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.

  • $\begingroup$ For a complete factorisation, the important criterion is the size of the second-largest prime factor (which for a semiprime is just the smallest prime factor, as you say). $\endgroup$ – TonyK Nov 10 '14 at 17:31
  • $\begingroup$ So, is it only a proof by example? $\endgroup$ – gliderkite Nov 11 '14 at 14:44
  • $\begingroup$ We have upper bounds on factoring difficulty established by known algorithms. When you look at lower bounds you run into issues similar to those found in P=NP research. Most think it's likely that there is some superpolynomial lower bound (probably exponential) for factorization difficulty, and most people think there's an exponential lower bound for NP-complete problems. But no one has actually come out and proven it yet. $\endgroup$ – NovaDenizen Nov 11 '14 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.