Handbook of finite fields.

*(English)*Zbl 1319.11001
Discrete Mathematics and Its Applications. Boca Raton, FL: CRC Press (ISBN 978-1-4398-7378-6/hbk; 978-1-4398-7382-3/ebook). xxxv, 1033 p. (2013).

This is a brilliant monumental work on the state-of-the-art in theory and applications of finite fields. It’s a must for everyone doing research in finite fields and their related areas. The contents is best described by citing from the editors’ excellent preface.

The Handbook is organized into three parts. Part I contains two chapters, the first one which is devoted to the history of finite fields through the 18th and 19th centuries by Roderick Gow (3–11), and the second which gives an “Introduction to finite fields”, written by the editors Gary L. Mullen and Daniel Panario (13–49), providing the basic properties of finite fields used in various places throughout the entire Handbook. Mention should be made of a rather extensive list of recent finite-field related books, including textbooks as well as books dealing with theoretical and applied topics, the latter mainly related to combinatorics, coding theory and cryptography. A list of recent finite-field related conference proceedings volumes is also given. Finally, Section 2.2 by David Thomson entitled Tables, contains several tables of polynomials of interest in computational issues. Note that the website http://www.crcpress.com/product/isbn/9781439873786 provides larger and more extensive versions of the tables presented here. Note: The preface claims Ch. 2 to belong to Part II, whereas the book itself treats it as chapter of Part I.

Part II: Theoretical properties opens with Ch. 3 on “Irreducible polynomials” (53–85), containing subsections on “Counting irreducible polynomials” by Joseph L. Yucas, on “Construction of irreducibles” by Melsik Kyuregyan, on “Conditions for reducible polynomials by Daniel Panario, on “Weights of irreducible polynomials” by Omran Ahmadi, on “Prescribed coefficients” by Stephen D. Cohen, and finally on “Multivariate polynomials” by Xiang-dong Hou.

The fourth chapter, “Primitive polynomials” (87–99), gives an “Introduction to primitive polynomials” by Gary L. Mullen and Daniel Panario, and further treats topics like “Prescribed coefficients” by Stephen D. Cohen, “Weights of primitive polynomials” by Stephen D. Cohen, “Elements of high order” by Jose Felipe Voloch.

The next two chapters deal with polynomials such as irreducible and primitive polynomials over finite fields. Ch. 5 “Bases” (101–138), discusses various kinds of bases over finite fields, and Ch. 6 (139–192), discusses “Character and exponential sums” over finite fields. Ch. 5 starts with “Duality theory of bases” by Dieter Jungnickel, then discusses “Normal bases” by Shuhong Gao and Qunying Liao, “Complexity of normal bases” by Shuhong Gao and David Thomson, and finally “Completely normal bases” by Dirk Hachenberger. Ch. 6 opens with a section on “Gauss, Jacobi, and Kloosterman sums” by Ronald J. Evans. “More general exponential and character sums” are discussed by Antonio Rojas-Leon, and “Some applications of character sums” by Alina Ostafe and Arne Winterhof. Also included is a relatively new topic as “Sum-product theorems and applications” byMoubariz Z. Garaev.

In Chapter 7, “Equations over finite field” (193–213), results on solutions of equations over finite fields are discussed. First “General forms” are discussed by Daqing Wan, then “Quadratic forms” by Robert Fitzgerald, and finally “Diagonal equations” by Francis Castro and Ivelisse Rubio.

Ch. 8 “Permutation polynomials” (215–240), covers permutation polynomials in “One variable” by Gary L. Mullen and Qiang Wang and “Several variables” by Rudolf Lidl and Gary L. Mullen, as well as a discussion of “Value sets of polynomials” by Gary L. Mullen and Michael E. Zieve, and “Exceptional polynomials” over finite fields by Michael E. Zieve.

