On the Number of False Witnesses for a Composite Number

Paul Erdös, Carl Pomerance

Type: Article

Publication Date: 1986-01-01

Citations: 25

DOI: https://doi.org/10.2307/2008231

View Publication

Locations

Mathematics of Computation - View

Similar Works

Action	Title	Year	Authors
+	On the number of false witnesses for a composite number	1987	Paul Erdös Carl Pomerance
+ PDF Chat	On the Number of Witnesses in the Miller–Rabin Primality Test	2020	Shamil Ishmukhametov Bulat Gazinurovich Mubarakov R. G. Rubtsova
+	On the difficulty of finding reliable witnesses	1994	W. R. Alford Andrew Granville Carl Pomerance
+ PDF Chat	Strong pseudoprimes to base 2	2022	Kubra Nari Enver Ozdemır Neslihan Ayşen Özkirişçi
+	Generalized Strong Pseudoprime Tests and Applications	2000	Pedro Berrizbeitia T. G. Berry
+	On the Number of Witnesses (a mod n) Providing A Proper Divisor of n	1995	Heiko Gerlach
+	Pseudoprimes	1995	Lindsay N. Childs
+ PDF Chat	Finding strong pseudoprimes to several bases	2000	Zhenxiang Zhang
+	Roots of Unity in ℤ/mℤ	1995	Lindsay N. Childs
+	Counting composites with two strong liars	2013	Eric Bach Andrew Shallue
+	Counting composites with two strong liars	2013	Eric Bach Andrew Shallue
+	Carmichael Numbers	2008
+	Euler Pseudoprime Polynomials and Strong Pseudoprime Polynomials	2000	Véronique Mauduit
+	Some Remarks on Primality Testing Based on Lucas Functions	2023	Siguna Müller
+ PDF Chat	Counting composites with two strong liars	2015	Eric Bach Andrew Shallue
+ PDF Chat	Tabulating Pseudoprimes and Tabulating Liars	2016	Andrew Shallue
+ PDF Chat	Bad witnesses for a composite number	2024	Johnathan Djella Legnongo Tony Ezome Florian Luca
+ PDF Chat	A one-parameter quadratic-base version of the Baillie-PSW probable prime test	2002	Zhenxiang Zhang
+	On the Number of Primality Witnesses of Composite Integers	2021	B. G. Mubarakov
+	On the number of primality witnesses of composite integers	2021	Bulat Gazinorovich Mubarakov

Works That Cite This (21)

Action	Title	Year	Authors
+	Finding Four Million Large Random Primes	2007	Ronald L. Rivest
+ PDF Chat	The generation of random numbers that are probably prime	1988	Pierre Beauchemin Gilles Brassard Claude Crépeau Claude Goutier Carl Pomerance
+ PDF Chat	Average liar count for degree-$2$ Frobenius pseudoprimes	2019	Andrew Fiori Andrew Shallue
+ PDF Chat	The probability that a random probable prime is composite	1989	Su Hee Kim Carl Pomerance
+ PDF Chat	On the average number of groups of square-free order	1987	Carl Pomerance
+ PDF Chat	Number-Theoretic Algorithms	1990	Eric Bach
+	Prime Numbers	2004	Richard K. Guy
+ PDF Chat	Tabulating Pseudoprimes and Tabulating Liars	2016	Andrew Shallue
+ PDF Chat	Elliptic pseudoprimes	1989	I. Miyamoto M. Ram Murty
+	How to Recognize Whether a Natural Number Is a Prime	1996	Paulo Ribenboim

Works Cited by This (17)

Action	Title	Year	Authors
+	On the distribution of amicable numbers. II.	1981	Carl Pomerance
+ PDF Chat	A new lower bound for the pseudoprime counting function	1982	Carl Pomerance
+ PDF Chat	On the number of restricted prime factors of an integer. I	1976	Karl K. Norton
+	Central Limit Theorems	1997	Y. S. Chow Henry Teicher
+ PDF Chat	The pseudoprimes to 25⋅10⁹	1980	Carl Pomerance J. L. Selfridge Samuel S. Wagstaff
+ PDF Chat	On the distribution of pseudoprimes	1981	Carl Pomerance
+	ON THE NORMAL NUMBER OF PRIME FACTORS OF <i>p</i>-1 AND SOME RELATED PROBLEMS CONCERNING EULER'S ø-FUNCTION	1935	P. Erdős
+	On a Primality Test of Solovay and Strassen	1982	A. O. L. Atkin Richard G. Larson
+	Analysis of a simple factorization algorithm	1976	Donald E. Knuth Luis Trabb Pardo
+	Th�or�me de Brun-Titchmarsh; application au th�or�me de Fermat	1985	�tienne Fouvry