Two strong pseudoprimes to twenty prime bases
- 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
The statement
Let be the smallest odd composite that passes the Miller–Rabin strong test for the first 20 prime bases. Two products of the form give explicit examples.
| 1113813905784150541 | 2481162833436289154832260656117034821 |
| 1726253494836549181 | 5959902256870799858089729225626992341 |
The smaller product is an upper bound on . Its minimality remains open.
Check it yourself
Multiply the two factors in either row. For each prime base from 2 through 71, write with odd. Check whether modulo or one of the powers with exponents equals modulo . Both products pass every base through 71. At 73 they both fail, although 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 composite above passing the first 20 prime bases, and no smaller upper bound on , was found in the searches logged. On 2026-11-22, a Google Scholar sweep (5 queries) found no prior work stating this claim.
Still owed. Chinese-language journals including Journal of Anhui Normal University (Natural Science) — specifically Xie Ruirui (2011, citation-only record surfaced in the 2026-11-22 Google Scholar sweep) — direct Google Scholar cited-by traversal for Zhang (2007), Math Stack Exchange and MathOverflow (API-refused), and the full text of Zhang (2010) beyond its abstract and author summary.