Cryptography Reference
In-Depth Information
x
3
=
x
1
−
qx
2
=1+6=7
y
3
=
y
1
−
qy
2
=
−
2
−
6
·
3=
−
20
Finally, we increment
i
and come back to the fourth incarnation of the while-
loop with
i
=3. When we compute
r
3
= 100
·
7+(
−
20)
·
35
we immediately realize that this value equals 0. Consequently, we don't enter the
while-loop anymore, but return (
x, y
)=(
x
2
,y
2
)=(
1
,
3) as the result of the
algorithm. It can easily be verified that this result is correct, because
gcd
(100
,
35) =
5=
−
−
1
·
100 + 3
·
35.
3.2.4
Prime Numbers
Prime numbers (or primes) as formally introduced in Definition 3.26 are frequently
used in mathematics.
16
Definition 3.26 (Prime number)
A natural number
1
<n
∈
N
is called a
prime
number
(or
prime
) if it divisible only by
1
and itself.
that is not prime is called
composite
(note that 1 is neither prime nor composite). In this topic, the set of all
prime numbers is denoted as
Contrary to that, a natural number 1
<n
∈
N
P
.Theset
P
is infinitely large (i.e.,
|
P
|
=
∞
), and its
first 8 elements are 2
,
3
,
5
,
7
,
11
,
13
,
17
,
and 19.
Suppose that you want to find the set that consists of all primes less than a
certain threshold
n
(e.g.,
n
=20). In the third century B.C., Eratosthenes proposed
an algorithm to systematically find these primes, and this algorithm introduced the
notion of a
sieve
. The sieve starts by writing down the set of all natural numbers
between 2 and
n
. In our example
n
=20, this may look as follows:
{
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
10
,
11
,
12
,
13
,
14
,
15
,
16
,
17
,
18
,
19
,
20
}
Next, all numbers bigger than 2 (i.e., the smallest prime) which are multiples
of 2 are removed from the set (this means that all even numbers are removed). The
following set remains:
16
The first recorded definition of a prime was again given by Euclid. There is even some evidence that
the concept of primality was known earlier to Aristotle and Pythagoras.