Wagstaff prime
   HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, a Wagstaff prime is a
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
of the form : where ''p'' is an odd prime. Wagstaff primes are named after the mathematician Samuel S. Wagstaff Jr.; the
prime pages The PrimePages is a website about prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is ...
credit François Morain for naming them in a lecture at the Eurocrypt 1990 conference. Wagstaff primes appear in the New Mersenne conjecture and have applications in
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
.


Examples

The first three Wagstaff primes are 3, 11, and 43 because :\begin 3 & = , \\ pt11 & = , \\ pt43 & = . \end


Known Wagstaff primes

The first few Wagstaff primes are: :3, 11, 43, 683, 2731, 43691, 174763, 2796203, 715827883, 2932031007403, 768614336404564651, ... Exponents which produce Wagstaff primes or
probable prime In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific co ...
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, ...


Generalizations

It is natural to consider more generally numbers of the form :Q(b,n)=\frac where the base b \ge 2. Since for n odd we have :\frac=\frac=R_n(-b) these numbers are called "Wagstaff numbers base b", and sometimes consideredRepunit
Wolfram MathWorld (Eric W. Weisstein) a case of the repunit numbers with negative base -b. For some specific values of b, all Q(b,n) (with a possible exception for very small n) are composite because of an "algebraic" factorization. Specifically, if b has the form of a perfect power with odd exponent (like 8, 27, 32, 64, 125, 128, 216, 243, 343, 512, 729, 1000, etc. ), then the fact that x^m+1, with m odd, is divisible by x+1 shows that Q(a^m, n) is divisible by a^n+1 in these special cases. Another case is b=4k^4, with ''k'' a positive integer (like 4, 64, 324, 1024, 2500, 5184, etc. ), where we have the aurifeuillean factorization. However, when b does not admit an algebraic factorization, it is
conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
d that an infinite number of n values make Q(b,n) prime, notice all n are odd primes. For b=10, the primes themselves have the following appearance: 9091, 909091, 909090909090909091, 909090909090909090909090909091, … , and these ''n''s are: 5, 7, 19, 31, 53, 67, 293, 641, 2137, 3011, 268207, ... . See Repunit#Repunit primes for the list of the generalized Wagstaff primes base b. (Generalized Wagstaff primes base b are generalized repunit primes base -b with odd n) The least primes ''p'' such that Q(n, p) is prime are (starts with ''n'' = 2, 0 if no such ''p'' exists) :3, 3, 3, 5, 3, 3, 0, 3, 5, 5, 5, 3, 7, 3, 3, 7, 3, 17, 5, 3, 3, 11, 7, 3, 11, 0, 3, 7, 139, 109, 0, 5, 3, 11, 31, 5, 5, 3, 53, 17, 3, 5, 7, 103, 7, 5, 5, 7, 1153, 3, 7, 21943, 7, 3, 37, 53, 3, 17, 3, 7, 11, 3, 0, 19, 7, 3, 757, 11, 3, 5, 3, ... The least bases ''b'' such that Q(b, prime(n)) is prime are (starts with ''n'' = 2) :2, 2, 2, 2, 2, 2, 2, 2, 7, 2, 16, 61, 2, 6, 10, 6, 2, 5, 46, 18, 2, 49, 16, 70, 2, 5, 6, 12, 92, 2, 48, 89, 30, 16, 147, 19, 19, 2, 16, 11, 289, 2, 12, 52, 2, 66, 9, 22, 5, 489, 69, 137, 16, 36, 96, 76, 117, 26, 3, ...


References


External links

* *Chris Caldwell
''The Top Twenty: Wagstaff''
at The
Prime Pages The PrimePages is a website about prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is ...
. * Renaud Lifchitz
''p'' + 1)/3"">"An efficient probable prime test for numbers of the form (2''p'' + 1)/3"
* Tony Reix
2 − 2 modulo a prime"">"Three conjectures about primality testing for Mersenne, Wagstaff and Fermat numbers based on cycles of the Digraph under ''x''2 − 2 modulo a prime"

List of Wagstaff primes base 2 to 160
{{Prime number classes, state=collapsed Classes of prime numbers Eponymous numbers in mathematics Unsolved problems in number theory