Cryptography Reference
In-Depth Information
A.5 Polynomials
Let
in
n
variables. We write deg
x
i
(
F
(
x
1
,...,x
n
)) to be the degree as a polynomial in
x
i
with coefficients in
k
be a field. Denote by
k
[
x
]
= k
[
x
1
,...,x
n
] the set of polynomials over
k
k
[
x
1
,...,x
i
−
1
,x
i
+
1
,...,x
n
]. For polynomials
F
(
x
)
∈ k
[
x
] we write
deg(
F
(
x
)) for deg
x
(
F
(
x
)). A degree
d
polynomial in
k
[
x
]is
monic
if the coefficient of
=
l
i
=
1
F
i
x
m
i,
1
x
m
i,
n
(with
F
i
=
x
d
is 1. The
total degree
of a polynomial
F
(
x
)
···
0) is
max
1
≤
i
≤
l
j
=
1
m
i,j
.
A polynomial
F
(
x
) is divisible by
G
(
x
) if there exists a polynomial
H
(
x
) such that
F
(
x
)
1
deg(
F
)
=
=
G
(
x
)
H
(
x
). A polynomial
F
(
x
)
∈ k
[
x
]is
irreducible
over
k
(also called
k
-
irreducible) if whenever
F
(
x
)
=
G
(
x
)
H
(
x
) with
G
(
x
)
,H
(
x
)
∈ k
[
x
] either
G
or
H
is a
constant polynomial.
There are various ways to show that a polynomial is irreducible.
Eisenstein's criteria
states that
F
(
x
)
=
i
=
0
F
i
x
i
∈
R
[
x
], where
R
is a UFD, is irreducible if there is a prime
i<n
, and
p
2
p
in
R
such that
p
F
0
. We refer to Proposition III.1.14
of [
529
], Theorem IV.3.1 of [
329
] or Theorem III.6.15 of [
271
] for proofs.
If
F
n
,
p
|
F
i
for 0
≤
k
is a field then the polynomial ring
k
[
x
1
,...,x
n
] is a UFD (Theorem III.6.14 of
[
271
]). Let
F
(
x
)
∈ k
[
x
] be a polynomial in one variable of degree
d
. Then either
F
=
0or
else
F
(
x
) has at most
d
roots in
.
Lemma A.5.1
Let N
d,q
be the number of monic irreducible polynomials of degree d in
F
q
[
x
]
. Then q
d
/
2
d
k
q
d
/d.
Proof
See Theorem 20.11 of [
497
] or Exercise 3.27 of [
350
]. A more precise result is given
in Theorem
15.5.12
.
≤
N
d,q
≤
[
x
]. One can define the
derivative
F
(
x
) by using the rule (
F
n
x
n
)
=
Let
F
(
x
)
∈ k
nF
n
x
n
−
1
0 for each monomial. This is a formal algebraic operation and does not
require an interpretation in terms of calculus.
for
n
≥
Lemma A.5.2
Let F
1
(
x
)
,F
2
(
x
)
∈ k
[
x
]
. Then:
F
2
(
x
))
=
F
1
(
x
)
F
2
(
x
)
.
1.
(
F
1
(
x
)
+
+
2.
(
F
1
(
x
)
F
2
(
x
))
=
F
1
(
x
)
F
2
(
x
)
F
2
(
x
)
F
1
(
x
)
.
+
3.
(
F
1
(
F
2
(
x
))
=
F
1
(
F
2
(
x
))
F
2
(
x
)
.
k
=
p then F
(
x
)
=
=
G
(
x
)
p
for some G
(
x
)
∈ k
4. If
char(
)
0
if and only F
(
x
)
[
x
]
.
Similarly, the notation
∂F/∂x
i
is used for polynomials
F
(
x
)
∈ k
[
x
] and an analogue of
Lemma
A.5.2
holds.
A.5.1 Homogeneous polynomials
Definition A.5.3
A non-zero polynomial
F
(
x
)
∈ k
[
x
]is
homogeneous
of degree
d
if all
its monomials have degree
d
, i.e.
F
i
0
,i
1
,...,i
n
x
i
0
x
i
1
···
x
i
n
.
F
(
x
0
,...,x
n
)
=
i
0
,i
1
,...,i
n
∈Z
≥
0
i
0
+
i
1
+···
i
n
=
d
Any polynomial
F
(
x
)
∈ k
[
x
0
,...,x
n
] can be written as a
homogeneous decomposition
i
=
0
F
i
(
x
)forsome
m
∈ N
where
F
i
(
x
) is a homogeneous polynomial of degree
i
;see
Section II.3 of [
329
].
