Cryptography Reference
In-Depth Information
somehow related question asks for the density of prime numbers. How likely does
an interval of a given size comprise a prime number? We can use the prime density
theorem addressed next to answer questions of this type.
3.2.4.2
Prime Density Theorem
Theorem 3.4 is called the
prime density theorem
. It says that arbitrarily sized prime
numbers do in fact exist, and that finding them is not difficult (even for very large
numbers). We give the theorem without a proof.
Theorem 3.4 (Prime density theorem)
π
(
n
)ln(
n
)
n
lim
n→∞
=1
In essence, the prime density theorem says that for sufficiently large
n
the
value
π
(
n
) is about
n/
ln(
n
) and that roughly every ln(
n
)
th
number of the size of
n
is prime. For example, ln(10
100
)
230. This means that about 1 in 230 (115)
integers (odd integers) with 100 decimal digits is a prime. More specifically, it is
known that
≈
n
ln(
n
)
π
(
n
)
≥
for 2
<n
∈
N
and that
n
ln(
n
)
π
(
n
)
≤
1
.
10555
≤
n
∈
N
. Consequently,
π
(
n
)
≈
n/
ln(
n
) is indeed a very good approxima-
for 17
tion for almost all
n
∈
N
.
There are several open conjectures on prime numbers. For example, it is
conjectured that there exist infinitely many twin primes (i.e., primes
p
for which
p
+2is also prime), and that every even number is the sum of two primes. We don't
elaborate on these issues in this topic.
3.2.4.3
Generating Large Primes
In cryptographic applications, one often needs large primes, and there are two
methods for generating them:
