Cryptography Reference
In-Depth Information
φ
(
n
)=
i
1)
q
k
i
−
1
i
(
q
i
−
For example, in order to compute
φ
(45) we compute the factorization 45 =
3
2
·
5 and apply the formula given earlier. In fact, we have
3
2
−
1
1)
1
−
1
φ
(45)
−
·
·
−
=
(3
1)
(5
3
1
5
0
=2
·
·
4
·
=2
·
3
·
4
·
1
=24
.
A final word is due to the difficulty of computing
φ
(
n
) as compared to finding
the factorization of
n
. For simplicity, we assume
n
to be the product of two primes
p
and
q
(i.e.,
n
=
pq
). In this case, we can show that computing
φ
(
n
) is equally
difficult to finding
p
and
q
. This means that if we can compute
φ
(
n
) for any
n
,then
we can also factor
n
.
Starting with
φ
(
pq
)=(
p
−
1)(
q
−
1) =
pq
−
(
p
+
q
)+1=
n
−
(
p
+
q
)+1,
we can state (3.3):
p
+
q
=
n
−
φ
(
pq
)+1
(3.3)
q
)
2
=
p
2
2
pq
+
q
2
=
p
2
+2
pq
+
On the other hand, we can state that (
p
−
−
q
2
4
pq
=(
p
+
q
)
2
4
pq
=(
p
+
q
)
2
−
−
−
4
n
. Computing the square root on either side
q
=
(
p
+
q
)
2
of this equation, we get
p
4
n
. In this equation, we can substitute
p
+
q
with the right side of (3.3). The result is (3.4):
−
−
q
=
(
n
p
−
−
φ
(
pq
)+1)
2
−
4
n
(3.4)
By adding (3.3) and (3.4), we get the following formula to compute (
p
+
q
)+
(
p
−
q
)=
p
+
q
+
p
−
q
=2
p
:
φ
(
pq
)+1+
(
n
2
p
=
n
−
−
φ
(
pq
)+1)
2
−
4
n
