Cryptography Reference
In-Depth Information
Theorem 6.3.1
Let m have the following canonical factorization
m
=
p
e
1
p
e
2
p
e
n
,
·
·
...
·
where the p
i
are distinct prime numbers and e
i
are positive integers,
then
n
i
=1
(
p
e
i
−
p
e
i
−
1
Φ
(
m
)=
)
.
i
Since the value of
n
, i.e., the number of distinct prime factors, is always quite small
even for large numbers
m
, evaluating the product symbol
is computationally easy.
Let's look at an example where we calculate Euler's phi function using the relation:
∏
Example 6.10.
Let
m
= 240. The factorization of 240 in the canonical factorization
form is
p
e
3
There are three distinct prime factors, i.e.,
n
= 3. The value for Euler's phi functions
follows then as:
5 =
p
e
1
p
e
2
15 = 2
4
m
= 240 = 16
·
·
3
·
·
·
(
m
)=(2
4
2
3
)(3
1
3
0
)(5
1
5
0
)=8
Φ
−
−
−
·
2
·
4 = 64
.
That means that 64 integers in the range
are coprime to
m
= 240.
The alternative method, which would have required to evaluate the gcd 240 times,
would have been much slower even for this small number.
{
0
,
1
,...,
239
}
It is important to stress that we need to know the factorization of
m
in order to
calculate Euler's phi function quickly in this manner. As we will see in the next
chapter, this property is at the heart of the RSA public-key scheme: Conversely, if
we know the factorization of a certain number, we can compute Euler's phi function
and decrypt the ciphertext. If we do not know the factorization, we cannot compute
the phi function and, hence, cannot decrypt.
6.3.4 Fermat's Little Theorem and Euler's Theorem
We describe next two theorems which are quite useful in public-key crpytography.
We start with
Fermat's Little Theorem
.
1
The theorem is helpful for primality testing
and in many other aspects of public-key cryptography. The theorem gives a seem-
ingly surprising result if we do exponentiations modulo an integer.
1
You should not confuse this with Fermat's Last Theorem, one of the most famous number-
theoretical problems, which was proved in the 1990s after 350 years.
