Cryptography Reference
In-Depth Information
Computing a polynomial basis for a finite field
Suppose
F
q
m
is given by some basis that is not a polynomial basis. We now give a method
to compute a polynomial basis for
F
q
m
.
∈ F
q
m
is chosen uniformly at random, then, by Lemma
A.8.4
, with probability at
least 1
/q
the element
g
does not lie in a subfield of
If
g
F
q
m
that contains
F
q
. Hence, the minimal
polynomal
F
(
x
)of
g
over
F
q
has degree
m
and the algorithm of the previous subsection
computes
F
(
x
). One therefore has a polynomial basis
1
,x,...,x
m
−
1
{
}
for
F
q
m
over
F
q
.
Exercise 2.14.11
Determine the complexity of this algorithm.
Computing isomorphisms between finite fields
Suppose one has two representations for
F
q
and wants to compute
an isomorphism between them. We do this in two stages: first, we compute an isomorphism
from any representation to a polynomial basis, and second we compute isomorphisms
between any two polynomial bases. We assume that one already has an isomorphism
between the corresponding representations of the subfield
F
q
m
as a vector space over
F
q
.
F
q
for one of the representations of
F
q
m
. The first task is to compute an isomorphism from this representation to a polynomial
representation. To do this, one computes a polynomial basis for
Let
{
θ
1
,...,θ
m
}
be the vector space basis over
F
q
m
over
F
q
using the
method above. One now has a monic irreducible polynomial
F
(
x
)
∈ F
q
[
x
]ofdegree
m
and
=
i
=
1
a
i
θ
i
for a root of
F
(
x
)in
a representation
x
F
q
m
. Determine the representations of
x
2
,x
3
,...,x
m
over the basis
{
θ
1
,...,θ
m
}
. This gives an isomorphism from
F
q
[
x
]
/
(
F
(
x
))
to the original representation of
F
q
m
. By solving a system of linear equations, one can
express each of
θ
1
,...,θ
m
with respect to the polynomial basis; this gives the isomorphism
from the original representation to
F
q
[
x
]
/
(
F
(
x
)). The above ideas appear in a special case
in the work of Zierler [
574
].
Exercise 2.14.12
Determine the complexity of the above algorithm to give an isomorphism
between an arbitrary vector space representation of
F
q
m
and a polynomial basis for
F
q
m
.
Finally, it remains to compute an isomorphism between any two polynomial rep-
resentations
F
q
[
x
]
/
(
F
1
(
x
)) and
F
q
[
y
]
/
(
F
2
(
y
)) for
F
q
m
. This is done by finding a root
a
(
y
)
∈ F
q
[
y
]
/
(
F
2
(
y
)) of the polynomial
F
1
(
x
). The function
x
→
a
(
y
) extends to a field
isomorphism from
F
q
[
x
]
/
(
F
1
(
x
)) to
F
q
[
y
]
/
(
F
2
(
y
)). The inverse to this isomorphism is
computed by linear algebra.
Exercise 2.14.13
Determine the complexity of the above algorithm to give an isomorphism
between an arbitrary vector space representation of
F
q
m
and a polynomial basis for
F
q
m
.
See Lenstra [
341
] for deterministic algorithms to solve this problem.
Random sampling of finite fields
Let
F
p
m
be represented as a vector space over
F
p
with basis
{
θ
1
,...,θ
m
}
. Generating an
element
g
∈ F
p
m
uniformly at random can be done by selecting
m
integers
a
1
,...,a
m
