The aim of this chapter is to give a brief summary of some fundamental algorithms for arithmetic in finite fields. The intention is not to provide an implementation guide; instead, we sketch some important concepts and state some complexity results that will be used later in the book. We do not give a consistent level of detail for all algorithms; instead, we only give full details for algorithms that will play a significant role in later chapters of the book.

More details of these subjects can be found in Crandall and Pomerance [150], Shoup [497], Buhler and Stevenhagen [106], Brent and Zimmermann [95], Knuth [308], von zur Gathen and Gerhard [220], Bach and Shallit [21] and the handbooks [16, 376].

The chapter begins with some remarks about computational problems, algorithms and complexity theory. We then present methods for fast integer and modular arithmetic. Next we present some fundamental algorithms in computational number theory such as Euclid's algorithm, computing Legendre symbols and taking square roots modulo p. Finally, we discuss polynomial arithmetic, constructing finite fields and some computational problems in finite fields.

Algorithms and complexity

We assume the reader is already familiar with computers, computation and algorithms. General references for this section are Chapter 1 of Cormen et al. [136], Davis and Weyuker [154], Hopcroft and Ullman [265], Section 3.1 of Shoup [497], Sipser [509] and Talbot and Welsh [539].