You are here

Algebraic Geometry in Coding Theory and Cryptography

Harald Niederreiter and Chaoping Xing
Princeton University Press
Publication Date: 
Number of Pages: 
[Reviewed by
Darren Glass
, on

To a reader wanting to learn about algebraic geometry, there are many choices of books one can turn to, each of which offers its own spin on both the choice of topics and the presentation. Harald Niederreiter and Chaoping Xing have both written a number of research papers in coding theory, and as such this is the point of view they offer to the reader of their new book Algebraic Geometry in Coding Theory and Cryptography.

The topics covered in the first four chapters are the topics one would expect from most books in algebraic geometry: function fields, varieties, morphisms, curves, divisors, Riemann-Roch spaces, Zeta functions and the Hasse-Weil theorem. Where this book is different from other books is in the final two chapters, which are dedicated to the applications to coding theory and cryptography. The authors start at a basic level with coding theory, defining what a code is and discussing in detail how the curves and divisors and Riemann-Roch spaces of the earlier sections can be used in order to construct codes that have particularly good parameters. In the chapter on cryptography, the authors again start with very basic material on public key cryptosystems and the Diffie-Hellman problem before moving on to discuss cryptosystems based on elliptic and hyperelliptic curves and their divisors. The final sections look at encryption schemes such as the McEliece and Niederreiter (yes, the same Niederreiter) cryptosystems, which use coding theory and algebraic geometric codes in order to encrypt information.

The book lacks the quantity of examples and exercises one might want from a textbook, and there are other books that cover much of the same material (Stichtenoth's Algebraic Function Fields and Codes is a particular favorite of this reviewer, for example). That said, I have found myself reaching for Niederreiter and Xing's book several times in recent weeks, as the exposition in the book is clear and it serves as a nice reference for the material it covers. The bibliography is copious, and the topics covered are well-chosen. This book would make a fine addition to any library or to the shelves of an algebraic geometer wanting to learn some coding theory or vice versa.

Darren Glass is an associate professor of mathematics at Gettysburg College. He can be reached at

Preface ix

Chapter 1: Finite Fields and Function Fields 1
1.1 Structure of Finite Fields 1
1.2 Algebraic Closure of Finite Fields 4
1.3 Irreducible Polynomials 7
1.4 Trace and Norm 9
1.5 Function Fields of One Variable 12
1.6 Extensions of Valuations 25
1.7 Constant Field Extensions 27

Chapter 2: Algebraic Varieties 30
2.1 Affine and Projective Spaces 30
2.2 Algebraic Sets 37
2.3 Varieties 44
2.4 Function Fields of Varieties 50
2.5 Morphisms and Rational Maps 56

Chapter 3: Algebraic Curves 68
3.1 Nonsingular Curves 68
3.2 Maps Between Curves 76
3.3 Divisors 80
3.4 Riemann-Roch Spaces 84
3.5 Riemann's Theorem and Genus 87
3.6 The Riemann-Roch Theorem 89
3.7 Elliptic Curves 95
3.8 Summary: Curves and Function Fields 104

Chapter 4: Rational Places 105
4.1 Zeta Functions 105
4.2 The Hasse-Weil Theorem 115
4.3 Further Bounds and Asymptotic Results 122
4.4 Character Sums 127

Chapter 5: Applications to Coding Theory 147
5.1 Background on Codes 147
5.2 Algebraic-Geometry Codes 151
5.3 Asymptotic Results 155
5.4 NXL and XNL Codes 174
5.5 Function-Field Codes 181
5.6 Applications of Character Sums 187
5.7 Digital Nets 192

Chapter 6: Applications to Cryptography 206
6.1 Background on Cryptography 206
6.2 Elliptic-Curve Cryptosystems 210
6.3 Hyperelliptic-Curve Cryptography 214
6.4 Code-Based Public-Key Cryptosystems 218
6.5 Frameproof Codes 223
6.6 Fast Arithmetic in Finite Fields 233

A Appendix 241
A.1 Topological Spaces 241
A.2 Krull Dimension 244
A.3 Discrete Valuation Rings 245
Bibliography 249
Index 257