A probable prime test with high confidence (Q1273196): Difference between revisions

The Rabin strong probable prime test of an integer \(n\) has a probability of 1/4 for failing to detect compositeness. The author develops an improvement running about three times as long but with error of about 1/7710. This consists of a Lucas-type adaptation called the ``quadratic Frobenius tests.'' For \(n\) prime and \(\xi\) (with conjugate \(\xi')\) roots of the unfactorable \(x^2-bx-c\) it is easily seen that in \(\mathbb{F}_{n^2}\), with \(\eta=\xi^{(n+1)/2}\), then \(\eta^2(=\xi^n\cdot\xi)\equiv\xi'\xi=-c\) (hence ``Frobenius''). If additionally \((-c\mid n)=-1\), then \(\eta\notin \mathbb{F}_n\). At the same time \(\xi^{(n^2-1)}\equiv 1\), and this works on the even power in \(n^2-1\) (rather than \(n-1\) as in the probable prime test). The failure analysis is very sophisticated. For the mixed strategy, the author cites the work of \textit{C. Pomerance}, \textit{J. L. Selfridge} and \textit{S. Wagstaff} [The pseudoprimes to \(25\cdot 10^9\), Math. Comput. 35, 1003-1026 (1980; Zbl 0444.10007)].