Acerca del 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".

De la contraportada

"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

Fragmento. © Reproducción autorizada. Todos los derechos reservados.

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 NOT REPRODUCIBLE IN ASCII] over [F.sub.p]. Let R be the set of all roots of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in k. Then R has exactly [p.sup.n] elements since the derivative of the polynomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is easy to verify that R contains [F.sub.p] and R forms a subfield of [bar.[F.sub.p]] (note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for any [alpha], [member of] [bar.[F.sub.p]] and any integer m [greater than or equal to] 1). Thus, R is exactly the splitting field k, that is, k is a finite field with [p.sup.n] elements. (Uniqueness) Let k [subset or equal to] [bar.[F.sub.p]] be a finite field with q elements. By Proposition 1.1.1(iii), all elements of k are roots of the polynomial [x.sup.q] - x. Thus, k is the splitting field of the polynomial of [x.sup.q] - x over [F.sub.p]. This proves the uniqueness.

The above theorem shows that for given q = [p.sup.n], the finite field with q elements is unique in a fixed algebraic closure [bar.[F.sub.p]]. We denote this finite field by [F.sub.q] and call it the finite field of order q (or with q elements). It follows from the proof of the above theorem that [F.sub.q] is the splitting field of the polynomial [x.sup.q] - x over [F.sub.p], and so [F.sub.q]/[F.sub.p] is a Galois extension of degree n. The following result yields the structure of the Galois group Gal([F.sub.q]/[F.sub.p]).

Lemma 1.1.3. The Galois group Gal([F.sub.q]/[F.sub.p]) with q = [p.sup.n] is a cyclic group of order n with generator [sigma] : [alpha] -> [[alpha].sup.p]. Proof. It is clear that [sigma] is an automorphism in Gal([F.sub.q]/[F.sub.p]). Suppose that [[sigma].sup.m] is the identity for some m [greater than or equal to] 1. Then [[sigma].sup.m]([alpha]) = [alpha], that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], for all [alpha] [member of] [F.sub.q]. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has at least q = [p.sup.n] roots. Therefore, [p.sup.m] [greater than or equal to] [p.sup.n], that is, m [greater than or equal to] n. Hence, the order of [sigma] is equal to n since [absolute value of Gal([F.sub.q]/[F.sub.p])] = n. Lemma 1.1.4. The field [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if m divides n. Proof. If m divides n, then there exists a subgroup H of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [absolute value of H] = n/m since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a cyclic group of order n by Lemma 1.1.3. Let k be the subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] fixed by H. Then [k : [F.sub.p]] = m. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the uniqueness of finite fields. Conversely, let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then the degree [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] divides the degree [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Theorem 1.1.5. Let q be a prime power. Then: (i) [F.sub.q] is a subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every integer n [greater than or equal to] 1. (ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a cyclic group of order n with generator [sigma] : [alpha] -> [[alpha].sup.q]. (iii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if m divides n. Proof. (i) Let q = [p.sup.s] for some prime p and integer s [greater than or equal to] 1. Then by Lemma 1.1.4, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (ii) Using exactly the same arguments as in the proof of Lemma 1.1.3 but replacing p by q, we obtain the proof of (ii). (iii) By Lemma 1.1.4, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subfield of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if ms divides ns. This is equivalent to m dividing n.

We end this section by determining the structure of the multiplicative group [F.sup.*.sub.q] of nonzero elements of a finite field [F.sub.q].

Proposition 1.1.6. The multiplicative group [F.sup.*.sub.q] is cyclic. Proof. Let t [less than or equal to] q - 1 be the largest order of an element of the group [F.sup.*.sub.q]. By the structure theorem for finite abelian groups, the order of any element of [F.sup.*.sub.q] divides t. It follows that every element of [F.sup.*.sub.q] is a root of the polynomial [x.sup.t] - 1, hence, t [greater than or equal to] q - 1, and so t = q - 1. Definition 1.1.7. A generator of the cyclic group [F.sup.*.sub.q] is called a primitive element of [F.sub.q].

Let [gamma] be a generator of [F.sup.*.sub.q]. Then [[gamma].sup.n] is also a generator of [F.sup.*.sub.q] if and only if gcd(n, q - 1) = 1. Thus, we have the following result.

Corollary 1.1.8. There are exactly [phi](q - 1) primitive elements of [F.sub.q], where [phi] is the Euler totient function.

1.2 Algebraic Closure of Finite Fields

Let p be the characteristic of [F.sub.q]. It is clear that the algebraic closure [bar.[F.sub.q]] of [F.sub.q] is the same as [bar.[F.sub.q]].

Theorem 1.2.1. The algebraic closure of [F.sub.q] is the union [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Proof. Put [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is clear that U is a subset of [bar.[F.sub.q]] since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a subset of [bar.[F.sub.q]]. It is also easy to verify that U forms a field. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be a nonconstant polynomial over U. Then for 0 [less than or equal to] i [less than or equal to] s we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [m.sub.i] [greater than or equal to] 1. Hence, by Theorem 1.1.5(iii), f(x) is a polynomial over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where m = [[PI].sup.s.sub.i=0] [m.sub.i]. Let [alpha] be a root of f(x). Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an algebraic extension of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a finite-dimensional vector space over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is also a finite field containing [F.sub.q]. Let r be the degree of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] over [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains exactly [q.sup.rm] elements, that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. So [alpha] is an element of U. This shows that U is the algebraic closure [bar.[F.sub.q]].

We are going to devote the rest of this section to the study of the Galois group Gal([bar.[F.sub.q]]/[F.sub.q]). We start from the definition of the inverse limit for finite groups. For a detailed discussion of inverse limits of groups, we refer to the book by Wilson [130].

A directed set is a nonempty partially ordered set I such that for all [i.sub.1], [i.sub.2] [member of] I, there is an element j [member of] I for which [i.sub.1] [less than or equal to] j and [i.sub.2] [less than or equal to] j.

Definition 1.2.2. An inverse system {[G.sub.i], [[phi].sub.ij]} of finite groups indexed by a directed set I consists of a family {[G.sub.i] : i [member of] I} of finite groups and a family {[phi].sub.ij] [member of] Hom([G.sub.j], [G.sub.i]): i, j [member of] I, i [less than or equal to] j} of maps such that [phi].sub.ij] is the identity on [G.sub.i] for each i and [phi].sub.ij] [omicron] [phi].sub.jk] = [phi].sub.ik] whenever i [less than or equal to] j [less than or equal to] k. Here, Hom([G.sub.j], [G.sub.i]) denotes the set of group homomorphisms from [G.sub.j] to [G.sub.i].

