Two algorithms to find primes in patterns

DOI10.1090/MCOM/3501MaRDI QIDQ4960081zbMATH OpenOpenAlexFDO

Authors Jonathan Webster, Jonathan P. Sorenson

Publication date 8 April 2020

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

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

zbMATH Keywords

primesprimality teststwin primesCunningham chainsprime sievesprime patternsquadruplets primes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Primes (11A41) Primality (11Y11)

Abstract: Let $kge1$ be an integer, and let $P=(f_1(x),ldots,f_k(x))$ be $k$ admissible linear polynomials over the integers, or extit{the pattern}. We present two algorithms that find all integers $x$ where $max{f}_i(x)len$ and all the $f_i(x)$ are prime. Our first algorithm takes at most $O_P(n/(loglogn{)}^k)$ arithmetic operations using $O(ksqrtn)$ space. Our second algorithm takes slightly more time, $O_P(n/(loglogn{)}^{k-1})$ arithmetic operations, but uses only $n^{1/c}$ space for a constant $c>2$. We prove correctness unconditionally, but the running time relies on two unproven but reasonable conjectures. We are unaware of any previous complexity results for this problem beyond the use of a prime sieve. We also implemented several parallel versions of our second algorithm to show it is viable in practice. In particular, we found some new Cunningham chains of length 15, and we found all quadruplet primes up to $10^{17}$.

Recommendations

• Constructing finite field extensions with large order elements
• Testing numbers of the form for primality
• Constructing Finite Field Extensions with Large Order Elements
• scientific article; zbMATH DE number 917769
• A sublinear additive sieve for finding prime number
• Primality tests and factorization algorithms. I
• A space-efficient fast prime number sieve
• Decision problem \texttt{PRIMES}
• scientific article; zbMATH DE number 7556735

Cites work

• scientific article; zbMATH DE number 1643933 (Why is no real title available?)
• scientific article; zbMATH DE number 1186944 (Why is no real title available?)
• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 3467229 (Why is no real title available?)
• scientific article; zbMATH DE number 1259076 (Why is no real title available?)
• scientific article; zbMATH DE number 2154272 (Why is no real title available?)
• A Heuristic Asymptotic Formula Concerning the Distribution of Prime Numbers
• Algorithmic Number Theory
• Algorithmic Number Theory
• An improved sieve of Eratosthenes
• Approximate formulas for some functions of prime numbers
• Bounded gaps between primes
• Integers free of small prime factors in arithmetic progressions
• Long Chains of Nearly Doubled Primes
• On the Distribution of Pseudoprimes
• PRIMES is in P
• Primality testing with Gaussian periods
• Prime clusters and Cunningham chains
• Prime numbers and computer methods for factorization.
• Prime sieves using binary quadratic forms
• Riemann's hypothesis and tests for primality
• Sieving for pseudosquares and pseudocubes in parallel using doubly-focused enumeration and wheel datastructures
• Some results on pseudosquares
• Statistical Evidence for Small Generating Sets
• Strong pseudoprimes to twelve prime bases
• Sur certaines hypothèses concernant les nombres premiers
• Unsolved problems in number theory

Cited in

(4)

• An algorithm and computation to verify Legendre's conjecture up to \(7\cdot 10^{13}\)
• scientific article; zbMATH DE number 1194296 (Why is no real title available?)
• Sieving for large twin primes and Cunningham chains of length 2 of the second kind
• scientific article; zbMATH DE number 1078084 (Why is no real title available?)

This page was built for publication: Two algorithms to find primes in patterns

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