Specifics about the Project

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 2n 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 F2[x]/<x2 + 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 2n-2, plus 0. For example, using again the irreducible polynomial x2 + x + 1, the elements of F[x]/<x2 + x + 1> may be written as x2, x, 1, 0, because x is a root of x2 + 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 (x2 = x + 1) but for larger polynomials, such as x4 + 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 F2[x]/<p>, there is an easy way to do this. For example, if p = x4 + x + 1 = 0, then x4 = x + 1, x5 = x2 + x, x6 = x3 + x2, 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 F2[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 aixi, where ai is an element of {0, 1}, ai=0 means array[i]=false, and ai=1 means array[i]=true. For example, the polynomial x3 + 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 F2[x]/<x4 + x + 1>, x4 + x + 1=0, so x4=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 (x2 + x + 1)*(x2 + 1) in a field based on a polynomial of degree 5 will equal x2(x2 + 1) + x(x2 + 1) + 1(x2 + 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 F2[x]/<p>, where p is an irreducible polynomial, is invertible if and only if it is non-zero and relatively prime to p in F2. 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 F2 1). The Euclidean algorithm also states there are polynomials a and b such that a * p + b * f = 1, and since in F2[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 (x3 + x2 + 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 nth 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