Ch. 9 considers “Special functions over finite fields” (241–302). The discussion includes Boolean functions by Claude Carlet, “PN and APN functions” by Pascale Charpin, “Bent and related functions” by Alexander Kholosha and Alexander Pott, “\(\kappa\)-polynomials and related algebraic objects” by Robert Coulter, “Planar functions and commutative semifields” by Robert Coulter and “Dickson polynomials” by Qiang Wang and Joseph L. Yucas, and finishes with a discussion of “Schur’s conjecture and exceptional covers” by Michael D. Fried.

Part II of the Handbook continues in Ch. 10 with “Sequences over finite fields” (303–344). This chapter includes material on “Finite field transforms” by Gary McGuire, “LFSR sequences and maximal period sequences” by Harald Niederreiter, “Correlation and autocorrelation of sequences” by Tor Helleseth, “Linear complexity of sequences and multisequences” by Wilfried Meidl and Arne Winterhof, and finally on “Algebraic dynamical systems over finite fields” by Igor Shparlinski.

Another very interesting chapter is Ch. 11 “Algorithms” (345–404), dealing with various kinds of finite field algorithms. This includes basic finite field “Computational techniques” by Christophe Doche, “Univariate polynomial counting and algorithms” by Daniel Panario, “Algorithms for irreducibility testing and for constructing irreducible polynomials” by Mark Giesbrecht, “Factorization of univariate polynomials” by Joachim von zur Gathen, “Factorization of multivariate polynomials” by Erich Kaltofen and Gregoire Lecerf, “Discrete logarithms over finite fields” by Andrew Odlyzko, and ends up with “Standard models for finite fields” by Bart de Smit and Hendrik Lenstra.

In Ch. 12 “Curves over finite fields” (405–491), are discussed in greater detail. This discussion opens with “Introduction to function fields and curves” by Arnaldo Garcia and Henning Stichtenoth, and includes sections on “Elliptic curves” by Joseph Silverman, on “Addition formulas for elliptic curves” by Daniel J. Bernstein and Tanja Lange, on “Hyperelliptic curves” by Michael John Jacobson jun. and Renate Scheidler, on “Rational points on curves” by Arnaldo Garcia and Henning Stichtenoth, on “Towers” by Arnaldo Garcia and Henning Stichtenoth, on “Zeta functions and \(L\)-functions” by Lei Fu, on “\(p\)-adic estimates of zeta functions and \(L\)-functions” by Regis Blache, and finally on “Computing the number of rational points and zeta functions” by Daqing Wan.

Part II closes with Ch. 13 “Miscellaneous theoretical topics” (493–546), discusses a variety of topics over finite fields. This includes “Relations between integers and polynomials over finite fields” by Gove Effinger, “Matrices over finite fields” by Dieter Jungnickel, “Classical groups over finite fields” by Zhe-Xian Wan, “Computational linear algebra over finite fields” by Jean-Guillaume Dumas and Clément Pernet, and ends with“Carlitz and Drinfeld modules” by David Goss.

Part III of the Handbook, containing four chapters, discusses various important applications, including mathematical as well as very practical applications of finite fields. Due to the immense number of papers published in these areas, only those are discussed that treat techniques and topics related to finite fields.

The first chapter is Ch. 14 “Combinatorial” (549–658) including the areas of “Latin squares” by Gary L. Mullen, “Lacunary polynomials over finite fields” by Simeon Ball and Aart Blokhuis, “Affine and projective planes” by Gary Ebert and Leo Storme, “Projective spaces” by James W. P. Hirschfeld and Joseph A. Thas, “Block designs” by Charles J. Colbourn and Jeffrey H. Dinitz, “Difference sets” by Alexander Pott, “Other combinatorial structures” by Jeffrey H. Dinitz and Charles J. Colbourn, “\((t, m, s)\)-nets and \((t, s)\)-sequences” by Harald Niederreiter, “Applications and weights of multiples of primitive and other polynomials” by Brett Stevens, and finally “Ramanujan and expander graphs” by M. Ram Murty and Sebastian M. Cioaba.

