Well, yes, there is a probabilistic polynomial time algorithm the determines whether a number is a Carmichael number of not (probabilistic in the sense that it always returns the correct value, it terminates quickly with high probability). However, it isn't as helpful as you are thinking for your application.
The algorithm is based on two observations:
- Carmichael numbers are easy to factor
- Given the complete factorization, it is easy to verify whether a number is a Carmichael number or not (Korselt's criterion, as Thomas mentioned).
Here's the details on the first observation: if we have a composite number $N$, and an even value $e$ for which $x^e \equiv 1 \bmod N$ for a nontrivial fraction of the values $x$, then we can factor $N$. We do this by computing $\lambda$ a power of 2 such that $e/\lambda$ is odd, and for random values of $x$, compute $x^{e/\lambda}, x^{2e/\lambda}, x^{4e/\lambda}, ..., x^e$. If the series ends in 1 (which it will with good probability; that's the condition we placed on $e$), we look at the value immediately previous to the first 1; if that value $x^{ke/\lambda}$ is not -1, then we have the nontrivial factors $gcd(N, x^{ke/\lambda}-1)$ and $gcd(N, x^{ke/\lambda}+1)$ (because $x^{ke/\lambda}$ is a nontrivial square root of 1). In addition, if $N$ has more than 2 factors, this yields a random factorization of $N$.
Now, if $N$ is a Carmichael number, then $e = N-1$ is such a value; in fact, for any $x$, we have either $gcd(x,N)>1$ (and hence we have a factorization of $N$), or $x^{e} \equiv 1$ (and hence we have a factorization with good probability). In addition, if we pick a value $x$ and we find that $gcd(x,N)=1$ and $x^{e} \neq 1$, then we've just shown that $N$ is not a Carmichael number.
Hence, the probabilistic algorithm would look like:
Check if $N$ is prime; if it is, then return FALSE.
While we have don't have a complete factorization of $N$
Select a random $x$
If $gcd(x, N)=1$ and $x^{N-1} \ne 1 \bmod N$, then return FALSE.
Otherwise examine $gcd(x, N)$, $x^{(N-1)/\lambda}$ for a nontrivial factorization of $N$
If we have found a nontrivial factor, use that nontrivial factor to attempt to find more prime factors of $N$
Once we have a complete factorization of $N$, apply Korselt's criteria to determine whether $N$ is a Carmichael number.
This answers your question, however it's not very useful for determining whether a number is prime.
On the other hand, if you need an algorithm that produces large prime numbers, and you aren't happy with probabilistic methods, have you considered the Shawe-Taylor algorithm appendix A.1.2.1? The numbers this algorithm generates are guaranteed prime, and my experience is that it is about as fast as searching for primes using a Miller-Rabin test.
