I'm aware that factoring a prime into composites is one of the most difficult computational problems, but isn't it cheap to determine if a number is prime ? a^(p-1) == a mod p (where == means "congruent to" ). with modular exponentiation isn't it simple to compute the modulus ?
The little Fermat test requires you to test all "a"s in order to remove false positives. For most numbers, testing a few thousand bases is enough but you have Carmichael numbers that break the test.
There are better primality checks, but they all have downsides (either slow but provable or fast but probabilistic). Finding prime numbers can be shown to be easier than finding factors (see: how GIMPS checks for primality), but that doesn't make it easy.
isPrime(p) is polynomial relative to the number of digits of p, but not in any useful way- takes way too long practically speaking. But that's only if you want a definite solution.
If you're willing to do a probabilistic test, you can use algorithms like Miller-Rabin- the more time you use it with random inputs the more sure you are that the number is prime. And it's relatively easy to implement- check Wikipedia for the pseudocode.
