Because nobody knows a fast algorithm to factorize an integer into its prime factors. Yet, it is very easy to check if a set of prime factors multiply to a certain integer.

https://stackoverflow.com/questions/439870/why-are-primes-im...