Cryptography Reference
In-Depth Information
s
(
x
) 0 +
t
(
x
)
A
(
x
)
≡
1mod
P
(
x
)
A
−
1
(
x
) mod
P
(
x
)
t
(
x
)
≡
We give at this point an example of the algorithm for the small field
GF
(2
3
).
Example 6.7.
We are looking for the inverse of
A
(
x
)=
x
2
in the finite field
GF
(2
3
)
with
P
(
x
)=
x
3
+
x
+ 1. The initial values for the
t
(
x
) polynomial are:
t
0
(
x
)=0,
t
1
(
x
)=1
Iteration
r
i
−
2
(
x
)=[
q
i
−
1
(
x
)]
r
i
−
1
(
x
)+[
r
i
(
x
)]
t
i
(
x
)
2
x
3
+
x
+ 1 =[
x
]
x
2
+[
x
+ 1]
t
2
=
t
0
−
q
1
t
1
= 0
−
x
1
≡
x
x
2
1 +
x
2
3
=[
x
](
x
+ 1)+[
x
]
t
3
=
t
1
−
q
2
t
2
= 1
−
x
(
x
)
≡
1 (1 +
x
2
)
4
x
+ 1
=[1]
x
+[1]
t
4
=
t
2
−
q
3
t
3
=
x
−
1 +
x
+
x
2
5
x
=[
x
] 1 +[0] Termination since
r
5
= 0
Note that polynomial coefficients are computed in
GF
(2), and since addition and
multiplication are the same operations, we can always replace a negative coefficient
(such as
≡
t
4
x
) by a positive one. The new quotient and the new remainder that are
computed in every iteration are shown in brackets above. The polynomials
t
i
(
x
)
are computed according to the recursive formula that was used for computing the
integers
t
i
earlier in this section. The EEA terminates if the remainder is 0, which is
the case in the iteration with index 5. The inverse is now given as the last
t
i
(
x
) value
that was computed, i.e.,
t
4
(
x
):
−
A
−
1
(
x
)=
t
(
x
)=
t
4
(
x
)=
x
2
+
x
+ 1
.
Here is the check that
t
(
x
) is in fact the inverse of
x
2
, where we use the properties
that
x
3
x
+ 1mod
P
(
x
) and
x
4
x
2
+
x
mod
P
(
x
):
≡
≡
x
2
=
x
4
+
x
3
+
x
2
≡
t
4
(
x
)
·
(
x
2
+
x
)+(
x
+ 1)+
x
2
mod
P
(
x
)
≡
1mod
P
(
x
)
Note that in every iteration of the EEA, one uses long division (not shown above)
to determine the new quotient
q
i
−
1
(
x
) and the new remainder
r
i
(
x
).
The inverse Table 4.2 in Chap. 4 was computed using the extended Euclidean
algorithm.
6.3.3 Euler's Phi Function
We now look at another tool that is useful for public-key cryptosystems, especially
for RSA. We consider the ring
Z
m
, i.e., the set of integers
{
0
,
1
,...,
m
−
1
}
.Weare
