Cryptography Reference
In-Depth Information
said to be
smooth
if it is the product of only small prime factors. More specifically,
we must say what a “small prime factor” is, and hence one has to define smoothness
with respect to a certain bound
B
. The notion of a
B-smooth
integer is captured in
Definition 3.28.
Definition 3.28 (B-smooth integer)
Let
B
be an integer. An integer
n
is
B-smooth
if every prime factor of
n
is less than
B
.
For example, the integer
n
=4
3
5
2345
17
2
is 18-smooth (because 17 is the
·
·
largest prime factor of
n
).
3.2.6
Euler's Totient Function
Euler's totient function was first proposed by Leonhard Euler
22
as a function that
counts the numbers that are smaller than
n
and have no other common divisor with
n
other than 1 (i.e., they are co-prime with
n
). The function is formally defined as
follows:
φ
(
n
)=
|{
a
∈{
0
,...,n
−
}|
gcd
(
a, n
)=1
}|
1
The Euler's totient function has the following properties:
•
If
p
is prime, then every number smaller than
p
is co-prime with
p
. Conse-
quently, the equation
φ
(
p
)=
p
−
1 holds for every prime number.
p
k
/p
. This is because every
p
th
number between 1 and
p
k
is not co-prime with
p
k
(because
p
is a common
divisor of
p
i
(for
i
=1
,...,k
,then
φ
(
p
k
)=
p
k
•
If
p
is prime and 1
≤
k
∈
Z
−
1)and
p
k
) and we have to subtract
p
k
/p
from
−
p
k
accordingly. Note that
p
k
p
k
/p
=
p
k
p
k−
1
=
p
k−
1
(
p
−
−
−
1), and hence
φ
(
p
k
)=(
p
1)
p
k−
1
(this is the equation that is often found in textbooks).
−
•
If
n
is the product of two primes
p
and
q
(i.e.,
n
=
pq
), then
φ
(
n
)=
φ
(
p
)
φ
(
q
)=(
p
−
1)(
q
−
1). This is because the numbers 0
,p,
2
p,...,
(
q
−
1)
p, q,
2
q,...,
(
p
−
1)
q
are not co-prime with
n
,andthereare1+(
q
−
1) +
(
p
−
1) =
p
+
q
−
1 of these numbers (they are all different from each other if
p
=
q
). Consequently,
φ
(
n
)=
pq
−
(
p
+
q
−
1) =
pq
−
p
−
q
+1 = (
p
−
1)(
q
−
1).
Putting the results together, we can determine
φ
(
n
) for any integer
n
that has
a known prime factorization (i.e.,
n
=
i
q
k
i
):
i
22
Leonhard Euler was a Swiss mathematician who lived from 1707 to 1783.
