Cryptography Reference
In-Depth Information
For completeness we mention that a more complicated analysis shows that the
complexity is actually
2
). The proof of this result is out of the scope of this course
O
(
(see Ref. [112]).
As an important application of the Extended Euclid Algorithm, we can now com-
pute the inversion in
Z
n
: if we want to invert an element
x
in
Z
n
, we run the algo-
rithm with
a
=
x
and
b
=
n
. If the obtained gcd is 1, we get the Bezout relationship
x
−
1
(mod
n
). If the gcd is not 1,
x
and
n
have a com-
1
=
xu
+
n
v
, which means
u
≡
mon factor greater than 1, so
xu
−
qn
also shares this common factor for any
q
∈
Z
,
therefore
xu
mod
n
cannot be equal to 1:
x
is not invertible modulo
n
.
=
As an example, we can invert 22 modulo 35. We run the algorithm with
a
22
and
b
=
35. We obtain the following sequence of vectors.
Iteration
x
y
q
0
(22
,
1
,
0)
(35
,
0
,
1)
0
1
(35
,
0
,
1)
(22
,
1
,
0)
1
2
(22
,
1
,
0)
(13
,
−
1
,
1)
1
3
(13
,
−
1
,
1)
(9
,
2
,
−
1)
1
4
(9
,
2
,
−
1)
(4
,
−
3
,
2)
2
(4
,
−
3
,
2)
(1
,
8
,
−
5)
5
4
(1
,
8
,
−
5)
(0
,
−
35
,
22)
6
Thus 1
=
22
×
8
−
35
×
5, and the inverse of 22 modulo 35 is 8.
6.2.4 The Multiplicative Group Z
n
Let
Z
n
denote the multiplicative group of all invertible elements and let
(
n
) denote its
cardinality (called
Euler totient function
). We can prove the following properties of
Z
n
.
ϕ
Theorem 6.3.
Given an integer n, we have the following results.
Z
n
⇐⇒
1. For all x
∈
Z
n
we have x
∈
gcd(
x
,
n
)
=
1
.
2.
Z
n
is a field if and only if n is prime.
3. For all x
Z
n
we have x
ϕ
(
n
)
∈
≡
1 (mod
n
)
.
,
ϕ
=
→
x
e
4. For any e such that
gcd(
e
(
n
))
1
, then x
mod
n is a permuta-
Z
n
,y
e
−
1
tion on
Z
n
, and for all y
∈
mod
ϕ
(
n
)
mod
n is the only e-th root of y
modulo n
We already proved the first property. For the second one, we recall that
Z
n
is a field
if and only if
Z
n
consists of all nonzero elements of
Z
n
, which means that for any
x
1. This holds if and only if
n
is a prime. For
the third property, we notice that if
x
is a group element of
Z
n
, the Lagrange theorem
says that its order is a factor of the cardinality of the group which is
=
1
,...,
n
−
1, we have gcd(
x
,
n
)
=
ϕ
(
n
). Hence
x
ϕ
(
n
)
1 (mod
n
). The last property consists of solving the
x
e
≡
≡
y
(mod
n
) equation
Search WWH ::
Custom Search