Rice professor sees probabilistic method revolutionizing computing

Though, without a proof, it's uninteresting. It's probably not true.

Even if it were true that no Carmichael number has 2 as a quadratic residue, that wouldn't give an efficient way of finding very large prime numbers, because to prove something prime given that it isn't Carmichael you still have to run the Fermat test to every base, which will take ages.

Now, that isn't the same as saying that n^2-2 is never a Carmichael number. I've no idea whether that's true, but it wouldn't be very surprising; hand-wavily, the "probability" that m is a square is on the order of 1/m, and the "probability" that m is a Carmichael number is something complicated-ish that's less than 1/(log m)^2, and so the probability that m is both is less than 1/m(log m)^2, whose integral is finite, so there should only be finitely many Carmichael numbers of the form n^2-2, and if there aren't any small ones then probably there aren't any at all. But, again, even if it's true that n^2-2 is never a Carmichael number, that doesn't give you an efficient way of generating primes.

It's also not the same thing as saying that n^2-2 never passes the Fermat test to base 2 without being prime. That also might be true, for the same hand-wavy reason as above (the number of Fermat pseudoprimes to a given base satisfies an upper bound of the same general form as the number of Carmichael numbers). Most likely it's either very easy or very difficult to prove, if it happens to be true.

In any case, for practical purposes, if you generate a very large number at random and it passes the Fermat test to any one base, then it's almost certainly prime. (For your numbers with thousands of digits, if a single Fermat test says the number is prime then it's more likely to be wrong because your computer has malfunctioned than because you happened to pick a non-prime that satisfies the Fermat test.)