Improved error bounds for the Fermat primality test on random inputs

DOI10.1090/MCOM/3314zbMATH Open1441.11302arXiv1609.05569OpenAlexW2522957312MaRDI QIDQ3177720FDOQ3177720

Authors: Jared Duker Lichtman, Carl Pomerance 

Publication date: 1 August 2018

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

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.

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

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

zbMATH Keywords

Miller-Rabin testpseudoprimeprobable primeFermat test

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• The Probability that a Random Probable Prime is Composite
• Strong pseudoprimes to twelve prime bases
• Average Case Error Estimates for the Strong Probable Prime Test
• 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)