Finite fields: theory and computation. The meeting point of number theory, computer science, coding theory and cryptography. (English) Zbl 0967.11052

Shparlinski, I. E.

Mathematics and its Applications (Dordrecht). 477. Dordrecht: Kluwer Academic Publishers. xiv, 528 p. (1999).

The theory of finite fields has become increasingly important in the last twenty years. On the one hand there are classical algebraic and number theoretic problems related to finite fields and on the other hand finite fields have many modern applications in computer science, coding theory and cryptography. This excellent book surveys the most recent achievements in the theory and applications of finite fields and is not meant as an introduction. (For an introduction see the masterpiece of R. Lidl and H. Niederreiter [Finite fields, Encyclopedia of Mathematics and Its Applications. 20. Cambridge: Cambridge Univ. Press (1996; Zbl 0866.11069)].) The book is evidently an extension of the author’s book “Computational and algorithmic problems in finite fields” [Mathematics and Its Applications. Soviet Series. 88. Dordrecht: Kluwer Academic Publishers (1992; Zbl 0780.11064)]. The following table of contents can only give a glance of the importance of the book.
1. Polynomial factorization
2. Finding irreducible and primitive polynomials
3. The distribution of irreducible, primitive and other special polynomials and matrices
4. Bases and computations in finite fields
5. Coding theory and algebraic curves
6. Elliptic curves
7. Recurrence sequences in finite fields and cyclic linear codes
8. Finite fields and discrete mathematics
9. Congruences
10. Some related problems (primality testing, integer factorization, lattice basis reduction, algorithmic algebraic number theory, integer polynomials, algebraic complexity theory).
The book suggests numerous open problems and concludes with more than 3000 references. Consequently, it is essential for each researcher in finite field theory and related areas.

Reviewer: Arne Winterhof (Wien)

MSC:

11Txx	Finite fields and commutative rings (number-theoretic aspects)
11-02	Research exposition (monographs, survey articles) pertaining to number theory
11Y16	Number-theoretic algorithms; complexity
11T71	Algebraic coding theory; cryptography (number-theoretic aspects)
94A60	Cryptography
94B27	Geometric methods (including applications of algebraic geometry) applied to coding theory
11T06	Polynomials over finite fields
11T23	Exponential sums
11T55	Arithmetic theory of polynomial rings over finite fields
65C10	Random number generation in numerical analysis
68Q25	Analysis of algorithms and problem complexity
68W30	Symbolic computation and algebraic computation
11Y40	Algebraic number theory computations
14G05	Rational points
11G20	Curves over finite and local fields
11Y05	Factorization
11Y11	Primality

Keywords:

finite fields; number theory; algebraic number theory; computer science; coding theory; cryptography; algebraic geometry; discrete mathematics; polynomial factorization; counting points on curves; irreducible polynomials; primitive polynomials; bases; discrete logarithm; polynomial multiplication; algebraic curves; exponential sums; elliptic curves; recurrence sequences; cyclic codes; pseudo-random numbers; permutation polynomials; congruences; integer factorization; primality testing; computational algebraic number theory; algebraic complexity theory; polynomials with integer coefficients

Citations:

Zbl 0866.11069; Zbl 0780.11064

Software:

Hull; NTRU