Wagstaff prime
Encyclopedia
In number theory
, a Wagstaff prime is a prime number
p of the form
where q is another prime. Wagstaff primes are named after the mathematician
Samuel S. Wagstaff Jr.
; the prime pages
credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes are related to the New Mersenne conjecture and have applications in cryptology.
The first three Wagstaff primes are 3, 11, and 43 because
The first few Wagstaff primes are:
The first exponents q which produce Wagstaff primes or probable prime
s are:
These numbers are proven to be prime for the values of q up to 42737. Those with q > 42737 are probable primes . The primality proof for q = 42737 was performed by François Morain in 2007 with a distributed ECPP
implementation running on several networks of workstations for 743 GHz
-days on an Opteron
processor. It is the fourth largest primality proof by ECPP as of 2010.
The largest currently known probable Wagstaff prime
was found by Tony Reix in February 2010. It has 1,213,572 digits and it is the 3rd biggest PRP ever found at this date.
Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a Wagstaff prime is a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
p of the form
where q is another prime. Wagstaff primes are named after the mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
Samuel S. Wagstaff Jr.
Samuel S. Wagstaff Jr.
Samuel Standfield Wagstaff, Jr. is an American mathematician and computer scientist whose research interests are in the areas of cryptography, parallel computation, and analysis of algorithms, especially number theoretic algorithms...
; the prime pages
Prime pages
The Prime Pages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" lists for primes of various forms...
credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes are related to the New Mersenne conjecture and have applications in cryptology.
The first three Wagstaff primes are 3, 11, and 43 because
The first few Wagstaff primes are:
- 3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, …
The first exponents q which produce Wagstaff primes or probable prime
Probable prime
In number theory, a probable prime is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions...
s are:
- 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, 986191, 4031399, …
These numbers are proven to be prime for the values of q up to 42737. Those with q > 42737 are probable primes . The primality proof for q = 42737 was performed by François Morain in 2007 with a distributed ECPP
Elliptic curve primality proving
Elliptic Curve Primality Proving is a method based on elliptic curves to prove the primality of a number . It is a general-purpose algorithm, meaning it does not depend on the number being of a special form...
implementation running on several networks of workstations for 743 GHz
Hertz
The hertz is the SI unit of frequency defined as the number of cycles per second of a periodic phenomenon. One of its most common uses is the description of the sine wave, particularly those used in radio and audio applications....
-days on an Opteron
Opteron
Opteron is AMD's x86 server and workstation processor line, and was the first processor which supported the AMD64 instruction set architecture . It was released on April 22, 2003 with the SledgeHammer core and was intended to compete in the server and workstation markets, particularly in the same...
processor. It is the fourth largest primality proof by ECPP as of 2010.
The largest currently known probable Wagstaff prime
was found by Tony Reix in February 2010. It has 1,213,572 digits and it is the 3rd biggest PRP ever found at this date.
Currently, the fastest algorithm for proving the primality of Wagstaff numbers is ECPP.
External links
- Chris Caldwell, The Top Twenty: Wagstaff at The Prime PagesPrime pagesThe Prime Pages is a website about prime numbers maintained by Chris Caldwell at the University of Tennessee at Martin.The site maintains the list of the "5,000 largest known primes", selected smaller primes of special forms, and many "top twenty" lists for primes of various forms...
. - Renaud Lifchitz, "An efficient probable prime test for numbers of the form (2p + 1)/3".
- Tony Reix, "Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under x2 − 2 modulo a prime".