Cryptography Reference
In-Depth Information
}
This step is repeated for every prime number not bigger than
√
n
. In our
{
2
,
3
,
5
,
7
,
9
,
11
,
13
,
15
,
17
,
19
example,
√
20
4
.
472. This basically means that the step must be repeated only for
the prime number 3. The following set remains:
≈
{
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
}
What is left is the set of prime numbers less than 20. In this example, the
cardinality of the prime number set is 8. In general, the cardinality of the prime
number set is measured by the prime counting function
π
(
n
). This function is
introduced next.
3.2.4.1
Prime Counting Function
As mentioned earlier, the prime counting function
π
(
n
) counts the number of primes
that are less or equal to
n
∈
N
. This statement can be defined as follows:
π
(
n
):=
|{
p
∈
P
|
p
≤
n
}|
The following table illustrates the first couple of values of the prime counting
function
π
(
n
). Note that the function grows monotonically.
n
23456789 0 1 2 3 4. . .
π
(
n
)
12233444 4 5 5 6 6 . . .
In public key cryptography, one often uses very large prime numbers. Con-
sequently, one may ask whether there are arbitrarily sized prime numbers. This
question can be answered in the affirmative. In fact, it is easy to proof that there
are infinitely many primes. Assume that there are only finitely many primes, and let
them be
p
1
···
p
n
+1. Because
m
is bigger
than any prime, it must be composite, and hence it must be divisible by some prime.
We note, however, that
m
is not divisible by
p
1
,aswhenwedivide
m
by
p
1
we get
the quotient
p
2
···
p
n
. Consider the number
m
=
p
1
···
p
n
and a remainder of 1. Similarly,
m
is not divisible by any
p
i
for
i
=2
,...,n
. Consequently, we get a contradiction and hence the assumption
(i.e., that there are only finitely many primes) must be wrong. This proves that there
are infinitely many primes.
Although there are infinitely many primes, it may still be the case that they
are sparse and that finding a large prime is prohibitively difficult. Consequently, a
