Counting composites with two strong liars
| Autor: | Andrew Shallue, Eric Bach |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Algebra and Number Theory
Almost prime Mathematics - Number Theory Applied Mathematics Prime number 11Y11 Prime (order theory) Combinatorics Base (group theory) Computational Mathematics symbols.namesake Prime factor FOS: Mathematics Euler's formula symbols Calculus Number Theory (math.NT) Variety (universal algebra) Primality test Mathematics |
| Zdroj: | Mathematics of Computation. 84:3069-3089 |
| ISSN: | 1088-6842 0025-5718 |
| DOI: | 10.1090/mcom/2949 |
| Popis: | The strong probable primality test is an important practical tool for discovering prime numbers. Its effectiveness derives from the following fact: for any odd composite number $n$, if a base $a$ is chosen at random, the algorithm is unlikely to claim that $n$ is prime. If this does happen we call $a$ a liar. In 1986, Erd\H{o}s and Pomerance computed the normal and average number of liars, over all $n \leq x$. We continue this theme and use a variety of techniques to count $n \leq x$ with exactly two strong liars, those being the $n$ for which the strong test is maximally effective. We evaluate this count asymptotically and give an improved algorithm to determine it exactly. We also provide asymptotic counts for the restricted case in which $n$ has two prime factors, and for the $n$ with exactly two Euler liars. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|