Some definitions (examples are listed with each definition):

- a(bc) = (ab)c
- a + (b + c) = (a + b) + c
- ab = ba
- a + b = b + a
- a(c + d) = ac + ad
- a(1)=a
- a + 0 = a
- aa
^{-1}= 1 - a - a = 0

irreducible polynomial--an irreducible polynomial, p, has no non-trivial factors
of positive degree lower than itself, which means that the only factors of a degree lower than
p's are constants (in the case of **F**_{2}[x] the only constant is 1).
This is very important, as irreducible polynomials play a role similar to
that of the prime numbers in the integers. So every polynomial in a field is either irreducible itself
or can be written uniquely as a product of
irreducible polynomials, up to multiplication by constants.

relatively prime--two polynomials are relatively prime if they have no non-trivial (non-constant) factors in common, much like two numbers being relatively prime implies the only common factor is 1.

the notation **F**_{2}[x]/p--when p is an irreducible polynomial, this
produces a new field of degree 2^{n}, where n is the degree of p. Essentially, p becomes
equal to 0, and all operations on other members of **F**_{2} are then defined by this
relationship of p = 0. For example x^{n+1} = x^{n+1} + p * x.

Euclidean algorithm--this algorithm is used to find the gcd (greatest common divisor) of two elements, and, alternatively, to find the inverse of an element. It works as follows:

repeated squaring method--this algorithm speeds up computation of large powers enormously by squaring squares instead of simply multiplying a polynomial (or number) by itself many times. Far fewer computations must be performed, because each time the power will be doubled, instead of merely incremented by 1. The number of computations performed this way is on the order of log n, as opposed to being on the order of n. This can make a big difference for very large values of n.

That was much faster than multiplying it all out 3 by 3 by 3.

primitive root--a primitive root of a field is an element which solves the equation
x^{n} - 1, such that x^{n} = 1, but x^{m} doesn't equal 1 in the field for any m
less than n.
For the case interesting
to us, n is equal to the number of non-zero elements in **F**_{2}[x]/<p>, where p is an
irreducible polynomial. All the roots of p satisfy the first condition, but not all of them satisfy
the second condition. The roots of the equation aren't so hard to find, but finding the primitive
roots takes more effort and computation.
Primitive roots are important in that they generate, that is, all of their powers will
be equal to, all the non-zero elements in the field.

Links:

Introduction

Specifics About the Project

Index to the Java Programs

The Polynomial Calculator