Book review

The finite fields play an important role in algebraic number theory, coding theory, cryptography, computer science, numerical methods and so on. This book presents an exhaustive treatment of computational and algorithmic problems in finite fields such as polynomial factorization over finite fields, irreducibility and primitivity of polynomials and the distribution of irreducible polynomials and primitive polynomials, construction of bases of various types, the distribution of rational points on elliptic curves over finite fields. Two special chapters on some recent advances in and applications of the theory of congruences and other related subjects of computational number theory complete the survey.

A severe selection was made by the author in order to write a book specialized on announced topics only; he gave up the papers which consider only the structure of additive or multiplicative group of the finite field. Each result is presented with at least a sketch of proof and by underlying the main ideas. However, for some new results, more complete proofs are given.

The majority of the strongest results in the areas of the theory of finite fields and computer science, coding theory, computing, algebraic number theory are based on estimates of potential sums and of rational points of algebraic varieties over finite fields. Even in polynomial factorization, the best known algorithm depends drastically on estimates of character sums (see Theorem 1.1, which improves slightly the classical algorithm). The same can be stated on algorithms for finding primitive roots (Section 2.2.), for the multiplication algorithm with linear multiplicative complexity due to D. Chudnovsky and G. Chudnovsky, for a lot of results of algebraic coding theory (Chapter 5, Section 9.2), for the fastest known tests for permutation polynomials in Section 8.1 etc.

Chapter 1 of this book is devoted to new ideas and results (obtained by J. von zur Gathen, H.W. Lenstra, V. Shoup, R.J. Schoof, M. Mignotte, C.P. Schnorr, A.L. Chistov, D.Yu. Grigoriev, E. Kaltofen, D. Wan) in polynomial factorizing and solving algberaic equations over finite fields; the univariate and multivariate factorizations, quadratic equations and other topics are considered here.

Explicit constructions and fast algorithms for finding irreducible and primitive polynomials over finite fields are given in the second chapter, while the distribution of these polynomials is studied in the third chapter. Two examples: It is proved that for each prime p there exists an irreducible polynomial of a given fixed degree n and of height O(p^(2/3)). It is also proved that for each prime p there exists a primitive polynomial of a given fixed degree n and of height O(p^(n/(n+1)+ e) ) that for n=1 gives the famous bounds of I.M. Vinogradov on the smallest primitive roots modulo p.

A brief outline of some works devoted to arithmetic in a finite field is the subject of Chapter 4. The main prblem is the choice of the basis over its ground field and some fast constructions of such a basis are given here.

In Chapter 5 one can find some recent results on algebraic curves over finite fields and estimates of exponential sums which are connected with coding theory, in particular with geometric-algebraic codes (G. Lachaud, C. Moreno, O. Moreno, J.-P. Serre, S.G. Vladuts, M.A. Tsfasman, J. Wolfmann and others).

The next chapter deals with the very important special case of elliptic curves over finite fields, moreover new results on the number of rational points and on the group structure of these curves are pointed out.

Chapter 7 examines linear reccuring sequences over finite fields and their connections with finite automata and linear cyclic codes. A new combinatorial method and a new technique for studying the distribution of values of linear reccuring sequences. Chapter 8 describes applications of finite fields to cryptography, graph theory, combinatoric.

The chapter 9 is devoted to some related problems on congruences such as N.M. Korobov's optimal coefficients, congruential pseudo-random numbers, modular arithmetic,congruences in algebraic number fields and their applications to coding theory (H.W. Lenstra's codes). The last chapter makes a review of recent works on primality testing and integer factorization, on the lattice basis reduction algorithm, on algorithmic algebraic number theory, on integer polynomials and algebraic complexity theory.

Appendix 1 shows interconnections in the book, Appendix 2 gives a list of sources where the great part of papers considered in the book are published (for the Russian journals, Appendix 3 gives their English translations). The reference list contains 1306 titles and it is valuable in itself.

The book is interesting for the students and the researchers working in computational and algorithmic problems over finite fields; it can be recommended as supplementary graduate text for students.