HackerPapers

arXiv:1509.00864math.NT

Strong Pseudoprimes to Twelve Prime Bases

Jonathan P. Sorenson, Jonathan Webster

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

Let $ψ_m$ be the smallest strong pseudoprime to the first $m$ prime bases. This value is known for $1 \leq m \leq 11$. We extend this by finding $ψ_{12}$ and $ψ_{13}$. We also present an algorithm to find all integers $n\le B$ that are strong pseudoprimes to the first $m$ prime bases; with a reasonable heuristic assumption we can show that it takes at most $B^{2/3+o(1)}$ time.

arXiv comments
Journal reference
DOI
doi:10.1090/mcom/3134
Subjects
math.NTNumber Theory cs.DSData Structures and Algorithms cs.MSMathematical Software

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Oct 2017 to Oct 2017.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Left Truncatable Prime 1 comment

    • For what it's worth, here is an implementation of the Miller-Rabin primality test that first tries the smallest 13 primes and then tries some random bases: def is_probable_prime(n, num_random_trials=5): """ An implementation of the Miller-Rabin primality test. If this function…

      svatView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.