Why is factorization of large number hard

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.