🔢 mathematics

Three Brillhart-Lehmer-Selfridge primality proofs for Wagstaff numbers

This paper presents fully verified, classical $N-1$ primality proofs for the Wagstaff numbers $W_{2617}$ , $W_{10501}$ , and $W_{12391}$ using the Brillhart-Lehmer-Selfridge criterion and cyclotomic factorizations, thereby establishing their primality independently of elliptic-curve methods and unproven conjectures.

Original authors: Alexey Dolotov

Published 2026-05-19

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexey Dolotov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to prove that a specific, incredibly large number is truly "prime" (meaning it can only be divided by 1 and itself). In the world of mathematics, these numbers are like giant, intricate lockboxes. Most of the time, to prove a lockbox is unbreakable, mathematicians use a high-tech, complex method called ECPP (Elliptic Curve Primality Proving). It's like using a supercomputer to simulate a quantum physics experiment to check the lock. It works, but it's heavy, complicated, and hard for others to double-check quickly.

This paper by Alexey Dolotov presents a different approach. The author proves that three specific giant numbers (called Wagstaff numbers) are prime, but instead of using the heavy quantum-style tools, he uses a classic, "old-school" method called BLS (Brillhart–Lehmer–Selfridge).

Here is the breakdown of what the paper does, using simple analogies:

1. The Target: The Wagstaff Numbers

Think of Wagstaff numbers as a special family of numbers related to the famous Mersenne numbers (which are used to find the largest known primes). They are defined by a simple recipe: take a prime number $p$ , calculate $2^p + 1$ , and divide by 3.
The paper focuses on three specific "giants" in this family:

W2617 (a number with 788 digits)
W10501 (a number with 3,161 digits)
W12391 (a number with 3,730 digits)

Everyone already suspected these were prime, but the proof relied on the heavy ECPP method. This paper says, "Let's prove it again using a lighter, more transparent method."

2. The Method: The "N-1" Puzzle

The BLS method works like a puzzle. To prove a number $N$ is prime, you don't have to check every single number up to $N$ . Instead, you look at the number $N - 1$ .

Imagine $N - 1$ is a long chain of links. If you can find a big chunk of that chain that is fully factored (meaning you know exactly which small prime numbers make up that chunk), and that chunk is big enough (specifically, bigger than the cube root of $N$ ), you can mathematically prove the whole number $N$ is prime.

The Challenge: For these giant Wagstaff numbers, $N-1$ is a massive chain. Usually, most of the links are hidden or unknown.
The Trick: The author realized that $N-1$ for these numbers comes from a specific mathematical structure called cyclotomic decomposition. It's like knowing that the chain is made of specific types of links (called $\Phi_d(2)$ ).
The Harvest: The author went to existing "libraries" of math data (the Cunningham Project tables and FactorDB) to find the links that were already known. For the rest, he used computer algorithms to break them down.

3. The Verification: The "Gold Standard" Check

Once the author found a big enough chunk of the chain (the "factored portion"), he had to prove that every single small prime link inside that chunk was actually prime.

He didn't just guess. He used a rigorous, unbreakable method called APR-CL to certify every single small prime.
Think of this as a notary public stamping every single brick in a wall before declaring the wall safe.

4. The Double-Check: The "Magic Mirror"

To make sure his computer code didn't have a glitch, the author added a second, independent check.

He used a different mathematical system involving square roots of 2 (called $\mathbb{Z}[\sqrt{2}]$ ).
He checked a specific mathematical "congruence" (a fancy way of saying a pattern match) that must happen if the number is prime.
This is like checking your work by solving the problem backwards. If the pattern matches, it confirms the math was done correctly.

5. The Results

The paper successfully proves that W2617, W10501, and W12391 are prime.

Why is this special? These proofs are "unconditional," meaning they don't rely on unproven guesses. They are also "independent," meaning they don't use the heavy ECPP method that everyone else uses.
The Limit: The author explains that this method only works if the number $p-1$ is "smooth" (meaning it breaks down into small, known pieces easily). He checked all other known Wagstaff candidates and found that for almost all of them, the chain has a giant, unbreakable link that makes this specific method impossible to use right now. Only these three numbers were "smooth" enough to be solved this way.

Summary

Alexey Dolotov took three giant numbers that were already believed to be prime and proved them using a classic, transparent, and highly verifiable method. He didn't just say "it's prime"; he built a complete, step-by-step certificate that anyone can run on their own computer to verify the result. It's a "cleaner" proof that stands on its own, independent of the more complex methods usually used for these giants.

Technical Summary: Three Brillhart–Lehmer–Selfridge Primality Proofs for Wagstaff Numbers

