Cryptography Reference
In-Depth Information
F
p
m
requires
O
(
m
2
) bit operations
or, using fast polynomial arithmetic,
O
(
M
(
m
)) bit operations. If
m
is fixed and
p
goes to
infinity then the complexity is
O
(
M
(log(
p
))) bit operations.
Inversion of elements in
If
p
is constant and
m
grows then multiplication in
= F
p
[
x
]
/
(
F
(
x
)) can be done using the extended Euclidean
algorithm in
O
(
m
2
) operations in
F
p
m
F
p
.If
p
is fixed and
m
grows then one can invert elements
in
F
p
m
in
O
(
M
(
m
)log(
m
)) bit operations.
Alternatively, for any vector space basis
{
θ
1
,...,θ
m
}
for
F
q
m
over
F
q
there is an
m
×
m
matrix
M
over
F
q
such that the product
ab
for
a,b
∈ F
q
m
is given by
m
m
(
a
1
,...,a
m
)
M
(
b
1
,...,b
m
)
t
=
M
i,j
a
i
b
j
i
=
1
j
=
1
where (
a
1
,...,a
m
) and (
b
1
,...,b
m
) are the coefficient vectors for the representation of
a
and
b
with respect to the basis.
In particular, if
θ,θ
q
,...,θ
q
m
−
1
F
q
m
is represented by a normal basis
{
}
then multiplica-
tion of elements in normal basis representation is given by
a
i
θ
q
i
b
j
θ
q
j
m
−
1
m
−
1
m
−
1
m
−
1
=
a
i
b
j
θ
q
i
+
q
j
i
=
0
j
=
0
i
=
0
j
=
0
θ
q
i
+
q
j
so it is necessary to precompute the representation of each term
M
i,j
=
over the
normal basis. Multiplication in
F
p
m
using a normal basis representation is typically slower
than multiplication with a polynomial basis; indeed, the complexity can be as bad as
O
(
m
3
)
operations in
F
p
.An
optimal normal basis
is a normal basis for which the number of
non-zero coefficients in the product is minimal (see Section II.2.2 of [
60
] for the case of
F
2
m
). Much work has been done on speeding up multiplication with optimal normal bases;
for example see Bernstein and Lange [
52
] for discussion and references.
Raising an element of
F
q
m
to the
q
th power is always fast since it is a linear operation.
Taking
q
th powers (respectively,
q
th roots) is especially fast for normal bases as it is a
rotation; this is the main motivation for considering normal bases. This fact has a number
of important applications, see for example, Exercise
14.4.7
.
2.12 Factoring polynomials over finite fields
There is a large literature on polynomial factorisation and we only give a very brief sketch
of the main concepts. The basic ideas go back to Berlekamp and others. For full discussion,
historical background and extensive references see Chapter 7 of Bach and Shallit [
21
]or
Chapter 14 of von zur Gathen and Gerhard [
220
]. One should be aware that for polynomials
over fields of small characteristic the algorithm by Niederreiter [
418
] can be useful.
Let
F
(
x
)
∈ F
q
[
x
] such that
G
(
x
)
2
∈ F
q
[
x
]havedegree
d
. If there exists
G
(
x
)
|
F
(
x
) then
F
(
x
) where
F
(
x
) is the derivative of
F
(
x
). A polynomial is
square-free
if it has no
G
(
x
)
|
