Primes ARE fundamentally predictable, in the following very strong sense: There is a deterministic polynomial time algorithm for checking whether a number is prime (i.e. the runtime is polynomial in the number of digits of the number being tested.) http://en.wikipedia.org/wiki/AKS_primality_test