The Lucas primality test states that a number N is prime iff there exists a base $B, 1 < B < n$, such that:
[a] $\ B^{N-1} \equiv 1 \pmod N$
...and...
[b] $B^{(N-1)/F} \not\equiv 1 \pmod N$ for all prime factors $F$ of $N-1$.
Now we could select B at random but then the test wouldn't be deterministic. In order to force it to be so we would have to try every possible base until either [a] or [b] fails. So what's the lower bound? Well for most numbers I assume it's fairly reasonable but for one class of numbers at least it's in the neighborhood of $\ N^{1/3}$ : the Carmichael numbers. In fact, the only bases that give a definitive answer for a Carmichael are those that contain at least one of its factors. In other words, trial division would beat a Lucas primality test on these numbers!
So my concern here is whether or not this fact has been taken into account (or is at least a documented caveat) in the definition of Pratt certificates and such?
*** EDIT ***
I guess the takeaway here is that, while having little to no value as a strictly deterministic test, the Lucas primality test is nonetheless an excellent probabilistic method. That is the chance that any given number base yields a correct answer is basically 50% and therefore even with respect to Carmichaels, where the number of bases NOT coprime to its prime factors are indisputably plentiful, the probability of finding a suitable base at random is actually quite high. (Depending on the number of trials of course.)
Special thanks to Peter for the helpful comments. Cheers everyone!
For Carmichael numbers there is no base $B$ such that condition [b] is fulfilled. Therefore a valid Pratt certificate cannot be created.
Choosing random bases is pretty useless for this test as condition [b] is not fulfilled for each pair of prime and base but only for at least one.
Example: $43$ is prime, but $11^{42/3} = 11^{14} \equiv 1 \pmod{43}$.