Wagstaff prime

From Wikipedia, the free encyclopedia

A Wagstaff prime is a prime number p of the form

$p={{2^q+1}\over 3}$

where q is another prime. For example, the first 3 Wagstaff primes are 3, 11, and 43 because

$3={{2^3+1}\over 3},$

$11={{2^5+1}\over 3},$

and

$43={{2^7+1}\over 3}.$

Wagstaff primes are related to the New Mersenne conjecture. The first few Wagstaff primes (sequence A000979 in OEIS) are:

3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403.

The first exponents q which produce Wagstaff primes or probable primes are (A000978):

3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 79, 101, 127, 167, 191, 199, 313, 347, 701, 1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737, 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321.

Wagstaff primes are named after mathematician Samuel S. Wagstaff Jr. and have applications in cryptology. The prime pages credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference.