Cryptography Reference
In-Depth Information
Because of their importance in cryptographic public key algorithms prime
numbers and their properties have come increasingly to public attention, and it is
a pleasure to see how algorithmic number theory in regard to this and other topics
has become popular as never before. The problems of identifying a number as
prime and the decomposition of a number into its prime factors are the problems
that have attracted the greatest interest. The cryptographic invulnerability of
many public key algorithms (foremost among them the famous RSA procedure)
is based on the fact that factorization is a difficult problem (in the sense of
complexity theory), which at least at present is unsolvable in polynomial time.
7
Until recently, the same held true, in a weakened form, for the identification
of a number as prime if one were looking for a definitive proof that a number is
prime. On the other hand, there are tests that determine, up to a small degree of
uncertainty, whether a number is prime; furthermore, if the test determines that
the number is composite, then that determination is definitive. Such probabilistic
tests are, in compensation for the element of doubt, executable in polynomial
time, and the probability of a “false positive” can be brought below any given
positive bound, as we shall see, by repeating the test a sufficient number of times.
A venerable, but nonetheless still useful, method of determining all primes
up to a given natural number
N
was developed by the Greek philosopher and
astronomer Eratosthenes (276-195
B
.
C
.
E
.; see also [Saga]), and in his honor it is
known as the
sieve of Eratosthenes
. Beginning with a list of all natural numbers
greater than 1 and less than or equal to
N
, we take the first prime number, namely
2, and strike from the list all multiples of 2 greater than 2 itself. The first remaining
number above the prime number just used (2 in this case) is then identified as a
prime
p
, whose multiples
p
(
p
+2
i
)
,
i
= 0
,
1
,...
, are likewise stru
ck
from the
list. This process is continued until a prime number greater than
√
N
is found, at
which point the procedure is terminated. The numbers in the list that have not
been struck are the primes less than or equal to
N
. They have been “caught” in
the sieve.
We would like to elucidate briefly why it is that the sieve of Eratosthenes
works as advertised: First, an induction argument makes it immediately plain
that the next unstruck number above a prime is itself prime, since otherwise,
the number would have a smaller prime divisor and thus would already have
been struck from the list as a multiple of this prime factor. Since only composite
numbers are struck, no prime numbers can be lost in the process.
Fu
rth
ermore, it suffices to strike out only multiples of primes
p
f
or
which
p ≤
√
N
, since if
T
is the smallest proper divisor of
N
, then
T ≤
√
N
. Thus if
a composite number
n ≤ N
were t
o r
emai
n u
nstruck, then this number would
have a smallest prime divisor
p ≤
√
n ≤
√
N
, and
n
would have been struck as a
7
For a discussion of the complexity-theoretic aspects of cryptography one might have a look at
[HKW], Chapter 6, or [Schn], Sections 19.3 and 20.8, and the many further references therein.
One should also read the footnote in the present topic on page 191.
