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.
Search WWH ::




Custom Search