Why factoring a number is difficult compared to finding out if it is prime (which can be done in polynomial time) ?

I would think they might be of similar difficulty in terms of computational complexity.

  • 4
    $\begingroup$ You should try these problems for some numbers and compare how many operations it takes you to figure it out. Is 2873456329875692846592873465928745692 prime? What is its factorization? $\endgroup$ Jul 10 '13 at 5:20
  • $\begingroup$ This example doesn't really draw the picture I'm interested in, i.e. large numbers with just a couple of large prime factors $\endgroup$ Jul 10 '13 at 5:24
  • 4
    $\begingroup$ The question is not correctly posed. There is no proof that factoring is more difficult; it just seems that way. Maybe tomorrow someone will discover an amazing algorithm that nobody has conceived of before. So it would be better to ask why factoring numbers appears to be more difficult than deciding if a number is prime or not. A reason is that we know "fast" methods of determining primality that don't lead to any nontrivial factors if the test says the number is composite. $\endgroup$
    – KCd
    Jul 10 '13 at 5:52
  • $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$
    – lhf
    Jul 10 '13 at 16:19

Why do we expect primality testing to be easier than factorizing?

Let's recall Fermat's Little Theorem and try to base a primality test upon it. This test won't always work but it will suggest the difference between primality testing and factorization.

Let $p$ be a prime. Suppose that $a$ and $p$ have greatest common divisor $(a,p)=1$. Then $$ a^{p-1} \equiv 1 \mod p. $$

This calculation can be performed quickly using repeated squaring and the fact that we can work $\mod p$ rather than having to actually compute the (very large) number $a^{p-1}$.

For example, $59$ is prime, and $2^{58} \equiv 1 \mod 59$. If we did not already know that $59$ is prime, getting the answer 1 here would strongly suggest (but not prove) that it is a prime.

Another example, $63$ is not prime, and $2^{62} \equiv 4 \mod 63$. If we did not already know that $63$ is composite, this calculation would be enough to demonstrate that $63$ is composite. However, it does not tell us what the factorization is.

This is an example of how you can test for primality but without finding the factorization. We could try calculating $a^{n-1} \mod n$ for many different values of $a$. If we get an answer that is not $1$, we would immediately know that $n$ is composite. If we get the answer $1$ every time, then we would grow increasingly confident that $n$ is prime.

What I have just described is not a foolproof primality test; the Carmichael numbers (for example 561) fool it. But it demonstrates the idea that one can find something out about primality while not finding out what the factors are. One idea here is that $\mathbb Z/n\mathbb Z$ (the integers considered modulo n) has a different structure depending on whether $n$ is prime or composite. There are things (like the above Fermat primality test) which we can we do to distinguish between these different structures. In this way, we can learn that a number is composite without finding out its factorization.

  • $\begingroup$ A superb answer indeed! $\endgroup$
    – Peter
    May 18 '16 at 9:28

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.