Why is prime factorisation computationally intensive compared to normal factorisation?

Question

Why do we use prime factors in asymmetric algorithms compared to other factors?

For example:

lets say we use two prime numbers p = 53 and q = 59 our public key in RSA algorithm would be p * q = 3127

while it is difficult to find the private key from this using prime
factorisation, I feel it is equally difficult to find the factors for some normal number too

like p = 52, q = 58 where public key would be p * q = 3016

but why is prime number preferred over the others, is it because how the algorithm works? Think I am missing something trivial.

Answer 1

If one of the number has small factors, then it is easy to factorize everything. For example, $52 = 2 \times 2 \times 13$. Once this is computed, the other factor can also be found. Bottom line: factoring algorithms work very well when the prime factors are not too large, so the the "hardest" factoring problem is with two prime factors only (of equal size).

Answer 2

The problem are not prime factors, the problem are large prime factors. There are many rather efficient factorization algorithms (such as Pollard's rho) that are good at finding small factors. Actually in RSA we want $p, q$ to be approximately of the same size so this disproportion cannot be leveraged to factor $p*q$.

If you have a $p, q$ primes then $p*q$ has only two factors, smallest one is equal to $p$ or $q$. If $p,q$ are composite then the smallest factor of $p*q$ is smaller (upper bound on the factor is only $min(\sqrt{p}, \sqrt{q})$). Thus using composite numbers reduces your problem to much smaller instance. Moreover if your numbers have really small factors (such as $2$) then the reduction is even more straightforward (e.g. I can decide to divide $3016$ by $8$ just by looking at binary representation of $3016$, then it remains to factor $377$ which is almost 10 times smaller).