Improved error bounds for the Fermat primality test on random inputs

DOI10.1090/MCOM/3314MaRDI QIDQ3177720zbMATH OpenOpenAlexFDO

Authors Jared Duker Lichtman, Carl Pomerance

Publication date 1 August 2018

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.05569

zbMATH Keywords

Miller-Rabin testpseudoprimeprobable primeFermat test

Mathematics Subject Classification ID

Factorization; primality (11A51) Primality (11Y11)

Abstract: We investigate the probability that a random odd composite number passes a random Fermat primality test, improving on earlier estimates in moderate ranges. For example, with random numbers to $2^{200}$, our results improve on prior estimates by close to 3 orders of magnitude.

Recommendations

• Further investigations with the strong probable prime test
• The Probability that a Random Probable Prime is Composite
• Pseudoprime Statistics to 1019
• Average Case Error Estimates for the Strong Probable Prime Test
• Some thoughts on pseudoprimes
• Strong pseudoprimes to twelve prime bases
• scientific article; zbMATH DE number 503281
• scientific article; zbMATH DE number 1643943
• A one-parameter quadratic-base version of the Baillie-PSW probable prime test
• scientific article; zbMATH DE number 2098064

Cites work

• scientific article; zbMATH DE number 799757 (Why is no real title available?)
• Average Case Error Estimates for the Strong Probable Prime Test
• Estimating (x) and related functions under partial RH assumptions
• Evaluation and comparison of two efficient probabilistic primality testing algorithms
• Explicit estimates for the distribution of numbers free of large prime factors
• Further investigations with the strong probable prime test
• On the Number of False Witnesses for a Composite Number
• On the first sign change of (x) -x
• Probabilistic algorithm for testing primality
• Shifted primes without large prime factors
• The Difference between Consecutive Prime Numbers
• The Probability that a Random Probable Prime is Composite
• The generation of random numbers that are probably prime
• There are infinitely many Carmichael numbers

Cited in

(8)

• The Probability that a Random Probable Prime is Composite
• Strong pseudoprimes to twelve prime bases
• Bad witnesses for a composite number
• Average Case Error Estimates for the Strong Probable Prime Test
• Fermat pseudoprimes
• Average liar count for degree-2 Frobenius pseudoprimes
• Algorithms for the Multiplication Table Problem
• Pseudoprime Statistics to 1019

This page was built for publication: Improved error bounds for the Fermat primality test on random inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177720)