Algebraic Geometry in Coding Theory and Cryptography - Hardcover

Niederreiter, Harald; Xing, Chaoping

Hardcover

ISBN 10: 0691102880 ISBN 13: 9780691102887

Verlag: Princeton University Press, 2009

Inhaltsangabe

This textbook equips graduate students and advanced undergraduates with the necessary theoretical tools for applying algebraic geometry to information theory, and it covers primary applications in coding theory and cryptography. Harald Niederreiter and Chaoping Xing provide the first detailed discussion of the interplay between nonsingular projective curves and algebraic function fields over finite fields. This interplay is fundamental to research in the field today, yet until now no other textbook has featured complete proofs of it. Niederreiter and Xing cover classical applications like algebraic-geometry codes and elliptic-curve cryptosystems as well as material not treated by other books, including function-field codes, digital nets, code-based public-key cryptosystems, and frameproof codes. Combining a systematic development of theory with a broad selection of real-world applications, this is the most comprehensive yet accessible introduction to the field available.

• Introduces graduate students and advanced undergraduates to the foundations of algebraic geometry for applications to information theory


• Provides the first detailed discussion of the interplay between projective curves and algebraic function fields over finite fields


• Includes applications to coding theory and cryptography


• Covers the latest advances in algebraic-geometry codes


• Features applications to cryptography not treated in other books

Über diesen Titel

Ü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

By HARALD NIEDERREITER CHAOPING XING

PRINCETON UNIVERSITY PRESS

Copyright © 2009 Princeton University Press
All right reserved.
ISBN: 978-0-691-10288-7

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

Finite Fields and Function Fields

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...

Details zur Ausgabe

• Verlag: Princeton University Press
• Erscheinungsdatum: 2009
• Sprache: Englisch
• ISBN 10: 0691102880
• ISBN 13: 9780691102887
• Einband: Gebundene Ausgabe
• Anzahl der Seiten: 260
• Kontakt zum Hersteller: Nicht verfügbar
• Verantwortliche Person: Buchbär; info@buchbaer.de; ; Weberstr. 67; Osnabrück; 49084; Deutschland