A Probable Prime Test with Very High Confidence for n ≡ 3 mod 4

Abstract. The workhorse of most compositeness tests is Miller—Rabin, which works very fast in practice, but may fail for one-quarter of all bases. We present an alternative method to decide quickly whether a large number n is composite or probably prime. Our algorithm is both based on the ideas of Pomerance, Baillie, Selfridge, and Wagstaff, and on a suitable combination of square, third, and fourth root testing conditions. A composite number n ≡ 3 mod 4 will pass our test with probability less than 1/331,000, in the worst case. For most numbers, the failure rate is even smaller. Depending on the the respective residue classes n modulo 3 and 8 , we prove a worst-case failure rate of less than 1/5,300,000, 1/480,000, and 1/331,000, respectively, for any iteration of our test. Along with some fixed precomputation, our test has running time about three times the time as for the Miller—Rabin test. Implementation can be achieved very efficiently by naive arithmetic only.