Wagstaff numbers

Wagstaff numbers are numbers of the form (2p + 1) / 3 for odd prime p. Sometimes the term is used more broadly to include odd composite exponents as well.

If n is even, then the only possible primes of the form 2n + 1 are the Fermat primes. Whereas if n is odd, then 2n + 1 is always divisible by 3.

In the latter case, if the result after division by 3 is prime, this is known as a Wagstaff prime. This can only happen if n itself is prime.

In this way, the very few Fermat primes and the Wagstaff primes form a sort of parallel universe to the Mersenne primes of the form 2p − 1

Exponents of known Wagstaff primes (and probable primes) (43 exponents as of 2019)

The 41st Wagstaff prime (or probable prime) has exponent 4,031,399. It is not yet confirmed that there are no additional undiscovered primes with exponents between 10.3 million and 13,347,311.

Factors of composite Wagstaff numbers

It can be shown that the set of all factors of Wagstaff numbers with prime exponents is disjoint from the set of all factors of Mersenne numbers with prime exponents, except for the improper factor 3 = 22−1 = (23+1)/3.

Factors I know about (2768784 factors as of 2020-03-03, bzip2 format, about 23MB, prime cofactors are omitted)

The lines of this file are ordered according to the usual Primenet convention: the first field (exponent) is ordered numerically, while the second field (factor) is ordered lexicographically (for instance, 100 comes before 20).

Fully-factored composite Wagstaff numbers

In nearly all cases the cofactor that remains after dividing by all known factors is composite. If the cofactor is prime, the Wagstaff number has been fully factored. This prime cofactor, by definition the largest prime factor, is omitted by convention from the list of factors, since most of the time it is extremely large and can be easily computed if necessary.

Relatively few Wagstaff numbers have been fully factored. In the links below we also include cases where the cofactor is merely a probable prime rather than proven prime:

Exponents (265 exponents as of November 2019)

Exponents and factors. The factors are in lexicographical order and the prime cofactor is omitted.

Primality certificates

There is no mathematically-proven test for Wagstaff primes corresponding to the Lucas-Lehmer test for Mersenne primes. Only Wagstaff primes with exponents up to and including 83339 have actually been certified prime, for example with the Primo program. For larger exponents the certification becomes computationally infeasible, so they can only be considered probable primes.

Primality certificates for some Wagstaff primes and some cofactors of fully-factored composite Wagstaff numbers

2048-bit “type 5” residues of Wagstaff numbers (for PRP base 3)

exponents 0M to 4M (complete, for all odd prime exponents in this range; bzip2 format, about 73MB)

exponents 4M to 10M (partial, for only some of the prime exponents in this range, but including all for which there are no known factors; bzip2 format, about 37MB)

exponents above 10M (extends the above to 10.3M; beyond that it is very limited so far, with gaps)

These are values of 3^(2^p) mod (2^p + 1) for odd prime exponents p, with only the last 2048 bits shown. These can be calculated by Prime95/mprime with PRP=1,2,p,1,"3" or PRP=1,2,p,1,99,0,3,5,"3" (but program versions earlier than 29.5 only output the last 64 bits).

Wagstaff primes (or probable primes) have type-5 residue = 9 except for the smallest exponent p = 3, where the residue is 0.

Note the corresponding calculation for Mersenne numbers is 3^(2^p − 2) mod (2^p − 1) calculated with PRP=1,2,p,-1

2048-bit “type 1” residues of Wagstaff numbers (for PRP base 3)

exponents 0M to 1M (complete, for all odd prime exponents in this range; bzip2 format, about 21MB)

These are values of 3^((2^p + 1)/3 − 1) mod (2^p + 1)/3 for odd prime exponents p, with only the last 2048 bits shown. These can be calculated by Prime95/mprime with PRP=1,2,p,1,99,0,3,1,"3" (but program versions earlier than 29.5 only output the last 64 bits).

Wagstaff primes (or probable primes) have type-1 residue = 1 except for the smallest exponent p = 3, where the residue is 0.

In practice, type-1 PRP residues are less useful because the mprime program only performs Gerbicz error checking for type-5 PRP residues.

Note that for Mersenne numbers, type-1 and type-5 PRP residues are the same thing.

Other types of residues

The range 20.19M to 20.20M was tested separately using LLR software, which produces 64-bit residues which are neither type-1 PRP-3 nor type-5 PRP-3. No primes were found in this range.

