A Probable Prime Test With High Confidence

Abstract

Monier and Rabin proved that an odd composite can pass the Strong Probable Prime Test for at most $\frac{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 composite $n$ will pass for less than $\frac{1}{7710}$ of the polynomials $x^2-bx-c$ with $\left(\frac{b^2+4c}{n}\right)=-1$ and $\left(\frac{-c}{n}\right)=1$. The running time of the test is asymptotically $3$ times that of the Strong Probable Prime Test.