Cryptography Reference
In-Depth Information
Exercise 2.10.2
Prove Lemma
2.10.1
.
Exercise 2.10.3
Describe the Karatsuba and 3-Toom-Cook algorithms for multiplication
of polynomials of degree
d
in
F
q
[
x
]. Show that these algorithms have complexity
O
(
d
1
.
585
)
and
O
(
d
1
.
404
) multiplications in
F
q
.
Asymptotically fast multiplication of polynomials, analogous to the algorithms men-
tioned in Section
2.2
, are given in Chapter 8 of [
220
] or Section 18.6 of [
497
]. Multipli-
cation of polynomials in
k
[
x
] of degree bounded by
d
can be done in
O
(
M
(
d
)) multipli-
cations in
. The methods mentioned in Section
2.5
for efficiently computing remainders
F
(
x
)(mod
G
(
x
)) in
k
[
x
] can also be used with polynomials; see Section 9.6.2 of [
150
]
or Section 11.1 of [
220
] for details. Fast variants of the extended Euclidean algorithm for
polynomials in
k
k
[
x
] of degree bounded by
d
require
O
(
M
(
d
) log(
d
)) multiplications in
k
k
and
O
(
d
) inversions in
(Corollary 11.6 of [
220
]).
Kronecker substitution
is a general technique that transforms polynomial multiplica-
tion into integer multiplication. It allows multiplication of two-degree
d
polynomials in
F
q
[
x
] (where
q
is prime) in
O
(
M
(
d
(log(
q
)
O
(
M
(
d
log(
dq
))) bit operations;
see Section 1.3 of [
95
], Section 8.4 of [
220
] or Section 18.6 of [
497
]. Kronecker substitu-
tion can be generalised to bivariate polynomials and hence to polynomials over
+
log(
d
))))
=
F
q
where
q
is a prime power. We write
M
(
d,q
)
=
M
(
d
log(
dq
)) for the number of bit operations to
multiply two-degree
d
polynomials over
F
q
.
Exercise 2.10.4
Show that Montgomery reduction and multiplication can be implemented
for arithmetic modulo a polynomial
F
(
x
)
∈ F
q
[
x
]ofdegree
d
.
Exercise 2.10.5
One can evaluate a polynomial
F
(
x
)
∈
R
[
x
]atavalue
a
∈
R
efficiently
=
i
=
0
F
i
x
i
then one computes
F
(
a
)as
using
Horner's rule
. More precisely, if
F
(
x
)
(
F
0
. Write pseudocode for Horner's rule and show
that the method requires
d
additions and
d
multiplications if deg(
F
(
x
))
···
((
F
d
a
)
a
+
F
d
−
1
)
a
+···+
F
1
)
a
+
=
d
.
2.11 Arithmetic in finite fields
Efficient algorithms for arithmetic modulo
p
have been presented, but we now consider
arithmetic in finite fields
F
p
m
when
m>
1. We assume
F
p
m
is represented using either a
polynomial basis (i.e., as
F
p
[
x
]
/
(
F
(
x
))) or a normal basis. Our main focus is when either
p
is large and
m
is small, or vice versa. Optimal asymptotic complexities for the case when
both
p
and
m
grow large require some care.
Exercise 2.11.1
Show that addition and subtraction of elements in
F
p
m
requires
O
(
m
)
additions in
F
p
m
, represented by a polynomial basis
and using naive methods, requires
O
(
m
2
) multiplications modulo
p
and
O
(
m
) reductions
modulo
p
.
F
p
. Show that multiplication in
