Cryptography Reference
In-Depth Information
interested in the (at the moment seemingly odd) problem of knowing
how many
numbers in this set are relatively prime to
m
. This quantity is given by
Euler's phi
function
, which is defined as follows:
Definition 6.3.1
Euler's Phi Function
The number of integers in
Z
m
relatively prime to m is denoted by
Φ
(
m
)
.
We first look at some examples and calculate Euler's phi function by actually
counting all the integers in
Z
m
which are relatively prime.
Example 6.8.
Let
m
= 6. The associated set is
Z
6
=
{
0
,
1
,
2
,
3
,
4
,
5
}
.
gcd(0
,
6)=6
gcd(1
,
6)=1
gcd(2
,
6)=2
gcd(3
,
6)=3
gcd(4
,
6)=2
gcd(5
,
6)=1
Since there are two numbers in the set which are relatively prime to 6, namely 1 and
5, the phi function takes the value 2, i.e.,
Φ
(6)=2.
Here is another example:
Example 6.9.
Let
m
= 5. The associated set is
Z
5
=
{
0
,
1
,
2
,
3
,
4
}
.
gcd(0
,
5)=5
gcd(1
,
5)=1
gcd(2
,
5)=1
gcd(3
,
5)=1
gcd(4
,
5)=1
This time we have four numbers which are relatively prime to 5, hence,
Φ
(5)=4.
From the examples above we can guess that calculating Euler's phi function by
running through all elements and computing the gcd is extremely slow if the num-
bers are large. In fact, computing Euler's phi function in this naıve way is com-
pletely out of reach for the large numbers occurring in public-key cryptography.
Fortunately, there exists a relation to calculate it much more easily if we know the
factorization of
m
, which is given in following theorem.
