Cryptography Reference
In-Depth Information
Constructing a normal basis
We briefly survey the literature on constructing normal bases for finite fields. We assume
that a polynomial basis for
F
q
has already been computed.
The simplest randomised algorithm is to choose
θ
F
q
m
over
∈ F
q
m
at random and test whether
θ,θ
q
,...,θ
q
m
−
1
the set
F
q
. Corollary 3.6 of von zur Gathen
and Giesbrecht [
221
] (also see Theorem 3.73 and Exercise 3.76 of [
350
,
351
]) shows that
a randomly chosen
θ
is normal with probability at least 1
/
34 if
m<q
4
{
}
is linearly independent over
and probability at
q
4
.
least 1
/
(16 log
q
(
m
)) if
m
≥
Exercise 2.14.1
Determine the complexity of constructing a normal basis by randomly
choosing
θ
.
When
q>m
(
m
−
1) there is a better randomised algorithm based on the following
result.
Theorem 2.14.2
Let F
(
x
)
∈ F
q
[
x
]
be irreducible of degree m and let α
∈ F
q
m
be any
α
)
F
(
α
))
root of F
(
x
)
. Define G
(
x
)
=
F
(
x
)
/
((
x
−
∈ F
q
m
[
x
]
. Then there are q
−
m
(
m
−
1)
elements u
∈ F
q
such that θ
=
G
(
u
)
generates a normal basis.
Proof
See Theorem 28 of Section II.N of Artin [
14
] or Section 3.1 of Gao [
218
].
Deterministic
algorithms
for
constructing
a
normal
basis
have
been
given
by
Luneburg [
360
] and Lenstra [
341
] (also see Gao [
218
]).
2.14.2 Solving quadratic equations in finite fields
This section is about solving quadratic equations
x
2
F
q
. One can apply
any of the algorithms for polynomial factorisation mentioned earlier. As we saw in Exer-
cise
2.12.6
, when
q
is odd, the basic method computes roots in
O
(log(
q
)
M
(log(
q
))) bit
operations. When
q
is odd it is also natural to use the quadratic formula and a square-roots
algorithm (see Section
2.9
).
+
ax
+
b
=
0 over
Exercise 2.14.3
Generalise the Tonelli-Shanks algorithm from Section
2.9
to work for
any finite field
F
q
where
q
is odd. Show that the complexity remains an expected
O
(log(
q
)
2
M
(log(
q
))) bit operations.
F
q
(
θ
) where
θ
2
Exercise 2.14.4
Suppose
F
q
2
is represented as
∈ F
q
. Show that one can
compute square roots in
F
q
2
using two square roots in
F
q
and a small number of multipli-
cations in
F
q
.
F
2
m
using
linear algebra in
O
(
m
3
) bit operations. The following exercise gives a method that is more
efficient.
Since squaring in
F
2
m
is a linear operation, one can take square roots in
Exercise 2.
1
4.5
Suppose one represents
F
2
m
using a polynomial basis
F
2
[
x
]
/
(
F
(
x
)). Pre-
=
m
−
1
compute
√
x
as a polynomial in
x
.Let
g
i
=
0
a
i
x
i
. To compute
√
g
write (assuming