For an inverse system {[G.sub.i], [phi].sub.ij]} of finite groups indexed by a directed set I, we form the Cartesian product [[PI].sub.i [member of] I] [G.sub.i], viewed as a product group. We consider the subset of [[PI].sub.i [member of] I] [G.sub.i] given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is easy to check that D forms a subgroup of [[PI].sub.i [member of] I] [G.sub.i]. We call D the inverse limit of {Gi, ij }, denoted by [lim.sub.[left arrow]] [G.sub.i].

Example 1.2.3. Define a partial order in the set N of positive integers as follows: for m, n [member of] N, let m [less than or equal to] n if and only if m divides n. For each positive integer i, let [G.sub.i] be the cyclic group Z/iZ, and for each pair (i, j) [member of] [N.sup.2] with i|j, define [phi].sub.ij : [bar.n] [member of] [G.sub.j] -> [bar.n] [member of] [G.sub.i], with the bar indicating the formation of a residue class. Then it is easy to verify that the family {Z/iZ, [phi].sub.ij} forms an inverse system of finite groups indexed by N. The inverse limit [lim.sub.[left arrow] Z/iZ is denoted by [??]. Example 1.2.4. Now let [F.sub.q] be the finite field with q elements. We consider the family of Galois groups [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] over [F.sub.q] for each i [member of] N. We define a partial order in N as in Example 1.2.3. For each pair (i, j) [member of] [N.sup.2] with i|j, define the homomorphism [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] stands for the restriction of [[sigma].sub.j] to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] forms an inverse system of finite groups indexed by N. Theorem 1.2.5. We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Proof. For each i [member of] N, we have a homomorphism [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] obtained by restriction. These together yield a homomorphism [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] It is clear that the image of [theta] is contained in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We show in the following that [theta] is an isomorphism onto [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(Continues...)

Excerpted from Algebraic Geometry in Coding Theory and Cryptographyby HARALD NIEDERREITER CHAOPING XING Copyright © 2009 by Princeton University Press. Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.