Advanced Topics in Computational Number Theory

ISBN-13: 9781461264194 / Angielski / Miękka / 2012 / 581 str.

Henri Cohen

Opis

Written by an authority with great practical and teaching experience in the field, this book addresses a number of topics in computational number theory. Chapters one through five form a homogenous subject matter suitable for a six-month or year-long course in computational number theory. The subsequent chapters deal with more miscellaneous subjects.

Recenzje

"Das vorliegende Buch ist eine Fortsetzung des bekannten erkes "A Course in Computational Algebraic Number Theory" (Graduate Texts in Mathematics 138) desselben Autors. ...
So ist das vorliegende Buch ein sehr umfängliches Nachschlagewerk zur algorithmischen Zahlentheorie, das zusammen mit dem ersten Buch des Autors sicherlich eine Standard-Referenz für zahlentheoretische Algorithmen darstellen wird."
Internationale Mathematische Nachrichten, Nr. 187, August 2001

Spis treści

1. Fundamental Results and Algorithms in Dedekind Domains.- 1.1 Introduction.- 1.2 Finitely Generated Modules Over Dedekind Domains.- 1.2.1 Finitely Generated Torsion-Free and Projective Modules.- 1.2.2 Torsion Modules.- 1.3 Basic Algorithms in Dedekind Domains.- 1.3.1 Extended Euclidean Algorithms in Dedekind Domains.- 1.3.2 Deterministic Algorithms for the Approximation Theorem.- 1.3.3 Probabilistic Algorithms.- 1.4 The Hermite Normal Form Algorithm in Dedekind Domains.- 1.4.1 Pseudo-Objects.- 1.4.2 The Hermite Normal Form in Dedekind Domains.- 1.4.3 Reduction Modulo an Ideal.- 1.5 Applications of the HNF Algorithm.- 1.5.1 Modifications to the HNF Pseudo-Basis.- 1.5.2 Operations on Modules and Maps.- 1.5.3 Reduction Modulo p of a Pseudo-Basis.- 1.6 The Modular HNF Algorithm in Dedekind Domains.- 1.6.1 Introduction.- 1.6.2 The Modular HNF Algorithm.- 1.6.3 Computing the Transformation Matrix.- 1.7 The Smith Normal Form Algorithm in Dedekind Domains.- 1.8 Exercises for Chapter 1.- 2. Basic Relative Number Field Algorithms.- 2.1 Compositum of Number Fields and Relative and Absolute Equations.- 2.1.1 Introduction.- 2.1.2 Étale Algebras.- 2.1.3 Compositum of Two Number Fields.- 2.1.4 Computing (?1 and ?2.- 2.1.5 Relative and Absolute Defining Polynomials.- 2.1.6 Compositum with Normal Extensions.- 2.2 Arithmetic of Relative Extensions.- 2.2.1 Relative Signatures.- 2.2.2 Relative Norm, Trace, and Characteristic Polynomial.- 2.2.3 Integral Pseudo-Bases.- 2.2.4 Discriminants.- 2.2.5 Norms of Ideals in Relative Extensions.- 2.3 Representation and Operations on Ideals.- 2.3.1 Representation of Ideals.- 2.3.2 Representation of Prime Ideals.- 2.3.3 Computing Valuations.- 2.3.4 Operations on Ideals.- 2.3.5 Ideal Factorization and Ideal Lists.- 2.4 The Relative Round 2 Algorithm and Related Algorithms.- 2.4.1 The Relative Round 2 Algorithm.- 2.4.2 Relative Polynomial Reduction.- 2.4.3 Prime Ideal Decomposition.- 2.5 Relative and Absolute Representations.- 2.5.1 Relative and Absolute Discriminants.- 2.5.2 Relative and Absolute Bases.- 2.5.3 Ups and Downs for Ideals.- 2.6 Relative Quadratic Extensions and Quadratic Forms.- 2.6.1 Integral Pseudo-Basis, Discriminant.- 2.6.2 Representation of Ideals.- 2.6.3 Representation of Prime Ideals.- 2.6.4 Composition of Pseudo-Quadratic Forms.- 2.6.5 Reduction of Pseudo-Quadratic Forms.- 2.7 Exercises for Chapter 2.- 3. The Fundamental Theorems of Global Class Field Theory.- 3.1 Prologue: Hilbert Class Fields.- 3.2 Ray Class Groups.- 3.2.1 Basic Definitions and Notation.- 3.3 Congruence Subgroups: One Side of Class Field Theory.- 3.3.1 Motivation for the Equivalence Relation.- 3.3.2 Study of the Equivalence Relation.- 3.3.3 Characters of Congruence Subgroups.- 3.3.4 Conditions on the Conductor and Examples.- 3.4 Abelian Extensions: The Other Side of Class Field Theory.- 3.4.1 The Conductor of an Abelian Extension.- 3.4.2 The Frobenius Homomorphism.- 3.4.3 The Artin Map and the Artin Group Am(L/K).- 3.4.4 The Norm Group (or Takagi Group) Tm(L/K).- 3.5 Putting Both Sides Together: The Takagi Existence Theorem 154.- 3.5.1 The Takagi Existence Theorem.- 3.5.2 Signatures, Characters, and Discriminants.- 3.6 Exercises for Chapter 3.- 4. Computational Class Field Theory.- 4.1 Algorithms on Finite Abelian groups.- 4.1.1 Algorithmic Representation of Groups.- 4.1.2 Algorithmic Representation of Subgroups.- 4.1.3 Computing Quotients.- 4.1.4 Computing Group Extensions.- 4.1.5 Right Four-Term Exact Sequences.- 4.1.6 Computing Images, Inverse Images, and Kernels.- 4.1.7 Left Four-Term Exact Sequences.- 4.1.8 Operations on Subgroups.- 4.1.9 p-Sylow Subgroups of Finite Abelian Groups.- 4.1.10 Enumeration of Subgroups.- 4.1.11 Application to the Solution of Linear Equations and Congruences.- 4.2 Computing the Structure of (?K/m)*.- 4.2.1 Standard Reductions of the Problem.- 4.2.2 The Use of p-adic Logarithms.- 4.2.3 Computing (?K/pk)* by Induction.- 4.2.4 Representation of Elements of (?K/m)*.- 4.2.5 Computing (?K/m)*.- 4.3 Computing Ray Class Groups.- 4.3.1 The Basic Ray Class Group Algorithm.- 4.3.2 Size Reduction of Elements and Ideals.- 4.4 Computations in Class Field Theory.- 4.4.1 Computations on Congruence Subgroups.- 4.4.2 Computations on Abelian Extensions.- 4.4.3 Conductors of Characters.- 4.5 Exercises for Chapter 4.- 5. Computing Defining Polynomials Using Kummer Theory.- 5.1 General Strategy for Using Kummer Theory.- 5.1.1 Reduction to Cyclic Extensions of Prime Power Degree.- 5.1.2 The Four Methods.- 5.2 Kummer Theory Using Hecke’s Theorem When ?? ? K.- 5.2.1 Characterization of Cyclic Extensions of Conductor m and Degree ?.- 5.2.2 Virtual Units and the ?-Selmer Group.- 5.2.3 Construction of Cyclic Extensions of Prime Degree and Conductor m.- 5.2.4 Algorithmic Kummer Theory When ?? ? K Using Hecke.- 5.3 Kummer Theory Using Hecke When ?? ? K.- 5.3.1 Eigenspace Decomposition for the Action of ?.- 5.3.2 Lift in Characteristic 0.- 5.3.3 Action of ? on Units.- 5.3.4 Action of ? on Virtual Units.- 5.3.5 Action of ? on the Class Group.- 5.3.6 Algorithmic Kummer Theory When ?? ? K Using Hecke.- 5.4 Explicit Use of the Artin Map in Kummer Theory When ?n ? K.- 5.4.1 Action of the Artin Map on Kummer Extensions.- 5.4.2 Reduction to ? ? US(K)/US(K)n for a Suitable S.- 5.4.3 Construction of the Extension L/K by Kummer Theory.- 5.4.4 Picking the Correct ?.- 5.4.5 Algorithmic Kummer Theory When ?n ? K Using Artin.- 5.5 Explicit Use of the Artin Map When ?n ? K.- 5.5.1 The Extension Kz/K.- 5.5.2 The Extensions Lz/Kz and Lz/K.- 5.5.3 Going Down to the Extension L/K.- 5.5.4 Algorithmic Kummer Theory When ?n ? K Using Artin.- 5.5.5 Comparison of the Methods.- 5.6 Two Detailed Examples.- 5.6.1 Example 1.- 5.6.2 Example 2.- 5.7 Exercises for Chapter 5.- 6. Computing Defining Polynomials Using Analytic Methods.- 6.1 The Use of Stark Units and Stark’s Conjecture.- 6.1.1 Stark’s Conjecture.- 6.1.2 Computation of ?K,S?(0, ?).- 6.1.3 Real Class Fields of Real Quadratic Fields.- 6.2 Algorithms for Real Class Fields of Real Quadratic Fields.- 6.2.1 Finding a Suitable Extension N / K.- 6.2.2 Computing the Character Values.- 6.2.3 Computation of W(?).- 6.2.4 Recognizing an Element of ?K.- 6.2.5 Sketch of the Complete Algorithm.- 6.2.6 The Special Case of Hilbert Class Fields.- 6.3 The Use of Complex Multiplication.- 6.3.1 Introduction.- 6.3.2 Construction of Unramified Abelian Extensions.- 6.3.3 Quasi-Elliptic Functions.- 6.3.4 Construction of Ramified Abelian Extensions Using Complex Multiplication.- 6.4 Exercises for Chapter 6.- 7. Variations on Class and Unit Groups.- 7.1 Relative Class Groups.- 7.1.1 Relative Class Group for iL/K.- 7.1.2 Relative Class Group for NL/K.- 7.2 Relative Units and Regulators.- 7.2.1 Relative Units and Regulators for iL/K.- 7.2.2 Relative Units and Regulators for NL/K.- 7.3 Algorithms for Computing Relative Class and Unit Groups.- 7.3.1 Using Absolute Algorithms.- 7.3.2 Relative Ideal Reduction.- 7.3.3 Using Relative Algorithms.- 7.3.4 An Example.- 7.4 Inverting Prime Ideals.- 7.4.1 Definitions and Results.- 7.4.2 Algorithms for the S-Class Group and S-Unit Group.- 7.5 Solving Norm Equations.- 7.5.1 Introduction.- 7.5.2 The Galois Case.- 7.5.3 The Non-Galois Case.- 7.5.4 Algorithmic Solution of Relative Norm Equations.- 7.6 Exercises for Chapter 7.- 8. Cubic Number Fields.- 8.1 General Binary Forms.- 8.2 Binary Cubic Forms and Cubic Number Fields.- 8.3 Algorithmic Characterization of the Set U.- 8.4 The Davenport-Heilbronn Theorem.- 8.5 Real Cubic Fields.- 8.6 Complex Cubic Fields.- 8.7 Implementation and Results.- 8.7.1 The Algorithms.- 8.7.2 Results.- 8.8 Exercises for Chapter 8.- 9. Number Field Table Constructions.- 9.1 Introduction.- 9.2 Using Class Field Theory.- 9.2.1 Finding Small Discriminants.- 9.2.2 Relative Quadratic Extensions.- 9.2.3 Relative Cubic Extensions.- 9.2.4 Finding the Smallest Discriminants Using Class Field Theory.- 9.3 Using the Geometry of Numbers.- 9.3.1 The General Procedure.- 9.3.2 General Inequalities.- 9.3.3 The Totally Real Case.- 9.3.4 The Use of Lagrange Multipliers.- 9.4 Construction of Tables of Quartic Fields.- 9.4.1 Easy Inequalities for All Signatures.- 9.4.2 Signature (0,2): The Totally Complex Case.- 9.4.3 Signature (2, 1): The Mixed Case.- 9.4.4 Signature (4, 0): The Totally Real Case.- 9.4.5 Imprimitive Degree 4 Fields.- 9.5 Miscellaneous Methods (in Brief).- 9.5.1 Euclidean Number Fields.- 9.5.2 Small Polynomial Discriminants.- 9.6 Exercises for Chapter 9.- 10. Appendix A: Theoretical Results.- 10.1 Ramification Groups and Applications.- 10.1.1 A Variant of Nakayama’s Lemma.- 10.1.2 The Decomposition and Inertia Groups.- 10.1.3 Higher Ramification Groups.- 10.1.4 Application to Different and Conductor Computations.- 10.1.5 Application to Dihedral Extensions of Prime Degree.- 10.2 Kummer Theory.- 10.2.1 Basic Lemmas.- 10.2.2 The Basic Theorem of Kummer Theory.- 10.2.3 Hecke’s Theorem.- 10.2.4 Algorithms for ?th Powers.- 10.3 Dirichlet Series with Functional Equation.- 10.3.1 Computing L-Functions Using Rapidly Convergent Series.- 10.3.2 Computation of Fi(s, x).- 10.4 Exercises for Chapter 10.- 11. Appendix B: Electronic Information.- 11.1 General Computer Algebra Systems.- 11.2 Semi-general Computer Algebra Systems.- 11.3 More Specialized Packages and Programs.- 11.4 Specific Packages for Curves.- 11.5 Databases and Servers.- 11.6 Mailing Lists, Websites, and Newsgroups.- 11.7 Packages Not Directly Related to Number Theory.- 12. Appendix C: Tables.- 12.1 Hilbert Class Fields of Quadratic Fields.- 12.1.1 Hilbert Class Fields of Real Quadratic Fields.- 12.1.2 Hilbert Class Fields of Imaginary Quadratic Fields.- 12.2 Small Discriminants.- 12.2.1 Lower Bounds for Root Discriminants.- 12.2.2 Totally Complex Number Fields of Smallest Discriminant.- Index of Notation.- Index of Algorithms.- General Index.

O autorze

Preliminary Text. Do not use. The present book addresses a number of specific topics in computational number theory whereby the author is not attempting to be exhaustive in the choice of subjects. Written by an authority with great practical and teaching experience in the field, this book together with the author's earlier book will become the standard and indispensable reference on the subject.