Explicit witnesses Unrefereed

Two strong pseudoprimes to twenty prime bases

Edition 3 · On this site since · last revised · Verify & co-author
Kind
Explicit witnesses and an upper bound
Status
Both factorizations and all strong tests can be checked with exact integers; unrefereed
Prior work
Zhang studied this family; Bleichenbacher gave a 41-digit witness in 1996
On this page
  1. The statement
  2. Check it yourself
  3. What was searched
  4. Prior work

The statement

Let ψ20\psi_{20} be the smallest odd composite that passes the Miller–Rabin strong test for the first 20 prime bases. Two products of the form p(2p−1)p(2p-1) give explicit examples.

pp p(2p−1)p(2p-1)
1113813905784150541 2481162833436289154832260656117034821
1726253494836549181 5959902256870799858089729225626992341

The smaller product is an upper bound on ψ20\psi_{20}. Its minimality remains open.

Check it yourself

Multiply the two factors in either row. For each prime base from 2 through 71, write n−1=2sdn-1=2^s d with dd odd. Check whether bd=1b^d=1 modulo nn or one of the powers with exponents d,2d,…,2s−1dd,\allowbreak 2d,\allowbreak \ldots,\allowbreak 2^{s-1}d equals −1-1 modulo nn. Both products pass every base through 71. At 73 they both fail, although 73n−1=173^{n-1}=1 modulo each. The archive runs these tests and verifies primality certificates for the factors.

What was searched

The search covered one family in a bounded interval. A separate program repeated 64 of its 1,024 parts. The two products can be verified independently of that search. Bleichenbacher’s 1996 dissertation already lists a 41-digit composite passing the first 21 prime bases.

Prior work

Searches run. Full texts of Pratt (1975), Jaeschke (1993), Arnault (1995), Bleichenbacher (1996), Zhang (2007), Sorenson–Webster (2017), and Boltnev (2025) were checked, along with dated searches of OEIS (A014233), arXiv, zbMATH Open, OpenAlex (including citers of Zhang 2007 and Sorenson–Webster 2017), Semantic Scholar, OpenCitations, MathSciNet MR Lookup, CORE, Google Scholar, Zenodo, GitHub, and archived mersenneforum threads. No p(2p−1)p(2p - 1) composite above 103610^{36} passing the first 20 prime bases, and no smaller upper bound on ψ20\psi_{20}, was found in the searches logged.

Still owed. Chinese-language journals including Journal of Anhui Normal University (Natural Science) (unreached across Baidu Scholar, CNKI, Wanfang, Crossref, and rate-limited OpenAlex), Google Scholar's cited-by list for Zhang (2007), Math Stack Exchange and MathOverflow (API-refused), and the full text of Zhang (2010) beyond its abstract and author summary.