Cryptography Reference
In-Depth Information
m
is odd; the case of
m
even is similar)
=
a
0
+
a
m
−
1
x
m
−
1
+
x
a
1
+
a
m
−
2
x
m
−
3
.
a
2
x
2
a
3
x
2
+···+
+···+
g
Show that
√
g
=
a
0
+
x
m
−
1
x
(
m
−
1)
/
2
+
√
x
a
1
+
a
m
−
2
x
(
m
−
3)
/
2
.
+···
+···+
a
2
x
a
3
x
Show that this computation takes roughly half the cost of one field multiplication, and
hence
O
(
m
2
) bit operations.
Exercise 2.14.6
Generalise Exercise
2.14.5
to computing
p
th roots in
F
p
m
. Show that the
method requires (
p
−
1) multiplications in
F
p
m
.
We now consider how to solve quadratic equations of the form
x
2
+
x
=
α
(2.4)
where
α
∈ F
2
m
.
Exercise 2.14.7
Prove that the equation
x
2
+
x
=
α
has a solution
x
∈ F
2
m
if and only
if Tr
F
2
m
/
F
2
(
α
)
=
0.
Lemma 2.14.8
If m is odd (we refer to Section II.2.4 of [
60
] for the case where m is even)
then a solution to equation (
2.4
) is given by the
half trace
(
m
−
1)
/
2
α
2
2
i
.
x
=
(2.5)
i
=
0
Exercise 2.14.9
Prove Lemma
2.14.8
. Show that the complexity of solving quadratic
equations in
2
m
and
m
is odd is an expected
O
(
m
3
) bit operations (or
O
(
m
2
)
bit operations when a normal basis is being used).
F
q
when
q
=
F
2
m
when
m
is even is
O
(
m
4
) bit operations, or
O
(
m
3
) when a normal basis is being used. Hence, we can make
the statement that the complexity of solving a quadratic equation over any field
The expected complexity of solving quadratic equations in
F
q
is an
expected
O
(log(
q
)
4
) bit operations.
2.14.3 Isomorphisms between finite fields
Computing the minimal polynomial of an element
Given
g
∈ F
q
m
one can compute the minimal polynomial
F
(
x
)of
g
over
F
q
using linear
1
,g,g
2
,...,g
n
algebra. To do this, one considers the set
S
n
={
}
for
n
=
1
,...,m
.Let
n
be
the smallest integer such that
S
n
is linearly dependent over
F
q
. Then there are
a
0
,...,a
n
∈
F
q
such that
i
=
0
a
i
g
i
=
0. Since
S
n
−
1
is linearly independent, it follows that
F
(
x
)
=
i
=
0
a
i
x
i
is the minimal polynomial for
g
.
Exercise 2.14.10
Show that the above algorithm requires
O
(
m
3
) operations in
F
q
.