Ch. 15 on “Algebraic Coding Theory” (659–739) is another important chapter of the Handbook. First it offers a long introductory section on “Basic coding properties and bounds” by Ian Blake and W. Cary Huffman, then follow sections on “Algebraic-geometry codes” by Harald Niederreiter, “LDPC and Gallager codes over finite fields” by Ian Blake and W. Cary Huffman, “Turbo codes over finite fields” by Oscar Takeshita, “Raptor codes” by Ian Blake and W. Cary Huffman, and “Polar codes” by Simon Litsyn.

Ch. 16 “Cryptography” (741–823), being of equal importance, deals with cryptographic systems over finite fields. In the first section “Introduction to cryptography” by Alfred Menezes various basic issues dealing with cryptography are discussed. Then follow important topics such as “Stream and block ciphers” by Guang Gong and Kishan Chand Gupta, “Multivariate cryptographic systems” by Jintai Ding, “Elliptic curve cryptographic systems” by Andreas Enge, “Hyperelliptic curve cryptographic systems” by Nicolas Thériault, “Cryptosystems arising from abelian varieties” by Kumar Murty, and last but not least “Binary extension field arithmetic for hardware implementations” by M. Anwarul Hasan and Haining Fan.

Finally, in Ch. 17 “Miscellaneous applications” (825–849) several additional applications of finite fields are discussed, as there are “Finite fields in biology” by Franziska Hinkelmann and Reinhard Laubenbacher, “Finite fields in quantum information theory” by Martin Roetteler and Arne Winterhof, “Finite fields in engineering” by Jonathan Jedwab and Kai-Uwe Schmidt.

The authors/editors have collected in their very valuable Bibliography more than 3000 entries which may serve as a quick reference, the more as the relevant pages for each entry are listed. The Handbook closes with a useful 23 page Index. Finally one should mention that each section is meant to be self-contained and that no proofs are given, however, references have been given where proofs of important results can be located.

Though handbooks nowadays are preferably in computerized form, many readers might consider to buy a copy for his own, as it presents such a huge amount of information readily available and masterly presented.

Editors, contributors and publisher are equally congratulated for providing such a beautiful result not only for the finite field community but also for those from the applied areas, especially cryptographers and coding theorists.

The Handbook is organized into three parts. Part I contains two chapters, the first one which is devoted to the history of finite fields through the 18th and 19th centuries by Roderick Gow (3–11), and the second which gives an “Introduction to finite fields”, written by the editors Gary L. Mullen and Daniel Panario (13–49), providing the basic properties of finite fields used in various places throughout the entire Handbook. Mention should be made of a rather extensive list of recent finite-field related books, including textbooks as well as books dealing with theoretical and applied topics, the latter mainly related to combinatorics, coding theory and cryptography. A list of recent finite-field related conference proceedings volumes is also given. Finally, Section 2.2 by David Thomson entitled Tables, contains several tables of polynomials of interest in computational issues. Note that the website http://www.crcpress.com/product/isbn/9781439873786 provides larger and more extensive versions of the tables presented here. Note: The preface claims Ch. 2 to belong to Part II, whereas the book itself treats it as chapter of Part I.

Part II: Theoretical properties opens with Ch. 3 on “Irreducible polynomials” (53–85), containing subsections on “Counting irreducible polynomials” by Joseph L. Yucas, on “Construction of irreducibles” by Melsik Kyuregyan, on “Conditions for reducible polynomials by Daniel Panario, on “Weights of irreducible polynomials” by Omran Ahmadi, on “Prescribed coefficients” by Stephen D. Cohen, and finally on “Multivariate polynomials” by Xiang-dong Hou.

The fourth chapter, “Primitive polynomials” (87–99), gives an “Introduction to primitive polynomials” by Gary L. Mullen and Daniel Panario, and further treats topics like “Prescribed coefficients” by Stephen D. Cohen, “Weights of primitive polynomials” by Stephen D. Cohen, “Elements of high order” by Jose Felipe Voloch.

