Strengthening the Baillie-PSW primality test

Baillie, Robert; Fiori, Andrew; Wagstaff, Samuel S.

Strengthening the Baillie-PSW primality test

dc.contributor.author	Baillie, Robert
dc.contributor.author	Fiori, Andrew
dc.contributor.author	Wagstaff, Samuel S.
dc.date.accessioned	2021-07-06T16:34:16Z
dc.date.available	2021-07-06T16:34:16Z
dc.date.issued	2021
dc.description	Author original manuscript (preprint)	en_US
dc.description.abstract	In 1980, the first and third authors proposed a probabilistic primality test that has become known as the Baillie-PSW primality test. Its power to distinguish between primes and composites comes from combining a Fermat probable prime test with a Lucas probable prime test. No odd composite integers have been reported to pass this combination of primality tests if the parameters are chosen in an appropriate way. Here, we describe a significant strengthening of this test that comes at almost no additional computational cost. This is achieved by including in the test Lucas-V pseudoprimes, of which there are only five less than 10 (15)	en_US
dc.description.peer-review	Yes	en_US
dc.identifier.citation	Baillie, R., Fiori, A., & Wagstaff, S. S. (2021). Strengthening the Baillie-PSW primality test. Mathematics of Computation, 90(330), 1931-1955. https://doi.org/10.1090/mcom/3616	en_US
dc.identifier.uri	https://hdl.handle.net/10133/5943
dc.language.iso	en_US	en_US
dc.publisher	American Mathematical Society	en_US
dc.publisher.department	Department of Mathematics and Computer Science	en_US
dc.publisher.faculty	Arts and Science	en_US
dc.publisher.institution	State College (Pa.)	en_US
dc.publisher.institution	University of Lethbridge	en_US
dc.publisher.institution	Purdue University	en_US
dc.publisher.url	https://doi.org/10.1090/mcom/3616	en_US
dc.subject	Primality test	en_US
dc.subject	Lucas sequences	en_US
dc.subject	Baillie-PSW
dc.subject	Pseudoprimes
dc.subject.lcsh	Lucas numbers
dc.title	Strengthening the Baillie-PSW primality test	en_US
dc.type	Preprint	en_US