Cryptography Reference
In-Depth Information
where n is a positive integer (i.e., the degree of p ( x ) , denoted as deg ( p ) ), the
coefficients a i (0
i
n ) are elements in A , and x is a symbol not belonging
to A.
The set of all polynomials over A is denoted by A [ x ]. The elements of A [ x ]
are polynomials, and one can compute with these polynomials as if they were
integers. More specifically, one can add and multiply polynomials. Furthermore, if
f, g
A [ x ] such that g
=0, then one can write
f = gq + r
for q, r
A [ x ] and deg ( r ) <deg ( g ). This equation reminds us of Euclid's division
theorem (see Theorem 3.3), and hence we can also apply the Euclidean algorithms in
A [ x ]. In this case, r is the remainder of f divided by g , denoted by r
f (mod g ).
The set of all remainders of all polynomials in A [ x ] modulo g is denoted by A [ x ] g .
A polynomial f
A [ x ] is irreducible over A if the following two conditions
are satisfied:
1. f has a positive degree;
2. f = gh with g, h
A [ x ] implies that either g or h is a constant polynomial.
Otherwise, f is reducible over A . Note that the reducibility of a polynomial
depends on the algebraic structure A over which the polynomial is defined (i.e.,
a polynomial can be reducible over one algebraic structure and irreducible over
another).
Against this background, one can show that if F is a field and f is a nonzero
polynomial in F [ x ],then F [ x ] f is a ring. Furthermore, one can show that F [ x ] f is a
field if and only if f is irreducible over F . In this case, the number of elements in the
field F [ x ] f is p n (if p represents the number of elements in F and n represents the
degree of f ). We conclude that for every prime p and every positive integer n ,there
is a finite field with p n
elements (as mentioned in Section 3.1.2.5), and we denote
this field by
F p [ x ] f . Under isomorphism, we can say that
F p [ x ] f is the finite field of
order p n .
For example, the polynomial f ( x )= x 8 + x 4 + x 3 + x +1is irreducible over
F 2 . Consequently, the set of all polynomials modulo f over
F 2 forms a field with 2 8
elements (i.e., all polynomials over
F 2 of degree less than 8). So any element in the
field
F 2 [ x ] f is of the form
b 7 x 7 + b 6 x 6 + b 5 x 5 + b 4 x 4 + b 3 x 3 + b 2 x 2 + b 1 x + b 0
Search WWH ::




Custom Search