Problem Statement
The paper addresses the verification of primality for Wagstaff numbers, defined as $W_p = (2^p + 1)/3$ for odd primes $p$ . While Mersenne numbers ( $M_p = 2^p - 1$ ) possess a deterministic, standalone primality test (the Lucas–Lehmer test), no comparable deterministic test exists for Wagstaff numbers. Existing proofs for Wagstaff numbers with large exponents (specifically $p \ge 2617$ ) rely on the Elliptic Curve Primality Proving (ECPP) algorithm of Atkin–Morain. Although Chebyshev/Lucas-type congruences (specifically the Chua framework condition $\omega_3^{(W_p+1)/2} \equiv -1 \pmod{W_p}$ ) are known necessary conditions for Wagstaff primality, their sufficiency remains conjectural. Consequently, there is a need for unconditional primality proofs for large Wagstaff numbers that do not depend on ECPP or unproven conjectures.

Methodology
The authors present unconditional primality proofs for three specific Wagstaff numbers: $W_{2617}$ , $W_{10501}$ , and $W_{12391}$ . The methodology relies exclusively on the classical Brillhart–Lehmer–Selfridge (BLS) $N-1$ criterion, which requires that a significant portion of $N-1$ be completely factored.

Cyclotomic Decomposition: The proofs utilize the factorization of $N-1 = W_p - 1 = \frac{2(2^{p-1}-1)}{3}$ . The term $2^{p-1}-1$ is decomposed into cyclotomic polynomials: $2^{p-1}-1 = \prod_{d|p-1} \Phi_d(2)$ .
Factored Portion ( $F$ ): The authors harvest known factorizations of these cyclotomic factors $\Phi_d(2)$ from the Cunningham project tables and FactorDB. Any retrieved factors are re-certified for primality using the APR-CL (Adleman–Pomerance–Rumely / Cohen–Lenstra) algorithm.
BLS Criterion Application: The proofs establish a factored portion $F$ of $N-1$ such that $F^3 > N$ (exceeding the $N^{1/3}$ threshold). For each prime factor $q$ of $F$ , a Fermat-type witness $a_q$ is found satisfying $a_q^{N-1} \equiv 1 \pmod N$ and $\gcd(a_q^{(N-1)/q}-1, N) = 1$ . The discriminant $\Delta = s^2 - 8m$ (derived from $N = mF + s + 1$) is verified to be non-square.
Independent Verification: As an auxiliary check on the implementation of arithmetic in the ring $\mathbb{Z}[\sqrt{2}]$ , the authors verify the Chua congruence $\omega_3^{(W_p+1)/2} \equiv -1 \pmod{W_p}$ for each target. This serves as a cross-substrate check distinct from the integer-only BLS arithmetic but is not used to deduce primality.

Key Contributions

Unconditional Proofs: The paper provides the first published BLS-based primality proofs for $W_{2617}$ , $W_{10501}$ , and $W_{12391}$ , independent of ECPP.
Methodological Demonstration: It demonstrates the feasibility of applying the BLS $N-1$ framework to Wagstaff numbers by leveraging the cyclotomic decomposition of $2^{p-1}-1$ . This approach is shown to be viable for exponents where $p-1$ is sufficiently smooth to allow the factorization of enough cyclotomic factors.
Auditability: The proofs are designed for high auditability. The certificates are compact JSON records containing witnesses and discriminant checks. Verification requires only standard modular exponentiations and APR-CL checks, avoiding the complex elliptic curve evaluations required by ECPP.
Reproducibility: All computations are reproducible using open-source software (Python, SymPy, PARI/GP, gmpy2). Full driver scripts, logs, and certificates are archived on Zenodo.

Results
The paper successfully proves the primality of:

$W_{2617}$ : A 788-digit number. The factored portion $F$ exceeds $N^{1/3}$ by 46 bits, utilizing 22 distinct prime factors.
$W_{10501}$ : A 3,161-digit number. The factored portion exceeds the threshold by 3,261 bits, utilizing 103 distinct prime factors.
$W_{12391}$ : A 3,730-digit number. The factored portion exceeds the threshold by 2,860 bits, utilizing 61 distinct prime factors.

For each proof, every prime factor in the factored portion $F$ was certified unconditionally via APR-CL. The Chua congruence was verified for all three numbers as a consistency check.

Significance and Limitations
The paper claims significance primarily in the realm of auditability and methodological diversity. It offers an independent confirmation of the primality of these specific numbers, distinct from the ECPP proofs currently recorded in the Caldwell/Wagstaff-project archives.

The authors are modest regarding the scope of the method. They explicitly note that the BLS $N-1$ approach is limited by the smoothness of $p-1$ . An analysis of known Wagstaff primes and probable primes up to $p = 267,017$ reveals that only $p=10501$ and $p=12391$ (along with the smaller $p=2617$ ) possess $p-1$ structures smooth enough to yield a factored portion $F$ large enough for the BLS criterion with current factorization data. For other exponents, large prime factors in $p-1$ lead to unfactored cyclotomic components $\Phi_d(2)$ that are currently out of reach for general-purpose factorization. Thus, the paper does not propose a general solution for all Wagstaff numbers but rather establishes a rigorous, non-ECCPP proof path for a specific, constrained subset of exponents.