Über die Autorin bzw. den Autor

Harald Niederreiter is professor of mathematics and computer science at the National University of Singapore. Chaoping Xing is professor of mathematics at the Nanyang Technological University in Singapore. They are the authors of Rational Points on Curves over Finite Fields: Theory and Applications.

Von der hinteren Coverseite

"This is a beautifully written volume that gives the necessary background to read the research literature on coding and cryptography based on concepts from curves in algebraic geometries. Both of the authors are outstanding researchers, well known for the clarity and depth of their contributions. This work is a valuable and welcome addition to the literature on coding and cryptography."--Ian F. Blake, University of British Columbia

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Algebraic Geometry in Coding Theory and Cryptography

PRINCETON UNIVERSITY PRESS

Contents

Preface.......................................................ix1 Finite Fields and Function Fields..........................11.1 Structure of Finite Fields................................11.2 Algebraic Closure of Finite Fields........................41.3 Irreducible Polynomials...................................71.4 Trace and Norm............................................91.5 Function Fields of One Variable...........................121.6 Extensions of Valuations..................................251.7 Constant Field Extensions.................................272 Algebraic Varieties........................................302.1 Affine and Projective Spaces..............................302.2 Algebraic Sets............................................372.3 Varieties.................................................442.4 Function Fields of Varieties..............................502.5 Morphisms and Rational Maps...............................563 Algebraic Curves...........................................683.1 Nonsingular Curves........................................683.2 Maps Between Curves.......................................763.3 Divisors..................................................803.4 Riemann-Roch Spaces.......................................843.5 Riemann's Theorem and Genus...............................873.6 The Riemann-Roch Theorem..................................893.7 Elliptic Curves...........................................953.8 Summary: Curves and Function Fields.......................1044 Rational Places............................................1054.1 Zeta Functions............................................1054.2 The Hasse-Weil Theorem....................................1154.3 Further Bounds and Asymptotic Results.....................1224.4 Character Sums............................................1275 Applications to Coding Theory..............................1475.1 Background on Codes.......................................1475.2 Algebraic-Geometry Codes..................................1515.3 Asymptotic Results........................................1555.4 NXL and XNL Codes.........................................1745.5 Function-Field Codes......................................1815.6 Applications of Character Sums............................1875.7 Digital Nets..............................................1926 Applications to Cryptography...............................2066.1 Background on Cryptography................................2066.2 Elliptic-Curve Cryptosystems..............................2106.3 Hyperelliptic-Curve Cryptography..........................2146.4 Code-Based Public-Key Cryptosystems.......................2186.5 Frameproof Codes..........................................2236.6 Fast Arithmetic in Finite Fields..........................233A Appendix...................................................241A.1 Topological Spaces........................................241A.2 Krull Dimension...........................................244A.3 Discrete Valuation Rings..................................245Bibliography..................................................249Index.........................................................257

Chapter One

In the first part of this chapter, we describe the basic results on finite fields, which are our ground fields in the later chapters on applications. The second part is devoted to the study of function fields.

Section 1.1 presents some fundamental results on finite fields, such as the existence and uniqueness of finite fields and the fact that the multiplicative group of a finite field is cyclic. The algebraic closure of a finite field and its Galois group are discussed in Section 1.2. In Section 1.3, we study conjugates of an element and roots of irreducible polynomials and determine the number of monic irreducible polynomials of given degree over a finite field. In Section 1.4, we consider traces and norms relative to finite extensions of finite fields.

A function field governs the abstract algebraic aspects of an algebraic curve. Before proceeding to the geometric aspects of algebraic curves in the next chapters, we present the basic facts on function fields. In particular, we concentrate on algebraic function fields of one variable and their extensions including constant field extensions. This material is covered in Sections 1.5, 1.6, and 1.7.

One of the features in this chapter is that we treat finite fields using the Galois action. This is essential because the Galois action plays a key role in the study of algebraic curves over finite fields. For comprehensive treatments of finite fields, we refer to the books by Lidl and Niederreiter [71, 72].

1.1 Structure of Finite Fields

For a prime number p, the residue class ring Z/pZ of the ring Z of integers forms a field. We also denote Z/pZ by [F.sub.p]. It is a prime field in the sense that there are no proper subfields of [F.sub.p]. There are exactly p elements in [F.sub.p]. In general, a field is called a finite field if it contains only a finite number of elements.

Proposition 1.1.1. Let k be a finite field with q elements. Then:

(i) there exists a prime p such that [F.sub.p] [subset or equal to] k;

(ii) q = [p.sup.n] for some integer n [greater than or equal to] 1;

(iii) [[alpha].sup.q] = [alpha] for all [alpha] [member of] k.

Proof.

(i) Since k has only q < [infinity] elements, the characteristic of k must be a prime p. Thus, [F.sub.p] is the prime subfield of k.

(ii) We consider k as a vector space over [F.sub.p]. Since k is finite, the dimension [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (k) is also finite. Let {[[alpha].sub.1], ..., [[alpha].sub.n]} be a basis of k over [F.sub.p]. Then each element of k can be uniquely represented in the form [a.sub.1][[alpha].sub.1]1 + ... + [a.sub.n]][alpha].sub.n] with [a.sub.1], ..., [a.sub.n] [member of] [F.sub.p]. Thus, q = [p.sup.n].

(iii) It is trivial that [[alpha].sup.q] = [alpha] if [alpha] = 0. Assume that [alpha] is a nonzero element of k. Since all nonzero elements of k form a multiplicative group k* of order q - 1, we have [[alpha].sup.q-1] = 1, and so [[alpha].sup.q] = [alpha].

Using the above proposition, we can show the most fundamental result concerning the existence and uniqueness of finite fields.

Theorem 1.1.2. For every prime p and every integer n [greater than or equal to] 1, there exists a finite field with [p.sup.n] elements. Any finite field with q = [p.sup.n] elements is isomorphic to the splitting field of the polynomial [x.sup.q] - x over [F.sub.p]. Proof. (Existence) Let [bar.[F.sub.p]] be an algebraic closure of [F.sub.p] and let k [subset or equal to] [bar.[F.sub.p]] be the splitting field of the polynomial [MATHEMATICAL EXPRESSION...