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 2^{n}, which are isomorphic to the fields of elements
created by modding the polynomial ring **F**_{2}[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 2^{n} 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 b^{x},
how can one find the power of b that gives x, i.e. what is x=log_{b}y? 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.)

Karen Carter, 2001