How to test implementation of primality tests like Miller–Rabin? The Miller-Rabin primality test is an algorithm for checking if number is a prime. What would be best way to test implementation of such algorithm (or any primality test in general)?
Well, the obvious thing to do is give it a long list of integers of known primality, and see whether the algorithm reports it correctly (with it occasionally reporting a composite as "relatively-prime" not being counted as an error, as long as it reports that value as composite at least 75% of the time).

However, that simple-minded test might miss something.  The Miller-Rabin test can report $n$ is "composite" because of one of two reasons:


Because $g^{n-1} \ne 1 \bmod n$; that is, the Fermat test fails
Because $g^{(n-1)/2^\ell} \bmod n$ is a nontrivial squareroot of 1


If you just throw random composites $n$ at it, then it'll run into the first reason almost all the time.  Hence, it makes sense to deliberately try a value $n$ that fails for the second reason.

One set of values $n$ are known as Carmichael numbers; these are composites with $g^{n-1} = 1 \bmod n$ for all integers $g$ relatively prime to $n$; if we test a Carmichael number with no small factors, the Fermat test will almost always succeed, and so if the test fails, it'll be be the second reason.

One way of finding such Carmichael numbers is to search for prime triplets $6p+1, 12p+1, 18p+1$; if all three are prime, then $(6p+1)(12p+1)(18p+1)$ is a Carmichael number.