Computational methods for Finite Fields

Overview

Given a prime number p, the set of integers modulo p forms a finite field with p elements. More generally, given any power q of a prime p, there is a unique finite field with q elements. We call p the characteristic of the field. This course considers three basic computational problems associated to polynomials with coefficients in finite fields: multiplication, factorisation and zero counting. These problems are important in applications of number theory in areas such as cryptography.

Let f and g be polynomials of degree d over the field with q elements. Using an obvious algorithm, one can multiply together f and g in around d2 field operations. Remarkably, one can achieved around d log(d) field operations using a more sophisticated approach, and this will be the first topic we shall discuss. Suppose now that we are given the polynomial fg and we wish to recover the factors f and g. Trial division would take around qd field operations; however, we will describe an approach which takes only about d2 log(q) field operations. The final topic in the course relates to polynomials f(X,Y) in two variables with coefficients in a finite field. Here one wishes to compute the number of solutions (x,y) to the equation f(X,Y) = 0 where x and y lie in the finite field. The approach of trying all possible pairs requires q2 evaluations of the polynomial f. Unfortunately no algorithms are known which improve on this without some restrictions. We shall describe, instead, a method for counting the number of solutions modulo the characteristic e.g. if the characteristic is 2 determining whether the number of solutions is even or odd. This is the starting point for recent and developing work on the topic.