Cryptography Reference
In-Depth Information
10.5 A Primality Test
Primes is in P
—M. Agrawa, N. Kaval, N. Saxena, 2002
Not to stretch out the suspense, the largest known Mersenne prime,
M
11213
,
and, I believe, the largest prime known at present, has 3375 digits and is
therefore just about T-281
4
.
6
—Isaac Asimov,
Adding a Dimension
, 1964
Forty-First Known Mersenne Prime Found!!
The study of prime numbers and their properties is one of the oldest branches of
number theory and one of fundamental significance for cryptography. From the
seemingly harmless definition of a prime number as a natural number greater
than 1 that has no divisors other than itself and 1 there arises a host of questions
and problems with which mathematicians have been grappling for centuries and
many of which remain unanswered and unsolved to this day. Examples of such
questions are, “Are there infinitely many primes?” “How are the primes distributed
among the natural numbers?” “How can one tell whether a number is prime?”
“How can one identify a natural number that is not prime, that is, a number that
is composite?” “How does one find all the prime factors of a composite number?”
That there are infinitely many primes was proven already by Euclid about
2300 years ago (see, for example, [Bund], page 5, and especially the amusing proof
variant and the serious proof variant on pages 39 and 40). Another important
fact, which up to now we have tacitly assumed, will be mentioned here explicitly:
The fundamental theorem of arithmetic states that every natural number greater
than 1 has a unique decomposition as a product of finitely many prime numbers,
where the uniqueness is up to the order of the factors. Thus prime numbers are
truly the building blocks of the natural numbers.
As long as we stick close to home in the natural numbers and do not stray
among numbers that are too big for us to deal with easily we can approach a
number of questions empirically and carry out concrete calculations. Take note,
however, that the degree to which results are achievable depends in large measure
on the efficiency of the algorithms used and the capacities of available computers.
Tisfor
trillion
, whereby Asimov denotes the order of magnitude
10
12
. Thus T-281
4
stands for
10
12
·
281
.
25
=10
3375
6
2
11211
.
5
.
≈
