Strong pseudoprimes to base 2
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.
- Finding strong pseudoprimes to several bases
- Constructing Carmichael numbers which are strong pseudoprimes to several bases
- scientific article; zbMATH DE number 1643943
- A one-parameter quadratic-base version of the Baillie-PSW probable prime test
- A generalization of Miller’s primality theorem
- On a combined primality test
- Strong pseudoprimes to twelve prime bases
- Rabin-Miller Primality Test: Composite Numbers Which Pass It
- scientific article; zbMATH DE number 1164034
- Tabulating Pseudoprimes and Tabulating Liars
- A p + 1 Method of Factoring
- Advanced Topics in Computional Number Theory
- Elliptic Curves and Primality Proving
- Elliptic curves. Number theory and cryptography
- Factoring integers with elliptic curves
- Finding strong pseudoprimes to several bases
- Finding strong pseudoprimes to several bases. II
- Four primality testing algorithms
- Handbook of Elliptic and Hyperelliptic Curve Cryptography
- scientific article; zbMATH DE number 3460351 (Why is no real title available?)
- On distinguishing prime numbers from composite numbers
- On Strong Pseudoprimes to Several Bases
- PRIMES is in P
- Probabilistic algorithm for testing primality
- Riemann's hypothesis and tests for primality
- The Pseudoprimes to 25 ⋅10 9
This page was built for publication: Strong pseudoprimes to base 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097530)