Gerbicz cofactor-compositeness test

Python script: gerbicz_prp_cofactor.py

As long as one PRP test has been done on a Wagstaff number (or a Mersenne number, or a generalized repunit), and a sufficiently long residue has been recorded (e.g., 2048 bits), then there is very rarely any need to do additional PRP tests on the new cofactors that are created whenever new factors are discovered. Instead, the Gerbicz test can be used to very rapidly determine whether the cofactor is definitely composite or potentially a probable prime. Only in the latter case is a PRP test needed, to confirm that it is indeed a probable prime.

The residue is sufficiently long if the product of all known factors has a bit length smaller than or equal to the bit length of the residue. Residues of 2048 bits should be more than sufficient for many years of future factor discoveries.

It's strongly recommended to install the gmpy2 module for Python, otherwise the speed of the script will be much slower.

For example, try:

./gerbicz_prp_cofactor.py --help
./gerbicz_prp_cofactor.py -r 5 --maxp 5000 --wagstaff WAGSTAFF_FACTORS.txt Wagstaff_2048-bit_type_5_PRP_residues_0M_to_4M.txt
./gerbicz_prp_cofactor.py -r 1 --maxp 5000 --wagstaff WAGSTAFF_FACTORS.txt Wagstaff_2048-bit_type_1_PRP_residues_0M_to_1M.txt

The command lines below test for false negatives (probable prime cofactors incorrectly determined to be composite). There should be no output:

grep -f <(sed -e 's/^/\^/; s/$/,/' WAGSTAFF_FF.txt) WAGSTAFF_FACTORS.txt > /tmp/WAGSTAFF_FACTORS_FF.txt
./gerbicz_prp_cofactor.py -r 5 --verbose --wagstaff /tmp/WAGSTAFF_FACTORS_FF.txt Wagstaff_2048-bit_type_5_PRP_residues_0M_to_4M.txt | grep composite
./gerbicz_prp_cofactor.py -r 1 --verbose --wagstaff /tmp/WAGSTAFF_FACTORS_FF.txt Wagstaff_2048-bit_type_1_PRP_residues_0M_to_1M.txt | grep composite

Miscellaneous

N − 1 method could prove primality of some Wagstaff primes

Because b + 1 either divides bn + 1 if n is odd, or it divides bn − 1 if n is even, we can write:

b/(b+1) * (bn + 1) * (bn − 1) = (b2n+1 + 1)/(b+1) − 1

If W2n+1 is a probable prime, then it can be certified prime via the N − 1 method if W2n+1 − 1 is more than 50% factored. By the above, this will be true if at least one of 2n − 1 or 2n + 1 is either prime or composite but provably fully factored. For example, W2617 can be proven prime in this way, since 21308 − 1 and 21308 + 1 are both fully factored.

However, this method will not be useful in practice. For small exponents we could easily use the ECPP method instead, and for larger exponents it is extremely unlikely that all the necessary conditions can ever be met.

For composite 2n − 1 or 2n + 1, for arbitrary n it is usually very difficult to find all the factors if n is of nontrivial size. And after finding all the factors it would be necessary to prove the cofactor prime and not merely a probable prime. This is infeasible if the cofactor is larger than about 2100,000.

Similarly, for probable prime 2n + 1 it would be necessary to prove that it is actually prime. The same difficulty applies.

The only remaining case is 2n − 1 being prime, where primality is easily proven by Lucas-Lehmer test. In other words, we can look at Mersenne primes whose exponents are Sophie Germain primes (OEIS sequence A065406), and check for the extremely unlikely possibility that the safe prime counterpart happens to be the exponent of a Wagstaff probable prime. Beyond the tiny exponents n = 2, 3, 5 there are no known cases, and worse, the set of Mersenne primes with Sophie Germain exponents is conjectured by Boklan and Conway to be finite. One specific failed example is W86,225,219 which is PRP tested composite, and corresponds to the Mersenne prime M43,112,609.

Wagstaff numbers and Mersenne numbers with the same exponent

The largest currently-known prime exponents for which the Wagstaff number and the Mersenne number are simultaneously fully-factored are 1459, 7417, 8849. Perhaps there is some degree of correlation between the ease of fully factoring Wagstaff numbers and Mersenne numbers that have the same exponent?

Links

The “new Mersenne conjecture”


Home page