Algorithms for finite fields
Hendrik W. Lenstra · Cambridge University Press eBooks · 1990
In this paper, we survey the complexity status of some fundamental algorithmic problems concerning finite fields. In particular, we consider the following two questions: given a prime number p and a positive integer n , construct explicitly a field that is of degree n over the prime field of p elements; and given two such fields, construct an explicit field isomorphism between them. For both problems there exist good probabilistic algorithms. The situation is more complicated if deterministic algorithms are required. Introduction Every finite field has cardinality p n for some prime number p and some positive integer n . Conversely, if p is a prime number and n a positive integer, then there exists a field of cardinality p n , and any two fields of cardinality p n are isomorphic. These results are due to E. H. Moore (1893) [15]. In this paper, we discuss the complexity aspects of two algorithmic problems that are suggested by this theorem, and of two related problems. Constructing finite fields . We say that a finite field is explicitly given if, for some basis of the field over its prime field, we know the product of any two basis elements, expressed in the same basis. Let, more precisely, p be a prime number and n a positive integer.