A composite number that passes the Baillie–PSW test

The Baillie–PSW test calls an odd number "probably prime" when it passes a strong Fermat test to base 2 and a strong Lucas test. It is fast and is used in computer algebra systems such as Maple and SageMath, yet in more than forty years nobody has found a composite number that passes it. The task is to find one.

Problem

Let $n > 1$ be odd.

• Strong Fermat test to base 2. Write $n - 1 = d \cdot 2^s$ with $d$ odd. The number $n$ passes if $2^d \equiv 1 \pmod n$, or $2^{d \cdot 2^r} \equiv -1 \pmod n$ for some $0 \le r < s$.
• Strong Lucas test (Selfridge's method A). Let $D$ be the first term of $5, -7, 9, -11, 13, \dots$ whose Jacobi symbol $\left(\frac{D}{n}\right)$ equals $-1$ (no such $D$ exists when $n$ is a perfect square, so squares are excluded first). Put $P = 1$ and $Q = (1 - D)/4$, and define the Lucas sequences $U_0 = 0$, $U_1 = 1$, $V_0 = 2$, $V_1 = P$, with $W_k = P W_{k-1} - Q W_{k-2}$ for $W \in \{U, V\}$. Write $n + 1 = e \cdot 2^t$ with $e$ odd. The number $n$ passes if $U_e \equiv 0 \pmod n$, or $V_{e \cdot 2^r} \equiv 0 \pmod n$ for some $0 \le r < t$.

Task. Find an odd composite $n$ that passes both tests (a Baillie–PSW pseudoprime), or prove that none exists.

Background

The combined test first appeared in 1980 in a paper of Pomerance, Selfridge and Wagstaff, whose exhaustive search found no composite number below $25 \cdot 10^9$ passing both parts; the idea of combining the two tests originated with Baillie [2, 3], and Baillie and Wagstaff analysed the Lucas side [1]. Each test on its own is passed by some composites (OEIS A001262 and A217255); the hope behind the combination is that the two kinds of failure rarely meet. In a 1984 note Pomerance argued heuristically that they do meet: the number of counterexamples up to $x$ should exceed $x^{1-\varepsilon}$ for every $\varepsilon > 0$ [3]. So counterexamples are expected to exist, but they have never been seen.

What is known

• No Baillie–PSW pseudoprime exists below $2^{64}$, by exhaustive computation (as stated by Epoch).
• Pomerance's heuristic predicts more than $x^{1-\varepsilon}$ counterexamples up to $x$ [3].
• Baillie, Fiori and Wagstaff (2021) strengthened the test at almost no extra cost by adding a check on what they call Lucas-V pseudoprimes, of which there are only five below $10^{15}$ [4].

What would count as progress

• An odd composite $n$ together with a factorisation $n = ab$, $a, b > 1$, such that $n$ passes both tests. Checking takes milliseconds with arbitrary-precision arithmetic.
• Epoch's verifier takes two integers greater than 1 and runs both tests exactly on their product, with no size limit.
• A method that produces many such numbers would be stronger still; a proof that none exist would settle the question the other way.

References

1. R. Baillie and S. S. Wagstaff Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6
2. C. Pomerance, J. L. Selfridge and S. S. Wagstaff Jr., The pseudoprimes to $25 \cdot 10^9$, Math. Comp. 35 (1980), 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7
3. C. Pomerance, Are there counter-examples to the Baillie–PSW primality test?, 1984. math.dartmouth.edu/~carlp/dopo.pdf
4. R. Baillie, A. Fiori and S. S. Wagstaff Jr., Strengthening the Baillie-PSW primality test, Math. Comp. 90 (2021), 1931–1955. doi:10.1090/mcom/3616

Source

Imported from FrontierMath: Open Problems, baillie-psw, curated by Epoch AI. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.