Cryptography Reference
In-Depth Information
A list of the largest numbers identified as prime, published on the Internet,
demonstrates the impressive size of the most recent discoveries (see Table 10-1
Table 10-1. The ten largest known primes (as of December 2004)
Prime
Digits
Discoverer
Year
2
24 036 583
−
1
7 235 733
Findley
2004
2
20 996 011
−
1
6 320 430
Shafer
2003
2
13 466 917
−
1
4 053 946
Cameron, Kurowski
2001
2
6 972 593
−
1
2 098 960
Hajratwala, Woltman, Kurowski
1999
2
5 054 502
+1
5 539
·
1 521 561
Sundquist
2003
2
3 021 377
−
1
909 526
Clarkson, Woltman, Kurowski
1998
2
2 976 221
−
1
895 932
Spence, Woltman
1997
1 372 930
131 072
+1
804 474
Heuer
2003
1 361 244
131 072
+1
803 988
Heuer
2004
1 176 694
131 072
+1
795 695
Heuer
2003
The largest known prime numbers are of the form
2
p
−
1
. Primes that can be
represented in this way are called
Mersenne
primes, named for Marin Mersenne
(1588-1648), who discovered this particular structure of prime numbers in his
search for perfect numbers. (A natural number is said to be
perfect
if it equals
the sum of its proper divisors. Thus, for example,
496
is a perfect number, since
496=1+2+4+8+16+31+62+124+248
.)
For every divisor
t
of
p
we have that
2
t
−
1
is a divisor of
2
p
−
1
, since if
p
=
ab
,then
−
1)
2
a
(
b
−
1)
+2
a
(
b
−
2)
+
···
+1
.
2
p
−
1=(2
a
Therefore, we see that
2
p
−
1
canbeprimeonlyif
p
is prime. Mersenne himself
announced in 1644, without being in possession of a complete proof, that
for
p
257
theonlyprimesoftheform
2
p
≤
−
1
were those for the primes
p ∈{
2
,
3
,
5
,
7
,
13
,
17
,
19
,
31
,
67
,
127
,
257
}
. With the exception of
p
=67
and
p
= 257
, for which
2
p
1
is not prime, Mersenne's conjecture has been verified,
and analogous results for many additional exponents have been established as
well (see [Knut], Section 4.5.4, and [Bund], Section 3.2.12).
On the basis of the discoveries thus far of Mersenne primes one may
conjecture that there exist Mersenne primes for infinitely many prime numbers
p
. However, there is as yet no proof of this conjecture (see [Rose], Section 1.2).
An interesting overview of additional unsolved problems in the realm of prime
numbers can be found in [Rose], Chapter 12.
−
