Strong pseudoprimes to base 2 (Q2097530)

The paper investigates the properties of strong pseudoprimes to base 2 (spsp(2)) using arguments both theoretical and heuristic. Then using those properties the paper provides a new efficient primality test, with running time \(O(\log^{2+\varepsilon}n)\)\, for an integer \(n\). An odd integer \(n\)\, is called strong pseudoprime for a base \(a\in \mathbb{N}\)\, (spsp(a)) if it passes the Miller-Rabin test to base \(a\), see [\textit{M. O. Rabin}, J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)]. As is well known the test does not assure the primality of \(n\). Many researches have tried to characterize the composite \(n\in spsp(a)\), in particular for \(a=2\), see [\textit{G. Jaeschke}, Math. Comput. 61, No. 204, 915--926 (1993; Zbl 0802.11001)]. The method in the present paper to detect composite numbers in spsp(2) is based in properties of the singular cubic curve \(y^2=x(x-a)^2\). Section 2 studies that curve defined over a finite field \(\mathbb{F}_q\)\, (Theorem 2.2). Section 3 presents the proposed primality test, see Algorithm 2, which the authors conjecture never fail to catch the compositeness of an integer \(n\). They also said that ``the experiment that we conducted on the set of all spsp(2) less than \(10^{22}\)\, indicates that our method is a primality test for all integers with less than 22 digits. In addition to this, we test our algorithm for numbers with a few hundred digits and it never fails to detect composite ones''.