《计算代数数值论教程 A Course in Computational Algebraic Number Theory》求取 ⇩

Chapter 1Fundamental Number-Theoretic Algorithms1

1.1Introduction1

1.1.1 Algorithms1

1.1.2 Multi-precision2

1.1.3 Base Fields and Rings5

1.1.4 Notations6

1.2 The Powering Algorithms8

1.3Euclid's Algorithms12

1.3.1 Euclid's and Lehmer's Algorithms12

1.3.2 Euclid's Extended Algorithms16

1.3.3 The Chinese Remainder Theorem19

1.3.4 Continued Fraction Expansions of Real Numbers21

1.4The Legendre Symbol24

1.4.1 The Groups(Z/nZ)24

1.4.2 The Legendre-Jacobi-Kronecker Symbol27

1.5Computing Square Roots Modulo p31

1.5.1 The Algorithm of Tonelli and Shanks32

1.5.2 The Algorithm of Cornacchia34

1.6 Solving Polynomial Equations Modulo p36

1.7Power Detection38

1.7.1 Integer Square Roots38

1.7.2 Square Detection39

1.7.3 Prime Power Detection41

1.8 Exercises for Chapter 142

Chapter 2Algorithms for Linear Algebra and Lattices46

2.1 Introduction46

2.2Linear Algebra Algorithms on Square Matrices47

2.2.1 Generalities on Linear Algebra Algorithms47

2.2.2 Gaussian Elimination and Solving Linear Systems48

2.2.3 Computing Determinants50

2.2.4 Computing the Characteristic Polynomial53

2.3Linear Algebra on General Matrices57

2.3.1 Kernel and Image57

2.3.2 Inverse Image and Supplement60

2.3.3 Operations on Subspaces62

2.3.4 Remarks on Modules64

2.4Z-Modules and the Hermite and Smith Normal Forms66

2.4.1 Introduction to Z-Modules66

2.4.2 The Hermite Normal Form67

2.4.3 Applications of the Hermite Normal Form73

2.4.4 The Smith Normal Form and Applications75

2.5Generalities on Lattices79

2.5.1 Lattices and Quadratic Forms79

2.5.2 The Gram-Schmidt Orthogonalization Procedure82

2.6Lattice Reduction Algorithms84

2.6.1 The LLL Algorithm84

2.6.2 The LLL Algorithm with Deep Insertions90

2.6.3 The Integral LLL Algorithm92

2.6.4 LLL Algorithms for Linearly Dependent Vectors95

2.7Applications of the LLL Algorithm97

2.7.1 Computing the Integer Kernel and Image of a Matrix97

2.7.2 Linear and Algebraic Dependence Using LLL100

2.7.3 Finding Small Vectors in Lattices103

2.8 Exercises for Chapter 2106

Chapter 3Algorithms on Polynomials109

3.1Basic Algorithms109

3.1.1 Representation of Polynomials109

3.1.2 Multiplication of Polynomials110

3.1.3 Division of Polynomials111

3.2Euclid's Algorithms for Polynomials113

3.2.1 Polynomials over a Field113

