(1) Consider the Lucas primality test (https://en.wikipedia.org/wiki/Lucas_primality_test). If applied to a Carmichael number, is it the case that the test is worst-case O(n)? It seems to me that it is, but I wanted to be sure.

(2) I've been trying to improve my generic isPrime method. Right now it's trial division below a certain bound, and Miller-Rabin with preselected bases otherwise. However, is there some range of numbers for which the Fermat primality test is the fastest option?