Computing in Algebraic Extensions

The aim of this chapter is an introduction to elementary algorithms in algebraic extensions, mainly over Q and, to some extent, over GF(p). We will talk about arithmetic in Q(α) and GF(pn) in Section 1 and some polynomial algorithms with coefficients from these domains in Section 2. Then, we will consider the field K of all algebraic numbers over Q and show constructively that K indeed is a field, that multiple extensions can be replaced by single ones and that K is algebraically closed, i.e. that zeros of algebraic number polynomials will be elements of K (Section 4 — 6). For this purpose we develop a simple resultant calculus which reduces all Operations on algebraic numbers to polynomial arithmetic on long integers together with some auxiliary arithmetic on rational intervals (Section 3). Finally, we present some auxiliary algebraic number algorithms used in other chapters of this volume (Section 7). This chapter does not include any special algorithms of algebraic number theory. For an introduction and survey with an extensive bibliography the reader is referred to Zimmer [15].