Cryptography Reference
In-Depth Information
> iquo(25,7,'r'), r;
3, 4
shows that the quotient of dividing 25 by 7 is 3 and the remainder is 4. The quotient is
the output of the function and the remainder is stored in the variable
'r'
. Similarly,
if we compute
> irem(25,7,'q'), q;
4, 3
we obtain as output the remainder and the quotient is stored in the variable
'q'
.
We recall the definition of a prime number, a concept that plays an important role
in modern cryptography:
Definition 2.7
An integer
p
is called a
prime number
if
p
1 and the only positive
integers dividing
p
are 1 and
p
.A
composite number
is an integer greater than 1 that
is not prime.
>
,
,
,
,
,
,...
and there are arbitrarily large primes
because, as Euclid already knew more than 2300 years ago (Elements,
Proposition 20), the number of primes is infinite [194]. Another important fact that
Euclid also knew is:
The first primes are 2
3
5
7
11
13
Theorem 2.2
(The fundamental theorem of arithmetic)
Let a
>
1
be an integer.
p
e
1
p
e
2
p
e
k
k
Then a can be written as a product, a
=
···
, with p
i
prime and e
i
≥
1
for i
k. Furthermore, this factorization in prime powers is unique if the
primes are written in increasing order.
=
1
,...,
As we shall see, the problem of finding the prime factorization of a large integer
is thought to be computationally hard and this fact turns out to be very useful for
cryptography.
2.2.1 Representation of Integers
The usual method that we use to represent integers is by means of their decimal
expansion. But computers work naturally with the binary expansion and any integer
b
1 can be used as the
base
of a number system. These representations rely on
the following theorem in which we use the notation
>
to denote the
floor
of a real
number
x
, i.e., the greatest integer less than or equal to
x
.
x
Theorem 2.3
(Positional representation of numbers)
Let b
1
be an integer. Then
each positive integer n has a unique representation in the form
>
k
−
1
d
i
b
i
n
=
,
i
=
0