3.2.2 Unique Factorization Domains (UFD's)114

3.2.3 Polynomials over Unique Factorization Domains116

3.2.4 Euclid's Algorithm for Polynomials over a UFD117

3.3The Sub-Resultant Algorithm118

3.3.1 Description of the Algorithm118

3.3.2 Resultants and Discriminants119

3.3.3 Resultants over a Non-Exact Domain123

3.4Factorization of Polynomials Modulo p124

3.4.1 General Strategy124

3.4.2 Squarefree Factorization125

3.4.3 Distinct Degree Factorization126

3.4.4 Final Splitting127

3.5Factorization of Polynomials over Z or Q133

3.5.1 Bounds on Polynomial Factors134

3.5.2 A First Approach to Factoring over Z135

3.5.3 Factorization Modulo pe:Hensel's Lemma137

3.5.4 Factorization of Polynomials over Z139

3.5.5 Discussion141

3.6Additional Polynomial Algorithms142

3.6.1 Modular Methods for Computing GCD's in Z[X]142

3.6.2 Factorization of Polynomials over a Number Field143

3.6.3 A Root Finding Algorithm over C146

3.7 Exercises for Chapter 3148

Chapter 4Algorithms for Algebraic Number Theory I153

4.1Algebraic Numbers and Number Fields153

4.1.1 Basic Definitions and Properties of Algebraic Numbers153

4.1.2 Number Fields154

4.2Representation and Operations on Algebraic Numbers158

4.2.1 Algebraic Numbers as Roots of their Minimal Polynomial158

4.2.2 The Standard Representation of an Algebraic Number159

4.2.3 The Matrix(or Regular) Representation of an Algebraic Number160

4.2.4 The Conjugate Vector Representation of an Algebraic Number161

4.3 Trace,Norm and Characteristic Polynomial162

4.4Discriminants,Integral Bases and Polynomial Reduction165

4.4.1 Discriminants and Integral Bases165

4.4.2 The Polynomial Reduction Algorithm168

4.5The Subfield Problem and Applications174

4.5.1 The Subfield Problem Using the LLL Algorithm174

4.5.2 The Subfield Problem Using Linear Algebra over C175

4.5.3 The Subfield Problem Using Algebraic Algorithms177

4.5.4 Applications of the Solutions to the Subfield Problem179

4.6Orders and Ideals181

4.6.1 Basic Definitions181

4.6.2 Ideals of Zk186

4.7Representation of Modules and Ideal188

4.7.1 Modules and the Hermite Normal Form188

4.7.2 Representation of Ideals190

4.8Decomposition of Prime Numbers I196

4.8.1 Definitions and Main Results196

4.8.2 A Simple Algorithm for the Decomposition of Primes199

4.8.3 Computing Valuations201

4.8.4 Ideal Inversion and the Different204

4.9Units and Ideal Classes207

4.9.1 The Class Group207

4.9.2 Units and the Regulator209

4.9.3 Conclusion:the Main Computational Tasks of Algebraic Number Theory217

4.10 Exercises for Chapter 4217

Chapter 5Algorithms for Quadratic Fields223

5.1 Discriminant,Integral Basis and Decomposition of Primes223

5.2 Ideals and Quadratic Forms225

5.3Class Numbers of Imaginary Quadratic Fields231

5.3.1 Computing Class Numbers Using Reduced Forms231

5.3.2 Computing Class Numbers Using Modular Forms234

5.3.3 Computing Class Numbers Using Analytic Formulas237

5.4Class Groups of Imaginary Quadratic Fields240

5.4.1 Shanks's Baby Step Giant Step Method240

5.4.2 Reduction and Composition of Quadratic Forms243

5.4.3 Class Groups Using Shanks's Method250

5.5McCurley's Sub-exponential Algorithm252

5.5.1 Outline of the Algorithm252

5.5.2 Detailed Description of the Algorithm255

5.5.3 Atkin's Variant260

5.6Class Groups of Real Quadratic Fields262

5.6.1 Computing Class Numbers Using Reduced Forms262

5.6.2 Computing Class Numbers Using Analytic Formulas266

5.6.3 A Heuristic Method of Shahks268

5.7Computation of the Fundamental Unit and of the Regulator269

5.7.1 Description of the Algorithms269

5.7.2 Analysis of the Continued Fraction Algorithm271

5.7.3 Computation of the Regulator278

5.8The Infrastructure Method of Shanks279

5.8.1 The Distance Function279

5.8.2 Description of the Algorithm283

5.8.3 Compact Representation of the Fundamental Unit285

5.8.4 Other Application and Generalization of the Distance Function287

5.9Buchmann's Sub-exponential Algorithm288

5.9.1 Outline of the Algorithm289

5.9.2 Detailed Description of Buchmann's Sub-exponential Algorithm291

5.10The Cohen-Lenstra Heuristics295

5.10.1 Results and Heuristics for Imaginary Quadratic Fields295

5.10.2 Results and Heuristics for Real Quadratic Fields297

5.11 Exercises for Chapter 5298

Chapter 6Algorithms for Algebraic Number Theory II303

6.1Computing the Maximal Order303

6.1.1 The Pohst-Zassenhaus Theorem303

6 1.2The Dedekind Criterion305

6.1.3 Outline of the Round 2 Algorithm308

6.1.4 Detailed Description of the Round 2 Algorithm311

6.2Decomposition of Prime Numbers II312

6.2.1 Newton Polygons313

6.2.2 Theoretical Description of the Buchmann-Lenstra Method315

6.2.3 Multiplying and Dividing Ideals Modulo p317

6.2 4Splitting of Separable Algebras over Fp318

6.2.5 Detailed Description of the Algorithm for Prime Decomposition320

6.3Computing Galois Groups322

6.3.1 The Resolvent Method322

6.3.2 Degree3325

6.3.3 Degree4325

6.3.4 Degree5328

6.3.5 Degree6329

6.3.6 Degree7331

6.3.7 A List of Test Polynomials333

6.4Examples of Families of Number Fields334

6.4.1 Making Tables of Number Fields334

6.4.2 Cyclic Cubic Fields336

6.4.3 Pure Cubic Fields343

6.4.4 Decomposition of Primes in Pure Cubic Fields347

6.4.5 General Cubic Fields351

6.5Computing the Class Group,Regulator and Fundamental Units352

6.5.1 Ideal Reduction352

6.5.2 Computing the Relation Matrix354

6.5.3 Computing the Regulator and a System of Fundamental Units357

6.5.4 The General Class Group and Unit Algorithm358

6.5.5 The Principal Ideal Problem360

6.6 Exercises for Chapter 6362

Chapter 7Introduction to Elliptic Curves367

7.1Basic Definitions367

7.1.1 Introduction367

7.1.2 Elliptic Integrals and Elliptic Functions367

7.1.3 Elliptic Curves over a Field369

7.1.4 Points on Elliptic Curves372

7.2Complex Multiplication and Class Numbers376

7.2.1 Maps Between Complex Elliptic Curves377

7.2.2 Isogenies379

7.2.3 Complex Multiplication381

7.2.4 Complex Multiplication and Hilbert Class Fields384

7.2.5 Modular Equations385

7.3Rank and L-functions386

7.3.1 The Zeta Function of a Variety387

7.3.2 L-functions of Elliptic Curves388

7.3.3 The Taniyama-Weil Conjecture390

7.3.4 The Birch and Swinnerton-Dyer Conjecture392

7.4Algorithms for Elliptic Curves394

7.4.1 Algorithms for Elliptic Curves over C394

7.4.2 Algorithm for Reducing a General Cubic399

7.4.3 Algorithms for Elliptic Curves over Fp403

7.5Algorithms for Elliptic Curves over Q406

7.5.1 Tate's algorithm406

7.5.2 Computing rational points410

7.5.3 Algorithms for computing the L-function413

7.6Algorithms for Elliptic Curves with Complex Multiplication414

7.6.1 Computing the Complex Values of j(r)414

7.6.2 Computing the Hilbert Class Polynomials415

7.6.3 Computing Weber Class Polynomials416

7.7 Exercises for Chapter 7417

Chapter 8Factoring in the Dark Ages419

8.1 Factoring and Primality Testing419

8.2 Compositeness Tests421

8.3Primality Tests423

8.3.1 The Pocklington-Lehmer N-1 Test423

8.3.2 Briefly,Other Tests424

8.4 Lehman's Method425

8.5Pollard's p Method426

8.5.1 Outline of the Method426

8.5.2 Methods for Detecting Periodicity427

8.5.3 Brent's Modified Algorithm429

8.5.4 Analysis of the Algorithm430

8.6 Shanks's Class Group Method433

8.7 Shanks's SQUFOF434

8.8The p-1-method438

8.8.1 The First Stage439

8.8.2 The Second Stage440

8.8.3 Other Algorithms of the Same Type441

8.9 Exercises for Chapter 8442

Chapter 9Modern Primality Tests445

9.1The Jacobi Sum Test446

9.1.1 Group Rings of Cyclotomic Extensions446

9.1.2 Characters,Gauss Sums and Jacobi Sums448

9.1.3 The Basic Test450

9.1.4 Checking Condition？p455

9.1.5 The Use of Jacobi Sums457

9.1.6 Detailed Description of the Algorithm463

9.1.7 Discussion465

9.2The Elliptic Curve Test467

9.2.1 The Goldwasser-Kilian Test467

9.2.2 Atkin's Test471

9.3 Exercises for Chapter 9475

Chapter 10Modern Factoring Methods477

10.1 The Continued Fraction Method477

10.2The Class Group Method481

10.2.1 Sketch of the Method481

10.2.2 The Schnorr-Lenstra Factoring Method482

10.3The Elliptic Curve Method484

10.3.1 Sketch of the Method484

10.3.2 Elliptic Curves Modulo N485

10.3.3 The ECM Factoring Method of Lenstra487

10.3.4 Practical Considerations489

10.4The Multiple Polynomial Quadratic Sieve490

10.4.1 The Basic Quadratic Sieve Algorithm491

10.4.2 The Multiple Polynomisl Quadratic Sieve492

10.4.3 Improvements to the MPQS Algorithm494

10.5The Number Field Sieve495

10.5.1 Introduction495

10.5.2 Description of the Special NFS when h(K)=1496

10.5.3 Description of the Special NFS when h(K)>1500

10.5.4 Description of the General NFS501

10.5.5 Miscellaneous Improvements to the Number Field Sieve503

10.6 Exercises for Chapter 10504

Appendix A Packages for Number Theory507

Appendix B Some Useful Tables513

B.1Table of Class Numbers of Complex Quadratic Fields513

B.2 Table of Class Numbers and Units of Real Quadratic Fields515

B.3 Table of Class Numbers and Units of Complex Cubic Fields519

B.4 Table of Class Numbers and Units of Totally Real Cubic Fields521

B.5 Table of Elliptic Curves524

Bibliography527

Index540