•We do
know that GF (23) is an abelian group because of the operation
of
polynomial addition satisfies all of the requirements on a group operator and
because polynomial addition is commutative.
•GF (23) is also a commutative ring because
polynomial multiplication
distributes
over polynomial addition
–polynomial
multiplication
meets all the other stipulations on the ring operator: closedness,
associativity, commutativity
•
•GF (23) is an integral domain because of the
fact that the set contains the multiplicative identity element 1 and because if
for a ∈ GF(23) and b ∈ GF(23) we have
a×b = 0
mod(x3+x+1)
•Then
either a = 0 or
b = 0.
•We
now argue that GF (23) is a
finite field because
it is a
finite set and because it contains a unique multiplicative inverse for every
non-zero element.
•GF (23) contains a unique multiplicative
inverse for every non- zero element for the same reason that Z7 contains a unique multiplicative
inverse
for every non-zero integer in the set.
–For a counter
example,
recall that Z8 does not possess multiplicative inverses
for 2, 4, and 6.
–Stated
formally,
we say that for every non-zero element a ∈ GF(23)
there is always a unique element b∈GF(23)
such that a×b = 1.
•The above conclusion follows from the fact if you multiply a non-zero element a with each of the eight elements of GF(23), the result will be the eight distinct elements of GF(23).
–Obviously, the
results of such multiplications must equal 1 for exactly one of the non-zero
element of GF(23).
–So if a×b = 1,
then b must be the multiplicative inverse for a.
•
•The
same thing happens in Z7. If you multiply a non-zero element a of
this set with each of the seven elements of Z7, you
will get seven distinct answers.
–The answer
must therefore equal 1 for at least one such multiplication. When the answer is
1, you have your multiplicative inverse for a.
•For a
counter
example,
this is not what happens in Z8.
When you multiply 2 with every element of Z8, you
do not get eight distinct answers.
–Multiplying
2
with every element of Z8 yields {0, 2, 4, 6, 0, 2, 4, 6} that has only four
distinct elements
•For a more formal proof (by contradiction) of the fact that if you multiply a non-zero element a of GF(23) with every element of the same set, no two answers will be the same, let’s assume that this assertion is false. That is, we assume the existence of two distinct b and c in the set such that
a × b ≡ a × c mod (x3 + x + 1)
That implies
a×(b−c) ≡ 0 mod (x3+x+1)
•That
implies that either a is 0 or that b equals c. In either case, we have a
contradiction.
•The upshot
is that GF (23) is a finite field.
GF(2n) Is A
Finite Field For Every N
•GF(2n) is a finite field for every n.
•To
find all the polynomials in GF (2n), we
obviously need an irreducible polynomial of degree n.
•AES arithmetic
is
based on GF (28). It uses the following irreducible
polynomial
x8 +x4 +x3 +x+1
•In general, GF(pn) is a finite field for any prime p.
–The elements
of GF(pn) are polynomials over GF(p)
–which
is
the same as the set of residues Zp
Finding the Multiplicative Inverse
•Just
as the Euclidean
algorithm can
be adapted to find the greatest common divisor of two polynomials, the extended
Euclidean algorithm can
be adapted to find the multiplicative inverse of a
polynomial.
•
•Specifically, the
algorithm will find the multiplicative inverse
of b(x)
modulo a(x)
if
the degree
of b(x) is
less than the degree of a(x) and gcd[a(x), b(x)] = 1.
•
•If a(x) is
an irreducible polynomial, then it has no factor other than itself or 1, so
that gcd[a(x), b(x)] =
1.
•Given
polynomials a(x) and b(x) with the degree of a(x)
greater than the degree of b(x), we solve the following equation for the values v(x), w(x), and d(x),
where d(x) = gcd[a(x), b(x)]:
a(x)v(x)
+ b(x)w(x)
= d(x)
•If d(x) = 1,
then w(x) is
the multiplicative inverse of b(x) modulo a(x).
•The
calculations are
as follows.