The next two chapters deal with polynomials such as irreducible and primitive polynomials over finite fields. Ch. 5 “Bases” (101–138), discusses various kinds of bases over finite fields, and Ch. 6 (139–192), discusses “Character and exponential sums” over finite fields. Ch. 5 starts with “Duality theory of bases” by Dieter Jungnickel, then discusses “Normal bases” by Shuhong Gao and Qunying Liao, “Complexity of normal bases” by Shuhong Gao and David Thomson, and finally “Completely normal bases” by Dirk Hachenberger. Ch. 6 opens with a section on “Gauss, Jacobi, and Kloosterman sums” by Ronald J. Evans. “More general exponential and character sums” are discussed by Antonio Rojas-Leon, and “Some applications of character sums” by Alina Ostafe and Arne Winterhof. Also included is a relatively new topic as “Sum-product theorems and applications” byMoubariz Z. Garaev.

In Chapter 7, “Equations over finite field” (193–213), results on solutions of equations over finite fields are discussed. First “General forms” are discussed by Daqing Wan, then “Quadratic forms” by Robert Fitzgerald, and finally “Diagonal equations” by Francis Castro and Ivelisse Rubio.

Ch. 8 “Permutation polynomials” (215–240), covers permutation polynomials in “One variable” by Gary L. Mullen and Qiang Wang and “Several variables” by Rudolf Lidl and Gary L. Mullen, as well as a discussion of “Value sets of polynomials” by Gary L. Mullen and Michael E. Zieve, and “Exceptional polynomials” over finite fields by Michael E. Zieve.

Ch. 9 considers “Special functions over finite fields” (241–302). The discussion includes Boolean functions by Claude Carlet, “PN and APN functions” by Pascale Charpin, “Bent and related functions” by Alexander Kholosha and Alexander Pott, “\(\kappa\)-polynomials and related algebraic objects” by Robert Coulter, “Planar functions and commutative semifields” by Robert Coulter and “Dickson polynomials” by Qiang Wang and Joseph L. Yucas, and finishes with a discussion of “Schur’s conjecture and exceptional covers” by Michael D. Fried.

Part II of the Handbook continues in Ch. 10 with “Sequences over finite fields” (303–344). This chapter includes material on “Finite field transforms” by Gary McGuire, “LFSR sequences and maximal period sequences” by Harald Niederreiter, “Correlation and autocorrelation of sequences” by Tor Helleseth, “Linear complexity of sequences and multisequences” by Wilfried Meidl and Arne Winterhof, and finally on “Algebraic dynamical systems over finite fields” by Igor Shparlinski.

Another very interesting chapter is Ch. 11 “Algorithms” (345–404), dealing with various kinds of finite field algorithms. This includes basic finite field “Computational techniques” by Christophe Doche, “Univariate polynomial counting and algorithms” by Daniel Panario, “Algorithms for irreducibility testing and for constructing irreducible polynomials” by Mark Giesbrecht, “Factorization of univariate polynomials” by Joachim von zur Gathen, “Factorization of multivariate polynomials” by Erich Kaltofen and Gregoire Lecerf, “Discrete logarithms over finite fields” by Andrew Odlyzko, and ends up with “Standard models for finite fields” by Bart de Smit and Hendrik Lenstra.

In Ch. 12 “Curves over finite fields” (405–491), are discussed in greater detail. This discussion opens with “Introduction to function fields and curves” by Arnaldo Garcia and Henning Stichtenoth, and includes sections on “Elliptic curves” by Joseph Silverman, on “Addition formulas for elliptic curves” by Daniel J. Bernstein and Tanja Lange, on “Hyperelliptic curves” by Michael John Jacobson jun. and Renate Scheidler, on “Rational points on curves” by Arnaldo Garcia and Henning Stichtenoth, on “Towers” by Arnaldo Garcia and Henning Stichtenoth, on “Zeta functions and \(L\)-functions” by Lei Fu, on “\(p\)-adic estimates of zeta functions and \(L\)-functions” by Regis Blache, and finally on “Computing the number of rational points and zeta functions” by Daqing Wan.

