Fields of the Order 2n

by Karen Carter, working under Douglas Ulmer for
an Undergraduate Research Assistantship in the Mathematics
Department at the University of Arizona

The purpose of this project was originally to explore some of the issues surrounding number theory as it relates to cryptography, specifically using the text A Course in Number Theory and Cryptography by Neal Koblitz. The final result was an exploration of fields of the size of 2n, which are isomorphic to the fields of elements created by modding the polynomial ring F2[x] out by an irreducible polynomial of degree n from that ring. These elements are represented as polynomials whose results after being added together, multiplied together, etc. are determined by the irreducible polynomial. This exploration led to the production of a calculator of sorts, written in the Java programming language, which adds, subtracts, multiplies, divides, exponentiates, and finds inverses and logarithms for elements from fields of 2n elements, represented as polynomials.

This project relates to cryptography in several important ways. First, a number of cryptosystems in use today depend on the difficulty of solving the discrete logarithm problem in a finite group--that is, given an element y known to be of the form bx, how can one find the power of b that gives x, i.e. what is x=logby? As it turns out, this is much more difficult than one might think at first glance, at least under certain conditions ("difficult" here meaning so time-consuming so as to be computationally infeasible at the present level of technology). Some of the major systems based on this premise include the Diffie-Hellman key exchange system, the Massey-Omura cryptosystem, and the ElGamal cryptosystem.

Secondly, a working knowledge of finite fields and their construction is extremely helpful in understanding many other cryptosystems, especially those based on factoring, such as the RSA cryptosystem. RSA, in particular, is based upon the idea that it is very difficult (where "difficult" means again taking a very long time with today's methods and computing power) to find the prime factors of very large numbers ("large" also depends upon the means of computing such things at the current level of technology). The prime integers are related to the irreducible polynomials mentioned above, and understanding one helps to understand the other.

Finally, finite fields play a very important role in the world of mathematics and number theory, so the deeper understanding gained through this project is applicable to many other areas besides just number theory or cryptography.


Links:
Introduction
Specifics About the Project
Index to the Java Programs
The Polynomial Calculator


Feeling lost? Don't remember exactly how that whole "field" thing works? Here is a page containing defintions and examples. (This page assumes the reader is familiar with the basics of number theory, i.e. the definition of a group, etc.)


Please don't steal my code without giving me credit; that's all I ask.
Karen Carter, 2001