A Probable Prime Test with High Confidence Original Research Article

Monier and Rabin proved that an odd composite can pass the Strong Probable Prime Test for at most 1/4 of the possible bases. In this paper, a probable prime test is developed using quadratic polynomials and the Frobenius automorphism. The test, along with a fixed number of trial divisions, ensures that a compositenwill pass for less than 1/7710 of the polynomialsx2−bx−cwith (b2+4c n)=−1 and (−c n)=1. The running time of the test is asymptotically 3 times that of the Strong Probable Prime Test.