Part II closes with Ch. 13 “Miscellaneous theoretical topics” (493–546), discusses a variety of topics over finite fields. This includes “Relations between integers and polynomials over finite fields” by Gove Effinger, “Matrices over finite fields” by Dieter Jungnickel, “Classical groups over finite fields” by Zhe-Xian Wan, “Computational linear algebra over finite fields” by Jean-Guillaume Dumas and Clément Pernet, and ends with“Carlitz and Drinfeld modules” by David Goss.

Part III of the Handbook, containing four chapters, discusses various important applications, including mathematical as well as very practical applications of finite fields. Due to the immense number of papers published in these areas, only those are discussed that treat techniques and topics related to finite fields.

The first chapter is Ch. 14 “Combinatorial” (549–658) including the areas of “Latin squares” by Gary L. Mullen, “Lacunary polynomials over finite fields” by Simeon Ball and Aart Blokhuis, “Affine and projective planes” by Gary Ebert and Leo Storme, “Projective spaces” by James W. P. Hirschfeld and Joseph A. Thas, “Block designs” by Charles J. Colbourn and Jeffrey H. Dinitz, “Difference sets” by Alexander Pott, “Other combinatorial structures” by Jeffrey H. Dinitz and Charles J. Colbourn, “\((t, m, s)\)-nets and \((t, s)\)-sequences” by Harald Niederreiter, “Applications and weights of multiples of primitive and other polynomials” by Brett Stevens, and finally “Ramanujan and expander graphs” by M. Ram Murty and Sebastian M. Cioaba.

Ch. 15 on “Algebraic Coding Theory” (659–739) is another important chapter of the Handbook. First it offers a long introductory section on “Basic coding properties and bounds” by Ian Blake and W. Cary Huffman, then follow sections on “Algebraic-geometry codes” by Harald Niederreiter, “LDPC and Gallager codes over finite fields” by Ian Blake and W. Cary Huffman, “Turbo codes over finite fields” by Oscar Takeshita, “Raptor codes” by Ian Blake and W. Cary Huffman, and “Polar codes” by Simon Litsyn.

Ch. 16 “Cryptography” (741–823), being of equal importance, deals with cryptographic systems over finite fields. In the first section “Introduction to cryptography” by Alfred Menezes various basic issues dealing with cryptography are discussed. Then follow important topics such as “Stream and block ciphers” by Guang Gong and Kishan Chand Gupta, “Multivariate cryptographic systems” by Jintai Ding, “Elliptic curve cryptographic systems” by Andreas Enge, “Hyperelliptic curve cryptographic systems” by Nicolas Thériault, “Cryptosystems arising from abelian varieties” by Kumar Murty, and last but not least “Binary extension field arithmetic for hardware implementations” by M. Anwarul Hasan and Haining Fan.

Finally, in Ch. 17 “Miscellaneous applications” (825–849) several additional applications of finite fields are discussed, as there are “Finite fields in biology” by Franziska Hinkelmann and Reinhard Laubenbacher, “Finite fields in quantum information theory” by Martin Roetteler and Arne Winterhof, “Finite fields in engineering” by Jonathan Jedwab and Kai-Uwe Schmidt.

The authors/editors have collected in their very valuable Bibliography more than 3000 entries which may serve as a quick reference, the more as the relevant pages for each entry are listed. The Handbook closes with a useful 23 page Index. Finally one should mention that each section is meant to be self-contained and that no proofs are given, however, references have been given where proofs of important results can be located.

Though handbooks nowadays are preferably in computerized form, many readers might consider to buy a copy for his own, as it presents such a huge amount of information readily available and masterly presented.

Editors, contributors and publisher are equally congratulated for providing such a beautiful result not only for the finite field community but also for those from the applied areas, especially cryptographers and coding theorists.

Reviewer: Olaf Ninnemann (Berlin)

##### MSC:

11-00 | General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to number theory |

11Txx | Finite fields and commutative rings (number-theoretic aspects) |

12E20 | Finite fields (field-theoretic aspects) |

05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

11G20 | Curves over finite and local fields |

14G15 | Finite ground fields in algebraic geometry |

94A55 | Shift register sequences and sequences over finite alphabets in information and communication theory |

94A60 | Cryptography |