Why do most miners choose to use Fermat’s test for primality? I know it’s fast, but there’s another test - the Miller-Rabin (http://en.wikipedia.org/wiki/Miller-Rabin_primality_test) that has the same big-O running time, and is more accurate.
In fact, most other applications of probabalistic primality tests use the Miller-Rabin (for example, GMP’s own primality function (https://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions), and Mathematica).
In big O notations constants are generally ignored. Maybe Miller Rabin is faster in the general case where the Fermat test is faster on smaller numbers, like the ones used for Primecoin. I couldn’t find any definitive to compare the actual performance of the two, either. I can’t really say if that is the case.
Even if the Miller Rabin test is more accurate the chance of finding a psuedo prime with the fermat test is less than the chance of finding a real prime, so it doesn’t compromise the proof of work at all.