**This page assumes a fairly good understanding of number theory and field theory. For a
refresher, see the help page**.

Essentially, the calculator produced as a result of this project uses an irreducible polynomial
with coefficients from the field {0, 1} of any degree (limited by computing power, naturally) either
specified by the user or by the program itself. The program uses the sieve method:
multiply each polynomial
of appropriate degree by every other polynomial of appropriate degree, i.e. for an irreducible polynomial
of degree 5, multiply
all polynomials of degree 1 by all polynomial of degree 4 and all polynomials of degree 2 by all
polynomials of degree 3. Then look at the possible polynomials that aren't there--those are the
irreducibles. Such an irreducible polynomial is then used to create a field of elements represented
as polynomials with coefficients from {0, 1} with 2^{n}
elements, where n is the degree of the irreducible polynomial. These polynomials may then be
added, subtracted, multiplied, divided, and exponentiated, and their inverses may also be found
(recall that this is a field, so each element has both an additive and multiplicative inverse), as
well as logarithms to a specified base.

What do these elements look like? There are actually two different representations.
This program uses the representation of all possible polynomials of degree
less than n, where n is the degree of the irreducible polynomial as discussed above.
So, using this representation, the elements of **F**_{2}[x]/<x^{2} + x + 1>
may be written as x + 1, x, 1, and 0. The other representation is
simply the powers of a root of the irreducible polynomial, up to 2^{n}-2, plus 0. For
example, using again the irreducible polynomial x^{2} + x + 1, the elements of
**F**[x]/<x^{2}
+ x + 1> may be written as x^{2}, x, 1, 0, because x is a root of x^{2} + x + 1.
Unfortunately, x is not always a primitive root of the field,
so this representation is not always so easy to find.
It would be more complicated to first find a root and then determine how the powers of the root
worked together (for example, if one is using the power representation, how does one define addition?)
In the above example the correspondence between the two representations appears trivial, as
it is clearly defined by the irreducible polynomial (x^{2} = x + 1) but for
larger polynomials, such as x^{4} + x + 1, this is not necessarily true.
In the first representation, addition is very easy, but multiplication is much more complicated
than in the second. However, the problem of finding a root is more difficult than that of defining
multiplication, so the first representation is used for this program.

Any polynomial can be reduced mod the irreducible polynomial, p, to an element with degree less than
p. This is accomplished by calculating the powers of p which are equal to or greater than the degree
of p and replacing them. Since p is essentially set to zero in the field **F**_{2}[x]/<p>,
there is an easy way to do this. For example, if p = x^{4} + x + 1 = 0, then x^{4} = x + 1,
x^{5} = x^{2} + x, x^{6} = x^{3} + x^{2}, and so forth. So in
a given polynomial, any powers greater than the degree of p are replaced by their equivalences of lower
degree. This is the same as dividing p into a given element and taking the remainder to be the reduced
version.

The program itself is written in Java and consists of two parts. The first is a class named
Irreducibles.java, which can produce a list of all the reducible
elements from **F**_{2}[x] of a given degree, as well as a complete list of the elements
of a certain degree. The
second program, Operations.java, uses these results to pick an
irreducible polynomial of a specified degree, if the user wishes, or to verify an irreducible
polynomial provided by the user, in order to construct a field such as that described above.

The actual representation of these polynomials is a boolean array of size n,
n being the degree of the irreducible polynomial discussed above, where true
represents a coefficient of one and false a coefficient of 0. The polynomials are stored with
the least significant digit being first, i.e. for a given a_{i}x^{i}, where
a_{i} is an element of {0, 1}, a_{i}=0 means array[i]=false, and a_{i}=1
means array[i]=true. For example, the polynomial x^{3} + x + 1 is represented as the
array {true, true, false, true}. For input of polynomials of degree n or greater, the polynomial
is immediately reduced to an appropriate degree by use of the irreducible polynomial for the field
(e.g. in **F**_{2}[x]/<x^{4} + x + 1>, x^{4} + x + 1=0, so x^{4}=x + 1).

Addition and subtraction are the same operation for this program, as in the field of two elements, one and negative one are the same. Addition and subtraction are handled pairwise, so if, for two polynomials f and g, represented by the arrays f and g, respectively, f[i] and g[i] are both true or both false, then result[i] will be false. Otherwise, result[i] will be true.

Multiplication is handled as a series of additions, just the same way as one might multiply
polynomials by hand. So (x^{2} + x + 1)*(x^{2} + 1) in a field based on a polynomial
of degree 5 will equal x^{2}(x^{2} + 1) + x(x^{2} + 1) + 1(x^{2} + 1).

Division is actually handled through the inverse function, so that first the inverse of the divisor is calculated and then multiplied by the dividend.

Multiplicative inverses are rather more complicated (of course in this field, each polynomial is its
own additive inverse). An element in **F**_{2}[x]/<p>, where p is an irreducible polynomial,
is invertible if and only if it is non-zero and relatively prime
to p in **F**_{2}. To find inverses, the Euclidean algorithm for polynomials is quite useful.
It gives an expression to find the greatest common divisor of two polynomials, say p as above and f, the
element to be inverted. If f is invertible, the greatest common divisor will be a constant (in **F**_{2}
1). The Euclidean algorithm also states there are polynomials a and b such that a * p + b * f = 1, and
since in **F**_{2}[x]/<p>, p is equivalent to zero, the expression is really just b * f = 1,
so that b and f are inverses.
There is a specific explanation of
the Euclidean algorithm here on the help page.

Exponentiation is accomplished by use of the repeated squaring method. In a nutshell, this algorithm saves
time by making fewer calculations by squaring squares until the desired power is attained. For example, why calculate
(x^{3} + x^{2} + 1)^{9} by multiplying the polynomial 9 times, when one could calculate the
square, and then square the square (raising the original polynomial to the fourth power) and so forth. In this
implementation the results are reduced after each iteration, as that was much simpler in terms of storage.
Here are a more indepth explanation and an example..

Logarithms to a specific base may also be calculated, and this is accomplished in the crudest method possible.
Namely, the base is multiplied by itself repeatedly until the desired polynomial is achieved, or until the result
"wraps around" to the base--that is, if in the course of raising the base to the n^{th} power, the base
itself is a result, then obviously the logarithm is undefined.
This is because in a field which is not continuous but rather discrete, every element is not always a power of
every other element (unlike the positive real numbers).
The problem itself is also known as the discrete logarithm problem, as discussed in the introduction.
There do exist several faster algorithms for solving this problem, but they all assume some other knowledge
of the problem and are rather difficult to implement.

Links:

Introduction

Specifics About the Project

Index to the Java Programs

The Polynomial Calculator