3696 Kb
 

Западные традиции книгопечатания, в отличие от русских, выносят оглавление и предисловие в отдельный блок с отдельной нумерацией римскими цифрами. Поэтому при склейке DjVu-файлов, содержащих главы книги, в один общий файл этот мелкий блочок оглавления-предисловия приходится или игнорировать, или добавлять самым последним (иначе в DjVu-plugin'е нумерация страниц будет не совпадать с печатным оригиналом). Для тех, кто рассматривает выкладываемые мною файлы как полуфабрикат, который перед прочтением надо распечатать (сам не люблю читать с экрана большие тексты, тем более если они требуют вдумчивого отношения), добавляю этот "нулевой" файл оглавления (178 Kb), чтобы в итоге после печати получилась вся книга "as is". E.G.A.



Acknowledgements
Preface
 
Chapter 1.
Fundamental Number-Theoretic Algorithms
1.1. Introduction1
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.3. Euclid'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.4. The Legendre Symbol24
1.4.1. The Groups (Z/nZ)*24
1.4.2. The Legendre–Jacobi–Kronecker Symbol27
1.5. Computing 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.7. Power 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 2.
Algorithms for Linear Algebra and Lattices
2.1. Introduction46
2.2. Linear 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.3. Linear 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.4. Z-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.5. Generalities on Lattices79
2.5.1. Lattices and Quadratic Forms79
2.5.2. The Gram–Schmidt Orthogonalization Procedure82
2.6. Lattice 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.7. Applications 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 3.
Algorithms on Polynomials
3.1. Basic Algorithms109
3.1.1. Representation of Polynomials109
3.1.2. Multiplication of Polynomials110
3.1.3. Division of Polynomials111
3.2. Euclid'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.3. The 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.4. Factorization 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.5. Factorization 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.6. Additional 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 Z146
3.7. Exercises for Chapter 3148
 
Chapter 4.
Algorithms for Algebraic Number Theory I
4.1. Algebraic Numbers and Number Fields153
4.1.1. Basic Definitions and Properties of Algebraic Numbers153
4.1.2. Number Fields154
4.2. Representation 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.4. Discriminants, Integral Bases and Polynomial Reduction165
4.4.1. Discriminants and Integral Bases165
4.4.2. The Polynomial Reduction Algorithm168
4.5. The 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.6. Orders and Ideals181
4.6.1. Basic Definitions181
4.6.2. Ideals of ZK186
4.7. Representation of Modules and Ideals188
4.7.1. Modules and the Hermite Normal Form188
4.7.2. Representation of Ideals190
4.8. Decomposition 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.9. Units 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 5.
Algorithms for Quadratic Fields
5.1. Discriminant, Integral Basis and Decomposition of Primes223
5.2. Ideals and Quadratic Forms225
5.3. Class 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.4. Class 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.5. McCurley'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.6. Class 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 Shanks268
5.7. Computation 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.8. The 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.9. Buchmann's Sub-exponential Algorithm288
5.9.1. Outline of the Algorithm289
5.9.2. Detailed Description of Buchmann's Sub-exponential Algorithm291
5.10. The 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 6.
Algorithms for Algebraic Number Theory II
6.1. Computing the Maximal Order303
6.1.1. The Pohst–Zassenhaus Theorem303
6.1.2. The Dedekind Criterion305
6.1.3. Outline of the Round 2 Algorithm308
6.1.4. Detailed Description of the Round 2 Algorithm311
6.2. Decomposition 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.4. Splitting of Separable Algebras over Fp318
6.2.5. Detailed Description of the Algorithm for Prime Decomposition320
6.3. Computing Galois Groups322
6.3.1. The Resolvent Method322
6.3.2. Degree 3325
6.3.3. Degree 4325
6.3.4. Degree 5328
6.3.5. Degree 6329
6.3.6. Degree 7331
6.3.7. A List of Test Polynomials333
6.4. Examples 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.5. Computing 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 7.
Introduction to Elliptic Curves
7.1. Basic 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.2. Complex 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.3. Rank 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.4. Algorithms 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.5. Algorithms 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.6. Algorithms for Elliptic Curves with Complex Multiplication414
7.6.1. Computing the Complex Values of  j(τ)414
7.6.2. Computing the Hilbert Class Polynomials415
7.6.3. Computing Weber Class Polynomials416
7.7. Exercises for Chapter 7417
 
Chapter 8.
Factoring in the Dark Ages
8.1. Factoring and Primality Testing419
8.2. Compositeness Tests421
8.3. Primality Tests423
8.3.1. The Pocklington–Lehmer N–1 Test423
8.3.2. Briefly, Other Tests424
8.4. Lehman's Method425
8.5. Pollard's ρ 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.8. The 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 9.
Modern Primality Tests
9.1. The 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 Lp455
9.1.5. The Use of Jacobi Sums457
9.1.6. Detailed Description of the Algorithm463
9.1.7. Discussion465
9.2. The Elliptic Curve Test467
9.2.1. The Goldwasser–Kilian Test467
9.2.2. Atkin's Test471
9.3. Exercises for Chapter 9475
 
Chapter 10.
Modern Factoring Methods
10.1. The Continued Fraction Method477
10.2. The Class Group Method481
10.2.1. Sketch of the Method481
10.2.2. The Schnorr–Lenstra Factoring Method482
10.3. The 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.4. The Multiple Polynomial Quadratic Sieve490
10.4.1. The Basic Quadratic Sieve Algorithm491
10.4.2. The Multiple Polynomial Quadratic Sieve492
10.4.3. Improvements to the MPQS Algorithm494
10.5. The 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
 
Appendixes.
Appendix A. Packages for Number Theory507
Appendix B. Some Useful Tables513
B.1. Table 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
 
Bibliography
527
Index540



Acknowledgements

This book grew from notes prepared for graduate courses in computational number theory given at the University of Bordeaux I. When preparing this book, it seemed natural to include both more details and more advanced subjects than could be given in such a course. By doing this, I hope that the book can serve two audiences: the mathematician who might only need the details of certain algorithms as well as the mathematician wanting to go further with algorithmic number theory.

In 1991, we started a graduate program in computational number theory in Bordeaux, and this book was also meant to provide a framework for future courses in this area.

In roughly chronological order I need to thank, Horst Zimmer, whose Springer Lecture Notes on the subject [Zim] was both a source of inspiration and of excellent references for many people at the time when it was published.

Then, certainly, thanks must go to Donald Knuth, whose (unfortunately unfinished) series on the Art of Computer Programming ([Knu1], [Knu2] and [Knu3]) contains many marvels for a mathematician. In particular, the second edition of his second volume. Parts of the contents of Chapters 1 and 3 of this book are taken with little or no modifications from Knuth's book. In the (very rare) cases where Knuth goes wrong, this is explicitly mentioned.

My thesis advisor and now colleague Jacques Martinet, has been very influential, both in developing the subject in Bordeaux and more generally in the rest of France-several of his former students are now professors. He also helped to make me aware of the beauty of the subject, since my personal inclination was more towards analytic aspects of number theory, like modular forms or L-functions. Even during the strenuous period (for him!) when he was Chairman of our department, he always took the time to listen or enthusiastically explain.

I also want to thank Hendrik Lenstra, with whom I have had the pleasure of writing a few joint papers in this area. Also Arjen Lenstra, who took the trouble of debugging and improving a big Pascal program which I wrote, which is still, in practice, one of the fastest primality proving programs. Together and separately they have contributed many extremely important algorithms, in particular LLL and its applications (see Section 2.6). My only regret is that they both are now in the U.S.A., so collaboration is more difficult.

Although he is not strictly speaking in the algorithmic field, I must also thank Don Zagier, first for his personal and mathematical friendship and also for his continuing invitations first to Maryland, then at the Max Planck Institute in Bonn, but also because he is a mathematician who takes both real pleasure and real interest in creating or using algorithmic tools in number theory. In fact, we are currently finishing a large algorithmic project, jointly with Nils Skoruppa.

Daniel Shanks, both as an author and as editor of Mathematics of Computation, has also had a great influence on the development of algorithmic algebraic number theory. I have had the pleasure of collaborating with him during my 1982 stay at the University of Maryland, and then in a few subsequent meetings.

My colleagues Christian Batut, Dominique Bernardi and Michel Olivier need to be especially thanked for the enormous amount of unrewarding work that they put in the writing of the PARI system under my supervision. This system is now completely operational (even though a few unavoidable bugs crop up from time to time), and is extremely useful for us in Bordeaux, and for the (many) people who have a copy of it elsewhere. It has been and continues to be a great pleasure to work with them.

I also thank my colleague François Dress for having collaborated with me to write our first multi-precision interpreter ISABELLE, which, although considerably less ambitious than PARI, was a useful first step.

I met Johannes Buchmann several years ago at an international meeting. Thanks to the administrative work of Jacques Martinet on the French side, we now have a bilateral agreement between Bordeaux and Saarbrücken. This has allowed several visits, and a medium term joint research plan has been informally decided upon. Special thanks are also due to Johannes Buchmann and Horst Zimmer for this. I need to thank Johannes Buchmann for the many algorithms and techniques which I have learned from him both in published work and in his preprints. A large part of this book could not have been what it is without his direct or indirect help. Of course, I take complete responsibility for the errors that may have appeared!

Although I have met Michael Pohst and Hans Zassenhaus only in meetings and did not have the opportunity to work with them directly, they have greatly influenced the development of modern methods in algorithmic number theory. They have written a book [Poh-Zas] which is a landmark in the subject. I recommend it heartily for further reading, since it goes into subjects which could not be covered in this book.

I have benefited from discussions with many other people on computational number theory, which in alphabetical order are, Oliver Atkin, Anne-Marie Bergé, Bryan Birch, Francisco Diaz y Diaz, Philippe Flajolet, Guy Henniart, Kevin McCurley, Jean-François Mestre, François Morain, Jean-Louis Nicolas, Andrew Odlyzko, Joseph Oesterlé, Johannes Graf von Schmettow, Claus-Peter Schnorr, Rene Schoof, Jean-Pierre Serre, Bob Silverman, Harold Stark, Nelson Stephens, Larry Washington. There are many others that could not be listed here. I have taken the liberty of borrowing some of their algorithms, and I hope that I will be forgiven if their names are not always mentioned.

The theoretical as well as practical developments in Computational Number Theory which have taken place in the last few years in Bordeaux would probably not have been possible without a large amount of paperwork and financial support. Hence, special thanks go to the people who made this possible, and in particular to Jean-Marc Deshouillers, François Dress and Jacques Martinet as well as the relevant local and national funding committees and agencies.

I must thank a number of persons without whose help we would have been essentially incapable of using our workstations, in particular "Achille" Braquelaire, Laurent Fallot, Patrick Henry, Viviane Sauquet-Deletage, Robert Strandh and Bernard Vauquelin.

Although I do not know anybody there, I would also like to thank the GNU project and its creator Richard Stallman, for the excellent software they produce, which is not only free (as in "freedom", but also as in "freeware"), but is generally superior to commercial products. Most of the software that we use comes from GNU.

Finally, I thank all the people, too numerous to mention, who have helped me in some way or another to improve the quality of this book, and in particular to Dominique Bernardi and Don Zagier who very carefully read drafts of this book. But special thanks go to Gary Cornell who suggested improvements to my English style and grammar in almost every line.

In addition, several people contributed directly or helped me write specific sections of the book. In alphabetical order they are D. Bernardi (algorithms on elliptic curves), J. Buchmann (Hermite normal forms and sub-exponential algorithms), J.-M. Couveignes (number field sieve), H. W. Lenstra (in several sections and exercises), C. Pomerance (factoring and primality testing), B. Vallee (LLL algorithms), P. Zimmermann (Appendix A).



Preface

With the advent of powerful computing tools and numerous advances in mathematics, computer science and cryptography, algorithmic number theory has become an important subject in its own right. Both external and internal pressures gave a powerful impetus to the development of more powerful algorithms. These in turn led to a large number of spectacular breakthroughs. To mention but a few, the LLL algorithm which has a wide range of applications, including real world applications to integer programming, primality testing and factoring algorithms, sub-exponential class group and regulator algorithms, etc...

Several books exist which treat parts of this subject. (It is essentially impossible for an author to keep up with the rapid pace of progress in all areas of this subject.) Each book emphasizes a different area, corresponding to the author's tastes and interests. The most famous, but unfortunately the oldest, is Knuth's Art of Computer Programming, especially Chapter 4.

The present book has two goals. First, to give a reasonably comprehensive introductory course in computational number theory. In particular, although we study some subjects in great detail, others are only mentioned, but with suitable pointers to the literature. Hence, we hope that this book can serve as a first course on the subject. A natural sequel would be to study more specialized subjects in the existing literature.

The prerequisites for reading this book are contained in introductory texts in number theory such as Hardy and Wright [H-W] and Borevitch and Shafarevitch [Bo-Sh]. The reader also needs some feeling or taste for algorithms and their implementation. To make the book as self-contained as possible, the main definitions are given when necessary. However, it would be more reasonable for the reader to first acquire some basic knowledge of the subject before studying the algorithmic part. On the other hand, algorithms often give natural proofs of important results, and this nicely complements the more theoretical proofs which may be given in other books.

The second goal of this course is practicality. The author's primary intentions were not only to give fundamental and interesting algorithms, but also to concentrate on practical aspects of the implementation of these algorithms. Indeed, the theory of algorithms being not only fascinating but rich, can be (somewhat arbitrarily) split up into four closely related parts. The first is the discovery of new algorithms to solve particular problems. The second is the detailed mathematical analysis of these algorithms. This is usually quite mathematical in nature, and quite often intractable, although the algorithms seem to perform rather well in practice. The third task is to study the complexity of the problem. This is where notions of fundamental importance in complexity theory such as NP-completeness come in. The last task, which some may consider the least noble of the four, is to actually implement the algorithms. But this task is of course as essential as the others for the actual resolution of the problem.

In this book we give the algorithms, the mathematical analysis and in some cases the complexity, without proofs in some cases, especially when it suffices to look at the existing literature such as Knuth's book. On the other hand, we have usually tried as carefully as we could, to give the algorithms in a ready to program form-in as optimized a form as possible. This has the drawback that some algorithms are unnecessarily clumsy (this is unavoidable if one optimizes), but has the great advantage that a casual user of these algorithms can simply take them as written and program them in his/her favorite programming language. In fact, the author himself has implemented almost all the algorithms of this book in the number theory package PARI (see Appendix A).

The approach used here as well as the style of presentation of the algorithms is similar to that of Knuth (analysis of algorithms excepted), and is also similar in spirit to the book of Press et al [PFTV] Numerical Recipes (in Fortran, Pascal or C), although the subject matter is completely different.

For the practicality criterion to be compatible with a book of reasonable size, some compromises had to be made. In particular, on the mathematical side, many proofs are not given, especially when they can easily be found in the literature. From the computer science side, essentially no complexity results are proved, although the important ones are stated.

The book is organized as follows. The first chapter gives the fundamental algorithms that are constantly used in number theory, in particular algorithms connected with powering modulo N and with the Euclidean algorithm.

Many number-theoretic problems require algorithms from linear algebra over a field or over Z. This is the subject matter of Chapter 2. The highlights of this chapter are the Hermite and Smith normal forms, and the fundamental LLL algorithm.

In Chapter 3 we explain in great detail the Berlekamp — Cantor — Zassenhaus methods used to factor polynomials over finite fields and over Q, and we also give an algorithm for finding all the complex roots of a polynomial.

Chapter 4 gives an introduction to the algorithmic techniques used in number fields, and the basic definitions and results about algebraic numbers and number fields. The highlights of these chapters are the use of the Hermite Normal Form representation of modules and ideals, an algorithm due to Diaz y Diaz and the author for finding "simple" polynomials defining a number field, and the subfield and field isomorphism problems.

Quadratic fields provide an excellent testing and training ground for the techniques of algorithmic number theory (and for algebraic number theory in general). This is because although they can easily be generated, many non-trivial problems exist, most of which are unsolved (are there infinitely many real quadratic fields with class number 1?). They are studied in great detail in Chapter 5. In particular, this chapter includes recent advances on the efficient computation in class groups of quadratic fields (Shanks's NUCOMP as modified by Atkin), and sub-exponential algorithms for computing class groups and regulators of quadratic fields (McCurley — Hamer, Buchmann).

Chapter 6 studies more advanced topics in computational algebraic number theory. We first give an efficient algorithm for computing integral bases in number fields (Zassenhaus's round 2 algorithm), and a related algorithm which allows us to compute explicitly prime decompositions in field extensions as well as valuations of elements and ideals at prime ideals. Then, for number fields of degree less than or equal to 7 we give detailed algorithms for computing the Galois group of the Galois closure. We also study in some detail certain classes of cubic fields. This chapter concludes with a general algorithm for computing class groups and units in general number fields. This is a generalization of the sub-exponential algorithms of Chapter 5, and works quite well. For other approaches, I refer to [Poh-Zas] and to a forthcoming paper of J. Buchmann. This subject is quite involved so, unlike most other situations in this book, I have not attempted to give an efficient algorithm, just one which works reasonably well in practice.

Chapters 1 to 6 may be thought of as one unit and describe many of the most interesting aspects of the theory. These chapters are suitable for a two semester graduate (or even a senior undergraduate) level course in number theory. Chapter 6, and in particular the class group and unit algorithm, can certainly be considered as a climax of the first part of this book.

A number theorist, especially in the algorithmic field, must have a minimum knowledge of elliptic curves. This is the subject of chapter 7. Excellent books exist about elliptic curves (for example [Sil] and [Sil3]), but our aim is a little different since we are primarily concerned with applications of elliptic curves. But a minimum amount of culture is also necessary, and so the flavor of this chapter is quite different from the others chapters. In the first three sections, we give the essential definitions, and we give the basic and most striking results of the theory, with no pretense to completeness and no algorithms.

The theory of elliptic curves is one of the most marvelous mathematical theories of the twentieth century, and abounds with important conjectures. They are also mentioned in these sections. The last sections of Chapter 7, give a number of useful algorithms for working on elliptic curves, with little or no proofs.

The reader is warned that, apart from the material necessary for later chapters, Chapter 7 needs a much higher mathematical background than the other chapters. It can be skipped if necessary without impairing the understanding of the subsequent chapters.

Chapter 8 (whose title is borrowed from a talk of Hendrik Lenstra) considers the techniques used for primality testing and factoring prior to the 1970's, with the exception of the continued fraction method of Brillhart — Morrison which belongs in Chapter 10.

Chapter 9 explains the theory and practice of the two modern primality testing algorithms, the Adleman — Pomerance — Rumely test as modified by H. W. Lenstra and the author, which uses Fermat's (little) theorem in cyclotomic fields, and Atkin's test which uses elliptic curves with complex multiplication.

Chapter 10 is devoted to modern factoring methods, i.e. those which run in sub-exponential time, and in particular to the Elliptic Curve Method of Lenstra, the Multiple Polynomial Quadratic Sieve of Pomerance and the Number Field Sieve of Pollard. Since many of the methods described in Chapters 9 and 10 are quite complex, it is not reasonable to give ready-to-program algorithms as in the preceding chapters, and the implementation of any one of these complex methods can form the subject of a three month student project.

In Appendix A, we describe what a serious user should know about computer packages for number theory. The reader should keep in mind that the author of this book is biased since he has written such a package himself (this package being available without cost by anonymous ftp).

Appendix B has a number of tables which we think may useful to the reader. For example, they can be used to check the correctness of the implementation of certain algorithms.

What I have tried to cover in this book is so large a subject that, necessarily, it cannot be treated in as much detail as I would have liked. For further reading, I suggest the following books.

For Chapters 1 and 3, [Knu1] and [Knu2]. This is the bible for algorithm analysis. Note that the sections on primality testing and factoring are outdated. Also, algorithms like the LLL algorithm which did not exist at the time he wrote are, obviously, not mentioned. The recent book [GCL] contains essentially all of our Chapter 3, as well as many more polynomial algorithms which we have not covered in this book such as Grobner bases computation.

For Chapters 4 and 5, [Bo-Sh], [Mar] and [Ire-Ros]. In particular, [Mar] and [Ire-Ros] contain a large number of practical exercises, which are not far from the spirit of the present book, [Ire-Ros] being more advanced.

For Chapter 6, [Poh-Zas] contains a large number of algorithms, and treats in great detail the question of computing units and class groups in general number fields. Unfortunately the presentation is sometimes obscured by quite complicated notations, and a lot of work is often needed to implement the algorithms given there.

For Chapter 7, [Sil] and [Sil3] are excellent books, and contain numerous exercises. Another good reference is [Hus], as well as [Ire-Ros] for material on zeta-functions of varieties. The algorithmic aspect of elliptic curves is beautifully treated in [Cre], which I also heartily recommend.

For Chapters 8 to 10, the best reference to date, in addition to [Knu2], is [Rie]. In addition, Riesel has several chapters on prime number theory.

Note on the exercises. The exercises have a wide range of difficulty, from extremely easy to unsolved research problems. Many are actually implementation problems, and hence not mathematical in nature. No attempt has been made to grade the level of difficulty of the exercises as in Knuth, except of course that unsolved problems are mentioned as such. The ordering follows roughly the corresponding material in the text.

Warning. Almost all of the algorithms given in this book have been programmed by the author and colleagues, in particular as a part of the Pari package. The programming has not however, always been synchronized with the writing of this book, so it may be that some algorithms are incorrect, and others may contain slight typographical errors which of course also invalidate them. Hence, the author and Springer-Verlag do not assume any responsibility for consequences which may directly or indirectly occur from the use of the algorithms given in this book. Apart from the preceding legalese, the author would appreciate corrections, improvements and so forth to the algorithms given, so that this book may improve if further editions are printed. The simplest is to send an e-mail message to

cohen@math.u-bordeaux.fr

or else to write to the author's address:

Henri Cohen
U.F.R. de Mathématiques et Informatique
Université Bordeaux I
351 Cours de la Libération
F-33405 Talence Cedex, France.

In addition, a regularly updated errata file is available by anonymous ftp from megrez.math.u-bordeaux.fr (147.210.16.17), directory pub/cohenbook. Этот файл также можно найти по адресу http://www.math.u-bordeaux.fr/~cohen/. Исправления и уточнения, которые были упомянуты в errata4.dvi на 1 марта 2003 года, уже внесены в DjVu-файлы. E.G.A.


Appendix A
Packages for Number Theory

There exist several computer packages which can profitably be used for number-theoretic computations. In this appendix, I will briefly describe the advantages and disadvantages of some of these systems.

Most general-purpose symbolic algebra packages have been written primarily for applied mathematicians, engineers and physicists, and are not always well suited for number theory. These packages roughly fall into two categories. In the first category one finds computer algebra systems developed in the 1970's, of which the main representatives are Macsyma and Reduce. Because of their maturity, these systems have been extensively tested and have probably less bugs than more recent systems. In addition they are very often mathematically more robust. In the second category, I include more recent packages developed in the 1980's of which the most common are Mathematica, by Wolfram Research, Inc., Maple, by the University of Waterloo, Canada, and more recently Axiom, developed by IBM and commercialized by NAG. These second-generation systems being more recent have more bugs and have been less tested. They are also often more prone to mathematical errors. On the other hand they have been aggressively commercialized and as a consequence have become more popular. However, the older systems have also been improved, and in particular recently Macsyma was greatly improved in terms of speed, user friendliness and efficiency and now compares very favorably to more recent packages. Mathematica has a very nice user interface, and its plotting capabilities, for example on the Macintosh, are superb. Maple is faster and often simpler to use, and has my preference. Axiom is a monster (in the same sense that ADA is a monster as a programming language). It certainly has a large potential for developing powerful applications, but I do not believe that there is the need for such power (which is usually obtained at the expense of speed) for everyday (number-theoretic) problems.

Some other packages were specially designed for small machines like Personal Computers (PC's). One of these is Derive, which is issued from μ-Math, and requires only half a megabyte of main memory. Derive even runs on some pocket computers! Another system, the Calculus Calculator (CC), is a symbolic manipulator with three-dimensional graphics and matrix operations which also runs on PC's. A third system, Numbers, is a shareware calculator for number theory that runs on PC's. It is designed to compute number theoretic functions for positive integers up to 150 decimal digits (modular arithmetic, primality testing, continued and Farey fractions, Fibonacci and Lucas numbers, encryption and decryption).

In addition to commercial packages, free software systems (which are not complete symbolic packages) also exist. One is Ubasic, written by Y. Kida, which is a math-oriented high-precision Basic for PC's (see the review in Notices of the AMS of March 1991). Its extensions to Basic allow it to handle integers and reals of several thousand digits, as well as fractions, complex numbers and polynomials in one variable. Many number-theoretic functions are included in Ubasic, including the factoring algorithm MPQS. Since the package is written in assembly language, Ubasic is very fast.

Another package, closer to a symbolic package, is Pari, written by the author and collaborators (see the review in Notices of the AMS of October 1991). This package can be used on Unix workstations, Macintosh, Amiga, PC's, etc. Its kernel is also written in assembler, so it is also very fast. Furthermore, it has been specially tailored for number-theoretic computations. In addition, it provides tools which are rarely or never found in other symbolic packages such as the direct handling of concrete mathematical objects, for example p-adic numbers, algebraic numbers and finite fields, etc ... It also gives mathematically more correct results than many packages on fundamental operations (e.g. subtraction of two real numbers which are approximately equal).

Source is included in the package so it is easy to correct, improve and expand. Essentially all of the algorithms described in the present book have been implemented in Pari, so I advise the reader to obtain a copy of it.

Apart from those general computer algebra systems, some special-purpose systems exist: GAP, Kant, Magma, Simath. The Magma system is designed to support fast computations in algebra (groups, modules, rings, polynomial rings over various kinds of coefficient domains), number theory and finite geometry. It includes general machinery for classical number theory (for example the ECM program of A. K. Lenstra), finite fields and cyclotomic fields and facilities for computing in a general algebraic number field. It will eventually include a MPQS factoring algorithm, a Jacobi sum-type primality test and a general purpose elliptic curve calculator. According to the developers, it should eventually include "just about all of the algorithms of this book". GAP (Groups, Algorithms and Programming) is specially designed for computations in group theory. It includes some facilities for doing elementary number theory, in particular to calculate with arbitrary length integers and rational numbers, cyclotomic fields and their subfields, and finite fields. It has functions for integer factorization (based on elliptic curves), for primality testing, and for some elementary functions from number theory and combinatorics. Its programming language is Maple-like. Kant (Komputational Algebraic Number Theory) is a subroutine package for algorithms from the geometry of numbers and algebraic number theory, which will be included in Magma. Simath, developed at the university of Saarbrucken, is another system for number-theoretic computations which is quite fast and has a nice user interface called simcalc.

In addition to specific packages, handling of multi-precision numbers or more general types can be easily achieved with several languages, Lisp, C and C++. For Lisp, the INRIA implementation LeLisp (which is not public domain) contains a package written in assembler to handle large numbers, and hence is very fast. The GNU Calc system is an advanced desk calculator for GNU Emacs, written in Emacs Lisp. An excellent public domain C++ compiler can be obtained from the Free Software Foundation, and its library allows to use multi-precision numbers or other types. The library is however written in C++ hence is slow, so it is strongly advised to write a library in assembler for number-theoretic uses. Another multi-precision system written in C is the desk calculator (Calc) of Hans-J. Boehm for Unix workstations. Its particularity is to handle "constructive" real numbers, that is to remember the best known approximation to a number already computed. For PC's, Timothy C. Frenz has developed an "infinite" precision calculator, also named Calc.

Finally, a few free packages exist which have been specifically written for handling multi-precision integers as part of a C library in an efficient way. In addition to Pari mentioned above, there is the Bignum package of DEC PRL (which is essentially the package used in LeLisp as mentioned above) which can be obtained by sending an e-mail message to librarian@decprl.dec.com, and the GNU multi-precision package Gmp which can be obtained by anonymous ftp from prep.ai.mit.edu, the standard place where one can ftp all the GNU software.

Conclusions

My personal advice (which is certainly not objective) is the following. If you are on an IBM-PC 286, you do not have much choice. Obtain Ubasic, Derive or the Calculus Calculator. On an IBM-PC 386 or more, Maple, Macsyma, Mathcad (see Maple below) and Pari are also available. If you are on a MacII or on a Unix workstation then, if you really need all the power of a symbolic package, buy either Maple or Mathematica, my preference going to Maple. If you want a system that is already specialized for number theoretic computations, then buy Magma. In any case, as a complement to this package, obtain Pari.

Where to obtain these packages

You can order Maple at the following address: Waterloo Maple Software, 160 Columbia St. W., Waterloo, Ontario, Canada N2L 3L3, phone: (519) 747-2373, fax: (519) 747-5284, e-mail: wmsi@daisy.waterloo.edu. Maple has been ported to many different machines and it is highly probable that it has been ported to the machine that you want. There is also a system named Mathcad that uses some parts of Maple for its symbolic manipulations; Mathcad runs under Microsoft Windows and is published by MathSoft Inc., 201 Broadway, Cambridge, Massachussets, USA, 02139. Phone: (617) 577-1017.

You can order Mathematica from Wolfram Research, Inc. at the following address: Wolfram Research, 100 Trade Center Drive, Champaign, IL 61820, phone: 800-441-Math, fax: 217-398-0747, e-mail: info@wri.com. Mathematica has also been ported to quite a number of machines, and in addition you can use a friendly "front-end" like the Macintosh II linked to a more powerful computer (including supercomputers) which will do the actual computations.

Macsyma exists in two flavors: the commercial versions (Macsyma, ALJABR, ParaMacs) are licensed from MIT, the non-commercial versions (Vaxima, Maxima, and DOE-Macsyma) officially come from the American Department of Energy (DOE). All these versions are derived from the Macsyma developed by the Mathlab Group at MIT. The commercial version runs on PC 386, Symbolics computers, VMS machines and most Unix workstations; the address to order it is: Macsyma Inc., 20 Academy Street, Suite 201, Arlington MA 02174-6436, phone: (617) 646-4550 or 1-800-MACSYMA (free from the U.S.), fax: (617) 646-3161, e-mail: info-macsyma@macsyma.com. Vaxima is available from the Energy Science and Technology Software Center (ESTSC), P.O.Box 1020, Oak Ridge, Tennessee 37831, phone: (615) 576-2606. Maxima is a Common Lisp version maintained by William Schelter (e-mail: wfs@math.utexas.edu) at Texas University. Although it is a noncommercial version, one must get a license from the Energy Science and Technology Software Center (see above) to use it. For more information, get the file README.MAXIMA by anonymous ftp on rascal.ics.utexas.edu. ParaMacs is available from Leo Harten, Paradigm Associates, Inc., 29 Putnam Avenue, Suite 6, Cambridge, MA 02139, phone: (617) 492-6079, fax: (617) 876-8186, e-mail: lph@paradigm.com. ALJABR is available from Fort Pond Research, 15 Fort Pond Road, Acton, MA 01720, phone: 508-263-9692, e-mail: aljabr@fpr.com. It runs on Macintosh, Sun and SGI computers.

There are many distributors of Reduce, depending on the machine and version of Lisp that is used. The main one is Herbert Melenk, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Heilbronner Str. 10, D 1000 Berlin 31, Germany, phone: 30-89604-195, fax: 30-89604-125, e-mail: melenk@sc.zib-berlin.de. You will get detailed informations if you send an electronic message with send info-package as subject to reduce-netlib@rand.org.

Axiom on IBM RS/6000 is distributed by NAG: contact the Numerical Algorithms Group Ltd., Wilkinson House, Jordan Hill Rd., Oxford, UK OX2 8DR, phone: (0)-865-511245, e-mail: nagttt@vax.oxford.ac.uk. A Sparc version is also available.

Derive is available from Soft Warehouse, Inc., 3615 Harding Avenue, Suite 505, Honolulu, Hawaii 96816, USA, phone: (808) 734-5801, fax: (808) 735-1105.

You can obtain Ubasic by anonymous ftp at shape.mps.ohio-state.edu or wuarchive.wustl.edu. Or you can write directly to Kida at the following address: Prof. Yuji Kida, Department of Mathematics, Rikkyo University, Nishi-Ikebukuro 3, Tokyo 171, JAPAN, e-mail: kida@rkmath.rikkyo.ac.jp.

The Calculus Calculator (CC) is developed by David Meredith, Department of Mathematics, San Francisco State University, 1600 Holloway Avenue, San Francisco, CA 94132, phone: (415) 338-2199. Version 3 (CC3) is published with a 200 page manual by Prentice Hall, phone: (201) 767-5937. Version 4 (CC4) is available by anonymous ftp from wuarchive.wustl.edu.

You can order Magma from The Secretary, Computational Algebra Group, Pure Mathematics, University of Sydney, NSW 2006, Australia, phone: (2) 692-3338, fax: (2) 692-4534, e-mail: magma@maths.su.oz.au. It runs on Sun, HP, Apollo, VAX/VMS, Convex and various IBM machines.

GAP is available free of charge through ftp from Aachen: the ordinary mail address is Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64, D-5100 Aachen, Germany. For technical questions, contact Martin Schoenert (e-mail: martin@math.rwth-aachen.de), and for more general questions, contact Prof. Joachim Neubüser (e-mail: neubueser@math.rwth-aachen.de).

There are two versions of Kant: Kant VI is written in ANSI Fortran 77, while Kant V2 is built on the Magma Platform and written in ANSI C. These two versions are available from the KANT Group: e-mail to pohst@math.tu-berlin.de or daberkow@math.tu-berlin.de. You can get the system by anonymous ftp from ftp.math.tu-berlin.de, directory /pub/algebra/Kant. Note that Kant V2 is now also part of the Magma package.

You can obtain Simath by anonymous ftp from ftp.math.uni-sb.de.

Numbers is developed by Ivo Düntsch, Moorlandstr. 59, W-4500 Osnabrück, phone: (541) 189-106, fax: (541) 969-2470, e-mail: duentsch@dosunil.bitnet. You can get the system by anonymous ftp from dione.rz.uni-osnabrueck.de.

You can obtain Gmp (as well as all software from the Free Software Foundation) by anonymous ftp on prep.ai.mit.edu.

The three multi-precision systems named Calc can all be obtained by anonymous ftp: the GNU calculator (written and maintained by Dave Gillespie, e-mail: daveg@csvax.cs.caltech.edu, 256-80 Caltech, Pasadena, CA 91125) from csvax.cs.caltech.edu, the calculator of Hans-J. Boehm from arisia.xerox.com and the calculator of Timothy C. Frenz (5361 Amalfi Drive, Clay, NY 13041) from the site wuarchive.wustl.edu.

Finally, you can obtain Pari by anonymous ftp from the sites megrez.ceremab.u-bordeaux. fr, ftp.inria.fr and math.ucla.edu.

Internet addresses and numbers for ftp
arisia.xerox.com13.1.64.94Boehm-Calc
csvax.cs.caltech.edu131.215.131.131  GNU Calc
dione.rz.uni-osnabrueck.de131.173.128.15Numbers
ftp.math.tu-berlin.de130.149.12.72Kant
ftp.math.uni-sb.de134.96.32.23Simath
math.ucla.edu128.97.4.254Pari
megrez.ceremab.u-bordeaux.fr  147.210.16.17Pari
prep.ai.mit.edu18.71.0.38Gmp
rascal.ics.utexas.edu128.83.138.20Maxima
shape.mps.ohio-state.edu128.146.110.30Ubasic
wuarchive.wustl.edu128.252.135.4Most packages

Appendix B
Some Useful Tables

In this appendix, we give five short tables which may be useful as basic data on which to work in algebraic number fields and on elliptic curves. The first two tables deal with quadratic fields and can be found in many places.

The third and fourth table give the corresponding tables for complex and totally real cubic fields respectively, and have been produced by M. Olivier using the method explained in Section 6.4.1 and the KANT package (see Appendix A).

The fifth table is a short table of elliptic curves extracted from [LN476] and [Cre].

I give here a list of references to the main tables that I am aware of. Not included are tables which have been superseded, and also papers containing only a few of the smallest number fields.

For quadratic fields see [Bue1] and [Ten-Wil].

For cubic fields see [Enn-Tur1], [Enn-Tur2], [Gras], [Ang], [Sha-Wil] and [Ten-Wil].

For quartic fields see [Ford3], [Buc-Ford] and [BFP].

For quintic fields see [Diaz] and [SPD].

For sextic fields see [Oli3], [Oli4], [Oli5] and [Oli6].

Finally, for an extensive table of elliptic curves see Cremona's book [Cre].


B.1. Table of Class Numbers of Complex Quadratic Fields

Recall that the group of units of complex quadratic fields is equal to ±1 except when the discriminant is equal to –3 or –4 in which case it is equal to the group of sixth or fourth roots of unity respectively.

The following table list triples (dh(d), H(–d)) where d is negative and congruent to 0 or 1 modulo 4, h(d) is the class number of the quadratic order of discriminant d, and H(–d) is the Hurwitz class number of discriminant d (see Definition 5.3.6). Note that h(d) = H(–d) if and only if d is a fundamental discriminant, that H(–d) has a denominator equal to 2 (resp. 3) if and only if d is of the form –4f 2 (resp. –3f 2) and otherwise is an integer.

(–3, 1, 1/3)(–4, 1, 1/2)(–7, 1, 1)(–8, 1, 1)
(–11,1,1)(–12,1,4/3)(–15,2,2)(–16,1,3/2)
(–19,1,1)(–20,2,2)(–23,3,3)(–24,2,2)
(–27,1,4/3)(–28,1,2)(–31,3,3)(–32,2,3)
·     ·     ·
  (–499, 3, 3)    (–500, 10, 12)    (–503, 21, 21)    (–504, 8, 12)  


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

In the following table of real quadratic fields K we list the following data from left to right: the discriminant d = d(K), the class number h = h(K), the regulator R = R(K), the norm of the fundamental unit and finally the fundamental unit itself given as a pair of coordinates (ab) on the canonical integral basis (1, ω) where ω = (1 + √d)/2 if d ≡ 1 (mod 4), ω = √d/2 if d ≡ 0 (mod 4).

dhRN(ε)ε
1  0.4812    –1  (0,1)
1  0.8814–1  (1,1)
12 1  1.3171  (2,1)
13 1  1.195–1  (1,1)
17 1  2.095–1  (3,2)
21 1  1.5671  (2,1)
24 1  2.2921  (5,2)
28 1  2.7691  (8,3)
29 1  1.647–1  (2,1)
33 1  3.8281  (19,8)
  37 1  2.492–1  (5,2)
·     ·     ·
492 2  5.4971  (122,11)
493 2  4.710–1  (53,5)
497 1  14.691  (1147975,107824)


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

Any number field can be defined as K = Q[α] where α is a primitive algebraic integer (see Section 10.5.2), and we will denote by A(X) the minimal monic polynomial of α. We will choose A so that the index  f  = [ZK : Z[α]] is as small as possible and with small coefficients (hence A will not always be the pseudo-canonical polynomial given by Algorithm 4.4.12). The choice of the particular polynomials A which we will give is therefore not at all canonical.

Let now K be a cubic field. Since we have chosen α primitive, there exists an integral basis of the form (1, α, β). Furthermore any cubic field has at least one real embedding hence the set of roots of unity is always equal to ±1. On the other hand complex cubic fields have unit rank equal to 1, while real cubic fields have unit rank equal to 2. Since the norm of –1 is equal to –1, there is no such thing as the sign of the norm of fundamental units.

The following is a table of the first hundred complex cubic fields. For each field K we give the following data from left to right: the discriminant d = d(K), the index  f  = [ZK : Z[α]], the polynomial A, the third element β of an integral basis (1, α, β), the class number h = h(K), the regulator R = R(K) and the fundamental unit ε expressed on the integral basis (for example (2, 3, 1) means 2 + 3α + β). Since the signature of K is equal to (1, 1), the Galois group of the Galois closure of K is always equal to the symmetric group S3.

dfAβhRε
–23 1X 3 + X 2 – 1α210.2812(0,1,1)
–31 1X 3X 2 – 1α210.3822(0,1,0)
–44 1X 3X 2X – 1α210.6094(0,1,0)
–59 1X 3 + 2X – 1α210.7910(2,0,1)
–76 1X 3 – 2X – 2α211.019 (1,1,0)
–83 1X 3X 2 + X – 2α211.041 (1,0,1)
–87 1  X 3 + X 2 + 2X – 1  α210.9348(2,1,1)
·     ·     ·
–812 1X 3X 2 – 7X – 7α213.844 (4,5,2)
–815 1X 3 – 7X – 9α215.064 (20,22,7)


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

The following is a table of the first hundred totally real cubic fields. We give the following data from left to right: the discriminant d(K), the index [ZK : Z[α]], the polynomial A(K), the third element β of an integral basis (1, α, β), the class number h(K), the regulator R(K) and a pair of fundamental units ε1 and ε2 expressed on the integral basis (1, α, β). The Galois group of the Galois closure of K is equal to S3 except for the fields whose discriminant is marked with an asterisk, which are cyclic cubic fields, i.e. with Galois group equal to C3.

dfAβhRε1ε2
49*1X 3 + X 2 – 2X – 1α210.5255(–1,1,1)(2,0,–1)
81*1X 3 – 3X – 1α210.8493(2,1,–1)(0,–1,0)
148 1X 3X 2 – 3X – 1α211.662 (0,1,0)(2,0,–1)
169*1X 3X 2 – 4X – 1α211.365 (2,2,–1)(0,–1,0)
229 1X 3 – 4X – 1α212.355 (0,1,0)(2,1,0)
257 1X 3 – 5X – 3α211.975 (4,1,–1)(5,1,–1)
316 1 X 3 + X 2 – 4X – 2 α213.913 (–3,1,1)(–5,1,1)
·     ·     ·
 3124 1X 3 – 16X – 12α2/2119.56 (–5,–1,1)(115,121,–68)
 3132 1X 3 – 18X – 20α2/2122.49 (7,2,0)(7,7,2)


B.5. Table of Elliptic Curves

In the table below we give a table of all modular elliptic curves defined over Q with conductor N less than or equal to 44 (up to isomorphism). Recall that according to the Taniyama—Weil Conjecture 7.3.8, all elliptic curves defined over Q are modular.

To every elliptic curve is attached quite a large set of invariants. We refer to [Cre] for details and a complete table. In the following table, we only give the minimal Weierstrass equation of the curve, its rank and its torsion subgroup. The rank is always equal to 0 except in the two cases N = 37 (curve A1) and N = 43 for which it is equal to 1, and in these two cases a generator of the group E(Q) is the point with coordinates (0, 0). The canonical height of this point, computed using Algorithms 7.5.6 and 7.5.7 is equal to 0.0255557041... for N = 37 and to 0.0314082535... for N = 43.

The Kodaira types and the constants cp can be found by using Tate's Algorithm 7.5.1. The coefficients ap of the L-series can be computed using Algorithm 7.4.12 or simply by adding Legendre symbols if p is small. The periods can be computed using Algorithm 7.4.7. In the limit of the present table the Tate—Shafarevitch group III is always trivial.

We follow the notations of [Cre]. We give from left to right: the conductor N of the curve E, an identifying label of the curve among those having the same conductor. This label is of the form letter-number. The letter (A or B) denotes the isogeny class, and the number is the ordinal number of the curve in its isogeny class. Curves numbered 1 are the strong Weil curves (see [Sil]). The next 5 columns contain the coefficients a1, a2, a3, a4 and a6. The last two columns contain the rank r and the torsion subgroup T of E(Q) expressed as t if T @ Z/tZ and as t1 × t2 if T @ Z/t1Z × Z/t2Z.

N a1a2a3a4a6rT
11A10–11–10–2005
11A20–11–7820  –263580  01
11A30–110005
14A10–114–606
14A20–11–36–7006
14A30–11–171–87402
14A40–11–1006
14A50–11–2731–5514602
14A60–11–111206
·     ·     ·
43A10110011
44A10103–103
44A2010–77–28901


Bibliography

Essential Introductory Books

[Bo-Sh] Z. I. Borevitch and I. R. Shafarevitch, Number Theory, Academic Press, New York, 1966.

A classic must which gives a fairly advanced introduction to algebraic number theory, with applications for example to Fermat's last theorem. Contains numerous exercises.

[GCL] K. Geddes, S. Czapor and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers, Boston, Dordrecht, London, 1992.

This book contains a very detailed description of the basic algorithms used for handling fundamental mathematical objects such as polynomials, power series, rational functions, as well as more sophisticated algorithms such as polynomial factorization, Gröbner bases computation and symbolic integration. The algorithms are those which have been implemented in the Maple system (see Appendix A). This is required reading for anyone wanting to understand the inner workings of a computer algebra system.

[H-W] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, (5th ed.), Oxford University Press, Oxford, 1979.

This is another classic must for a beginning introduction to number theory. The presentation is very clear and simple, and the book contains all basic essential material. Avoid reading parts like the "elementary" proof of the prime number theorem. Proofs based on complex function theory, while requiring deeper concepts, are much more enlightening.

[Ire-Ros] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, (2nd ed.), Graduate texts in Math. 84, Springer-Verlag, New York, 1982.

A remarkable introductory book on the more analytic and computational parts of algebraic number theory, with numerous concrete examples and exercises. This book can be read profitably jointly with the present book for a deeper understanding of several subjects such as Gauss and Jacobi sums and related identities (used in Chapter 9), quadratic and cyclotomic fields (Chapters 5 and 9), zeta functions of varieties (Chapter 7), etc ... . A must.

[Knu1] D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, (2nd ed.), Addison-Wesley, Reading, Mass., 1973.

This is the first volume of the "bible" of computer science. Although not specifically targeted to number theory, this volume introduces a large number of fundamental concepts and techniques (mathematical or otherwise) which are of constant use to anyone implementing algorithms. The style of writing is crystal clear, and I have copied the style of presentation of algorithms from Knuth. A must.

[Knu2] D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, (2nd ed.), Addison-Wesley, Reading, Mass., 1981.

This is the second volume of the "bible" of computer science. Essentially all the contents of chapter 4 of Knuth's book is basic to computational number theory, and as stated in the preface, some parts of chapters 1 and 3 of the present book have been merely adapted from Knuth. The section on factoring and primality testing is of course outdated. The book contains also a huge number of fascinating exercises, with solutions. An absolute must.

[Knu3] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass., 1973.

This is the third volume of the "bible" of computer science. The description of searching and sorting methods (in particular heapsort and quicksort) as well as hashing techniques can be used for number-theoretic applications.

One can find at the URL

http://www-cs-faculty.stanford.edu/~knuth/index.html

nearly 350 pages of corrections and additions to [Knu1], [Knu2] and [Knu3], absolutely necessary for those having the older editions of Knuth's books. This has been incorporated in a new 3 volume set which came out in 1996.

[Lang1] S. Lang, Algebra, (2nd ed.), Addison-Wesley, Reading, Mass., 1984.

This book is quite abstract in nature and in fact contains little concrete examples. On the other hand one can find the statements and proofs of most of the basic algebraic results needed in number theory.

[Mar] D. A. Marcus, Number Fields, Springer-Verlag, New York, 1977.

An excellent textbook on algebraic number theory with numerous very concrete examples, not far from the spirit of this book, although much less algorithmic in nature.

[Rie] H. Riesel, Prime Numbers and Computer Methods for Factorization, Birkhäuser, Boston, 1985.

An excellent elementary text on prime number theory and algorithms for primality testing and factoring. As in the present book the algorithms are ready to implement, and in fact implementations of many of them are given in Pascal. The subject matter of the algorithmic part overlaps in a large part with chapters 8 to 10 of this book.

[Sam] P. Samuel, Théorie algébrique des nombres, Hermann, Paris, 1971.

Another excellent textbook on algebraic number theory. Gives the basic proofs and results in a very nice and concise manner.

[Ser] J.-P. Serre, A Course in Arithmetic, Springer-Verlag, New York, 1973.

A very nice little book which contains an introduction to some basic number-theoretic objects such as Z/nZ, finite fields, quadratic forms, modular forms, etc ... . A must, although further reading is necessary in almost all cases. The original was published in French in 1970.


Other Books and Volumes

[AHU] A. Aho, J. Hopcroft and J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974.

This book discusses many issues related to basic computer algorithms and their complexity. In particular, it discusses in detail the notion of NP-complete problems, and has chapters on integer and polynomial arithmetic, on the LUP decomposition of matrices and on the Fast Fourier Transform.

[Bac-Sha] E. Bach and J. Shallit, Algorithmic Number Theory, Vol. 1: Efficient Algorithms, MIT Press, Cambridge, Mass, 1996.

Studies in detail the complexity of number-theoretic algorithms.

[Bor-Bor] J. Borwein and P. Borwein, Pi and the AGM, Canadian Math. Soc. Series, John Wiley and Sons, New York, 1987.

A marvelous book containing a wealth of formulas in the style of Ramanujan, including formulas coming from complex multiplication for computing π to great accuracy.

[Bue] D. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations, Springer-Verlag, New York, 1990.

A nice and easy to read book on the theory of binary quadratic forms, which expands on some of the subjects treated in Chapter 5.

[Cas] J. Cassels, Lectures on elliptic curves, Cambridge Univ. Press, 1991.

An excellent small introductory book to the subject of elliptic curves containing a wealth of deeper subjects not so easily accessible otherwise. The viewpoint is different from Silverman's, and hence is a highly recommended complementary reading.

[Cas-Frö] J. Cassels and A. Fröhlich, Algebraic number theory, Academic Press, London and New York, 1967.

This book has been one of the main reference books for a generation of algebraic number theorists and is still the standard book to read before more sophisticated books like Shimura's.

[Cohn] H. Cohn, A Classical Introduction to Algebraic Numbers and Class Fields, Univer-sitext, Springer-Verlag, New York, 1978.

A highly recommended concrete introduction to algebraic number theory and class field theory, with a large number of detailed examples.

[Con-Slo] J. Conway and N. Sloane, Sphere Packings, Lattices and Groups, Grundlehren der math. Wiss. 290, Springer-Verlag, New York, 1988.

The bible on lattices and sphere packings. Everything you ever wanted to know and much more, including a large number of tables. An irreplaceable tool for research in the Geometry of Numbers.

[Cox] D. Cox, Primes of the Form x2 + ny2. Fermat, Class Field Theory and Complex Multiplication, John Wiley and Sons, New York, 1989.

This is an excellent book on class field theory and complex multiplication. It is written in a very concrete manner with many examples and exercises, and I recommend it highly.

[Cre] J. Cremona, Algorithms for Modular Elliptic Curves, Cambridge Univ. Press, 1992.

An extension of [LN476] to conductors less than 1000, and much more information. Also many algorithms related to elliptic curves are listed, most of which are not given in this book. A must on the subject.

[Dah-Bjö] G. Dahlquist and A. Björk (translated by N. Anderson), Numerical Methods, Prentice Hall, Englewood Cliffs, N.J., 1974.

A basic reference book on numerical algorithms, especially for linear algebra.

[Del-Fad] B. N. Delone and D. K. Fadeev, The Theory of Irrationalities of the Third Degree, Trans. Math. Mon. 10, A.M.S., Providence, R.I., 1964.

Although quite old, this book contains a wealth of theoretical and algorithmic information on cubic fields.

[Gol-Van] G. Golub and C. Van Loan, Matrix Computations, (2nd ed.), Johns Hopkins Univ. Press, Baltimore and London, 1989.

An excellent comprehensive introduction to basic techniques of numerical analysis used in linear algebra.

[Hus] D. Husemoller, Elliptic Curves, Graduate texts in Math. 111, Springer-Verlag, New York, 1987.

Simpler than Silverman's book, this gives a good introduction to elliptic curves.

[Kap] I. Kaplansky, Commutative Rings, Allyn and Bacon, Boston, 1970.

A very nicely written little book on abstract algebra.

[Kob] N. Koblitz, Introduction to Elliptic Curves and Modular Forms, Graduate texts in Math. 97, Springer-Verlag, New York, 1984.

This nice book gives the necessary tools for obtaining the complete solution of the congruent number problem modulo a weak form of the Birch—Swinnerton-Dyer conjecture. In passing, a lot of very concrete material on elliptic curves and modular forms is covered.

[Lang2] S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, Mass., 1970.

An advanced abstract introduction to the subject.

[Lang3] S. Lang, Elliptic Functions, Addison-Wesley, Reading, Mass., 1973.

A nice introductory book on elliptic functions and elliptic curves.

[Lang4] S. Lang, Introduction to Modular Forms, Springer-Verlag, Berlin, Heidelberg, New York, 1976.

A nice introductory book on modular forms.

[LN476] B. Birch and W. Kuyk (eds.), Modular Forms in one Variable IV, LN in Math. 476, Springer-Verlag, Berlin, Heidelberg, 1975.

A fundamental book of tables and algorithms on elliptic curves, containing in particular a detailed description of all elliptic curves of conductor less than or equal to 200. A must on the subject.

[MCC] H. W. Lenstra and R. Tijdeman (eds.), Computational Methods in Number Theory, Math. Centre tracts 154/155, Math. Centrum Amsterdam, 1982.

A very nice two volume collection on computational number theory, covering many different topics.

[Nau-Qui] P. Naudin and C. Quitté, Algorithmique Algébrique, Masson, Paris, 1992.

A very nice and leisurely introduction to computational algebra (in French) with many detailed algorithms and a complete chapter devoted to the use of the Fast Fourier Transform in computer algebra.

[Ogg] A. Ogg, Modular Forms and Dirichlet Series, Benjamin, 1969.

A nice little introductory book on modular forms, containing in particular a detailed proof of Weil's Theorem 7.3.7.

[PPWZ] A. Pethö, M. Pohst, H. Williams and H. G. Zimmer (eds.), Computational Number Theory, Walter de Gruyter, 1991.

Similar to [MCC] but very up to date and more oriented towards algebraic number theory. Contains very important contributions which are referenced separately here.

[Poh] M. Pohst (ed.), Algorithmic Methods in Algebra and Number Theory, Academic Press, 1987.

A special volume of the Journal of Symbolic Computation devoted to computational number theory, and containing a number of important individual contributions which are referenced separately here.

[Poh-Zas] M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Cambridge Univ. Press, 1989.

The reference book on algorithmic algebraic number theory. Contains detailed descriptions of numerous algorithms for solving the fundamental tasks of algebraic number theory in the general number field case. The notation is sometimes heavy, and direct computer implementation of the algorithms is not always easy, but the wealth of information is considerable. A must for further reading on the subject.

[Poh5] M. Pohst, Computational Algebraic Number Theory, DMV Seminar 21, Birkhäuser, Boston, 1993.

Writeup of a course given by the author in 1990. This can be considered as an update to parts of [Poh-Zas].

[PFTV] W. Press, B. Flannery, S. Teukolsky and W. Vetterling, Numerical Recipes in C, (2nd ed.), Cambridge University Press, Cambridge, 1988.

The algorithms presented in this book are essentially unrelated to number theory, but this is a basic reference book for implementing algorithms in numerical analysis, and in particular for number theory, polynomial root finding and linear algebra over R. A must for implementing numerical analysis-related algorithms.

[Sha] H. Williams (ed.), Math. Comp. 48 (January) (1987).

A special volume of Mathematics of Computation dedicated to D. Shanks. Contains a large number of important individual contributions.

[Shi] G. Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Iwanami Shoten and Princeton Univ. Press, Princeton, 1971.

This book is one of the great classics of advanced number theory, in particular about class fields, elliptic curves and modular forms. It contains a great wealth of information, and even though it is quite old, it is still essentially up to date and still a basic reference book. Beware however that the mathematical sophistication is high. A must for people wanting to know more about class fields, complex multiplication and modular forms at a high level.

[Sil] J. Silverman, The Arithmetic of Elliptic Curves, Graduate texts in Math. 106, Springer-Verlag, New York, 1986.

This excellent book has now become the reference book on elliptic curves, and a large part is of very advanced level. It is excellently written, contains numerous exercises and is a great pleasure to study. A must for further study of elliptic curves.

[Sil3] J. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, Graduate texts in Math. 151, Springer-Verlag, New York, 1994.

The long awaited sequel to [Sil].

[Was] L. Washington, Introduction to Cyclotomic Fields, Graduate Texts in Math. 83, Springer-Verlag, New York, 1982.

An excellent advanced introduction to algebraic number theory, with many concrete examples.

[W-W] E. Whittaker and G. Watson, A Course of Modern Analysis, (4th ed.), Cambridge Univ. Press, 1927.

Still the reference book on practical use of complex analysis. The chapters on elliptic functions and theta functions are of special interest to number theorists.

[Zag] D. Zagier, The Analytic Theory of Modular Forms, in preparation.

A thorough introduction to the analytic theory of modular forms, including a number of advanced topics. Very clear exposition. A must on the subject (when it comes out).

[Zim] H. Zimmer, Computational Problems, Methods and Results in Algebraic Number Theory, LN in Math. 262, Springer-Verlag, Berlin, Heidelberg, 1972.

A very thorough list of commented bibliographic references on computational number theory prior to 1971.


Papers and other references

[Adl] L. Adleman, Factoring numbers using singular integers, Proc. 18th Annual ACM Symp. on Theory of Computing (1991), 64–71.

[Adl-Hua] L. Adleman and M. Huang, Primality testing and Abelian varieties over finite fields, LN in Math 1512, Springer-Verlag, Berlin, Heidelberg, 1992.

[APR] L. Adleman, C. Pomerance and R. Rumely, On distinguishing prime numbers from composite numbers, Ann. of Math. 117 (1983), 173–206.

[AGP] R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722.

[Ang] I. Angell, A table of complex cubic fields, Bull. London Math. Soc. 5 (1973), 37–38.

[Arn] F. Arnault, The Rabin—Miller primality test: composite numbers which pass it, Math. Comp. 64 (1995), 335–361.

[ARW] S. Arno, M. Robinson and F. Wheeler, Imaginary quadratic fields with small odd class number (to appear).

[Atk1] O. Atkin, Composition of binary quadratic forms, manuscript (1990).

[Atk2] O. Atkin, The number of points on an elliptic curve modulo a prime, manuscript (1991).

[Atk-Mor] O. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68.

[Ayo] R. Ayoub, An Introduction to the Analytic Theory of Numbers, Mathematical surveys 10, A.M.S., 1963.

[Bach] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355–380.

[Bar] E. Bareiss, Sylvester's identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565–578.

[BeMaOl] A.-M. Bergé, J. Martinet and M. Olivier, The computation of sextic fields with a quadratic subfield, Math. Comp. 54 (1990), 869–884.

[Ber] E. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735.

[Bir-SwD] B. Birch and H. P. F. Swinnerton-Dyer, Notes on elliptic curves I, J. Reine Angew. Math. 212 (1963), 7–25; II, ibid. 218 (1965), 79–108.

[BFHT] A. Borodin, R. Fagin, J. Hopcroft and M. Tompa, Decreasing the nesting depth of expressions involving square roots, J. Symb. Comp. 1 (1985), 169–188.

[Bos] W. Bosma, Primality testing using elliptic curves, Report 85–12, Math. Instituut, Univ. of Amsterdam (1985).

[Bos-Hul] W. Bosma and M.-P. van der Hulst, Primality proving with cyclotomy, thesis, Univ. of Amsterdam, 1990.

[Bra] G. Bradley, Algorithms for Hermite and Smith normal form matrices and linear Diophantine equations, Math. Comp. 25 (1971), 897–907.

[Brau] R. Brauer, On the Zeta-function of algebraic number fields I, Amer. J. Math. 69 (1947), 243–250; II, ibid. 72 (1950), 739–746.

[Bre1] R. P. Brent, Some integer factorization algorithms using elliptic curves, in Proc. 9th Australian Computer science conference (1985).

[Bre2] R. P. Brent, An improved Monte-Carlo factorization algorithm, BIT 20 (1980), 176–184.

[Bre3] R.P. Brent, The first occurence of large gaps between successive primes, Math. Comp. 27 (1973), 959–963.

[BLSTW] J. Brillhart, D.H. Lehmer, J. Selfridge, B. Tuckerman and S. Wagstaff, Factorizations of bn ± 1, b = 2, 3, 5, 6, 7, 10, 11, 12, up to high powers, Contemporary Mathematics 22, A.M.S., Providence, R.I., 1983.

[Bri-Mor] J. Brillhart and M. Morrison, A method of factoring and the factorization of F7, Math. Comp. 29 (1975), 183–205.

[BLS] J. Brillhart, D. H. Lehmer and J. Selfridge, New primality criteria and factorizations of 2m ± 1, Math. Comp. 29 (1975), 620–647.

[BCS] S. Brlek, P. Castéran and R. Strandh, On addition schemes, TAPSOFT 1991, LN in Comp. Sci. 494, 1991, pp. 379–393.

[deBru] N. G. de Bruijn, The asymptotic behavior of a function occurring in the theory of primes, J. Indian Math. Soc. (N. S.) 15 (1951), 25–32.

[Buc1] J. Buchmann, A generalization of Voronoi's unit algorithm I and II, J. Number Theory 20 (1985), 177–209.

[Buc2] J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm, J. Number Theory 26 (1987), 8–30.

[Buc3] J. Buchmann, On the period length of the generalized Lagrange algorithm, J. Number Theory ,B>26 (1987), 31–37.

[Buc4] J. Buchmann, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper, Habilitationsschrift, University of Düsseldorf, 1988.

[Buc-Dül] J. Buchmann and S. Düllmann, A probabilistic class group and regulator algorithm and its implementation, in [PPWZ], 1991, pp. 53–72.

[Buc-Ford] J. Buchmann and D. Ford, On the computation of totally real quartic fields of small discriminant, Math. Comp. 52 (1989), 161–174.

[BFP] J. Buchmann, D. Ford and M. Pohst, Enumeration of quartic fields of small discriminant, Math. Comp. 61 (1993), 873–879.

[Buc-Len] J. Buchmann and H. W. Lenstra, Computing maximal orders and factoring over Zp, preprint.

[Buc-Len2] J. Buchmann and H. W. Lenstra, Approximating rings of integers in number fields, J. Th. des Nombres Bordeaux (Série 2) 6 (1994), 221–260.

[Buc-Pet] J. Buchmann and A. Petho, On the computation of independent units in number fields by Dirichlet's method, Math. Comp. 52 (1989), 149–159.

[Buc-Poh-Sch] J. Buchmann, M. Pohst and J. Graf von Schmettow, On the computation of unit groups and class groups of totally real quartic fields, Math. Comp. 53 (1989), 387–397.

[Buc-Thi-Wil] J. Buchmann, C. Thiel and H. Williams, Short representation of quadratic integers, Computational Algebra and Number Theory, Mathematics and its Applications, Kluwer, Dordrecht, 1995, pp. 159–185.

[Buc-Wil] J. Buchmann and H. Williams, On principal ideal testing in algebraic number fields, J. Symb. Comp. 4 (1987), 11–19.

[Bue1] D. Buell, The expectation of success using a Monte-Carlo factoring method — some statistics on quadratic class numbers, Math. Comp. 43 (1984), 313–327.

[BGZ] J. Buhler, B. Gross and D. Zagier, On the conjecture of Birch and Swinnerton-Dyer for an elliptic curve of rank 3, Math. Comp. 44 (1985), 473–481.

[BLP] J. Buhler, H. W. Lenstra and C. Pomerance, Factoring integers with the number field sieve, [Len-Len2], 1993, pp. 50–94.

[But-McKay] G. Butler and J. McKay, The transitive groups of degree up to eleven, Comm. in Algebra 11 (1983), 863–911.

[CEP] E. R. Canfield, P. Erdos and C. Pomerance, On a problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 1–28.

[Can-Zas] D. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587–592.

[Car] H. Carayol, Sur les représentations l-adiques associées aux formes modulaires de Hilbert, Ann. Sci. E.N.S. 19 (1986), 409–468.

[Chu] D. and G. Chudnovsky, Sequences of numbers generated by addition informal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), 187–237.

[Coa-Wil] J. Coates and A. Wiles, On the conjecture of Birch and Swinnerton-Dyer, Invent. Math. 39 (1977), 223–251.

[Coh1] H. Cohen, Variations sur un thème de Siegel et Hecke, Acta Arith. 30 (1976), 63–93.

[Coh2] H. Cohen, Formes modulaires à une et deux variables, Thesis, Univ. de Bordeaux I, 1976.

[Coh3] P. Cohen, On the coefficients of the transformation polynomials for the elliptic modular function, Math. Proc. Cambridge Phil. Soc. 95 (1984), 389–402.

[Coh-Diaz] H. Cohen and F. Diaz y Diaz, A polynomial reduction algorithm, Sem. Th. Nombres Bordeaux (Série 2) 3 (1991), 351–360.

[CohDiOl] H. Cohen, F. Diaz y Diaz and M. Olivier, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel, Séminaire de Théorie des Nombres Paris 1990–91 (1993), 35–46.

[Coh-Len1] H. Cohen and H. W. Lenstra, Heuristics on class groups of number fields, Number Theory, Noordwijkerhout 1983, LN in Math. 1068, Springer-Verlag, 1984, pp. 33–62.

[Coh-Len2] H. Cohen and H. W. Lenstra, Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297–330.

[Coh-Len3] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103–121.

[Coh-Mar1] H. Cohen and J. Martinet, Class groups of number fields: numerical heuristics, Math. Comp. 48 (1987), 123–137.

[Coh-Mar2] H. Cohen and J. Martinet, Etude heuristique des groupes de classes des corps de nombres, J. Reine Angew. Math. 404 (1990), 39–76.

[Coh-Mar3] H. Cohen and J. Martinet, Heuristics on class groups: some good primes are not too good, Math. Comp. 63 (1994), 329–334.

[Col] G. Collins, The calculation of multivariate polynomial resultants, JACM 18 (1971), 515–532.

[Cop1] D. Coppersmith, Solving linear equations over GF(2), RC 16997, IBM Research, T. J. Watson research center (1991).

[Cop2] D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333–350.

[Del] P. Deligne, La conjecture de Weil I, Publ. Math. IHES 43 (1974), 273–307.

[Deu] Deuring, Die Klassenkörper der komplexen Multiplication, Enzyklopädie der mathematischen Wissenschaften 12 (Book 10, Part II), Teubner, Stuttgart, 1958.

[Diaz] F. Diaz y Diaz, A table of totally real quintic number fields, Math. Comp. 56 (1991), 801–808 and S1–S12.

[DKT] P. Domich, R. Kannan and L. Trotter, Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Research 12 (1987), 50–59.

[Duk] W. Duke, Hyperbolic distribution functions and half-integral weight Maass forms, Invent. Math. 92 (1988), 73–90.

[Duv] D. Duval, Diverses questions relatives au calculformel avec des nombres algébriques, Thesis, Univ. of Grenoble, 1987.

[Eic1] Y. Eichenlaub, Méthodes de calcul des groupes de Galois sur  Q, Memoire DEA, 1990.

[Eic2] M. Eichler, On the class number of imaginary quadratic fields and the sums of divisors of natural numbers, J. Indian Math. Soc. 19 (1955), 153–180.

[Enn-Turl] V. Ennola and R. Turunen, On totally real cubic fields, Math. Comp. 44 (1985), 495–518.

[Enn-Tur2] V. Ennola and R. Turunen, On cyclic cubic fields, Math. Comp. 45 (1985), 585–589.

[Fal] G. Faltings, Endlichkeitssätze fur abelsche Varietäten über Zahlkörpern, Invent. Math. 73 (1983), 349–366.

[Fer1] S. Fermigier, Un exemple de courbe elliptique définie sur Q de rang ≥ 19, C. R. Acad. Sci. Paris 315 (1992), 719–722.

[Fer2] S. Fermigier, in preparation.

[Fin-Poh] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), 463–471.

[Ford1] D. Ford, On the computation of the maximal order in a Dedekind domain, Thesis, Ohio State Univ., 1978.

[Ford2] D. Ford, The construction of maximal orders over a Dedekind domain, J. Symb. Comp. 4 (1987), 69–75.

[Ford3] D. Ford, Enumeration of totally complex quartic fields of small discriminant, in [PPWZ], 1991, pp. 129–138.

[Fri] E. Friedman, Analytic formulas for the regulator of a number field, Invent. Math. 98 (1989), 599–622.

[Gir] K. Girstmair, On invariant polynomials and their application in field theory, Math. Comp. 48 (1987), 781–797.

[Gol] D. Goldfeld, The class number of quadratic fields and the conjectures of Birch and Swinnerton-Dyer, Ann. Sc. Norm. Super. Pisa 3 (1976), 623–663.

[Gol-Kil] S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. 18th Annual ACM Symp. on Theory of Computing (1986), 316–329.

[Gras] M.-N. Gras, Méthodes et algorithmes pour le calcul numérique du nombre de classes et des unites des extensions cubiques cycliques de Q, J. Reine Angew. Math. 277 (1975), 89–116.

[Gro-Zag1] B. Gross and D. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191–220.

[Gro-Zag2] B. Gross and D. Zagier, Heegner points and derivatives of L-series, Invent. Math. 84 (1986), 225–320.

[GKZ] B. Gross, W. Kohnen and D. Zagier, Heegner points and derivatives of L-series II, Math. Ann. 278 (1987), 497–562.

[Haf-McCur1] J. Hafner and K. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal American Math. Soc. 2 (1989), 837–850.

[Haf-McCur2] J. Hafner and K. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 1068–1083.

[Has] H. Hasse, Arithmetische Theorie der kubischen Zahlkörper auf klassenkörpertheoretischer Grundlage, Math. Zeit. 31 (1930), 565–582; Math. Abhandlungen, Walter de Gruyter, 1975, pp. 423–440.

[HJLS] J. Hastad, B. Just, J. C. Lagarias and C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, Siam J. Comput. 18 (1989), 859–881.

[Her] O. Hermann, Über die Berechnung der Fouriercoefficienten der Funktion j(τ), J. Reine Angew. Math. 274/275 (1975), 187–195.

[Hül] A. Hülpke, in preparation.

[Hun] J. Hunter, The minimum discriminants of quintic fields, Proc. Glasgow Math. Ass. 3 (1957), 57–67.

[Kal-Yui] E. Kaltofen and N. Yui, Explicit construction of the Hilbert class fields of imaginary quadratic fields by integer lattice reduction, New York Number Theory Seminar 1989–1990, Springer-Verlag, 1991, pp. 150–202.

[Kam] S. Kamienny, Torsion points on elliptic curves and q-coefficients of modular forms, Invent. Math. 109 (1992), 221–229.

[Kan-Bac] R. Kannan and A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal form of an integer matrix, Siam J. Comput. 8 (1979), 499–507.

[Kol1] V. A. Kolyvagin, Finiteness of E(Q) and Ш(E/Q) for a subclass of Weil curves, Izv. Akad. Nauk SSSR 52 (1988), 522–540.

[Kol2] V. A. Kolyvagin, Euler systems, Progress in Math. 87, Grothendieck Festschrift II, Birkhäuser, Boston, 1991, pp. 435–483.

[LaM] B. LaMacchia, Basis reduction algorithms and subset sum problems, Thesis, MIT Artificial Intelligence Lab., 1991.

[LaM-Odl] B. LaMacchia and A. M. Odlyzko, Solving large sparse linear systems over finite fields, Advances in cryptology: Crypto 90, A. Menezes and S. Vanstone (eds.), LN in Comp. Sci. 537, Springer-Verlag, 1991, pp. 109–133.

[Las] M. Laska, An algorithm for finding a minimal Weierstrass equation for an elliptic curve, Math. Comp. 38 (1982), 257–260.

[Leh1] S. Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646.

[Leh2] D. H. Lehmer, On Fermat's quotient, base two, Math. Comp. 36 (1981), 289–290.

[Len1] H. W. Lenstra, On the computation of regulators and class numbers of quadratic fields, Lond. Math. Soc. Lect. Note Ser. 56 (1982), 123–150.

[Len2] H. W. Lenstra, Divisors in residue classes, Math. Comp. 42 (1984), 331–334.

[Len3] H. W. Lenstra, Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649–673.

[Len4] A. K. Lenstra, Polynomial time algorithms for the factorization of polynomials, dissertation, Univ. of Amsterdam, 1984.

[Len-Len1] A. K. Lenstra and H. W. Lenstra, Algorithms in number theory, Handbook of theoretical computer science, J. Van Leeuwen, A. Mayer, M. Nivat, M. Patterson and D. Perrin (eds.), Elsevier, Amsterdam, 1990, pp. 673–715.

[Len-Len2] A. K. Lenstra and H. W. Lenstra (eds.), The development of the number field sieve, LN in Math. 1554, Springer-Verlag, Berlin, Heidelberg, New York, 1993.

[LLL] A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515–534.

[LLMP] A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard, The Number Field Sieve, in [Len-Len2], 1993, pp. 11–42.

[Llo-Quer] P. Llorente and J. Quer, On the 3-Sylow subgroup of the class group of quadratic fields, Math. Comp. 50 (1988), 321–333.

[Mah] K. Mahler, On a class of non-linear functional equations connected with modular functions, J. Austral. Math. Soc. 22A (1976), 65–118.

[Mart] J. Martinet, Méthodes géométriques dans la recherche des petits discriminants, Progress in Math. 59, 1985, pp. 147–179.

[Maz] B. Mazur, Rational isogenies of prime degree, Invent. Math. 44 (1978), 129–162.

[McCur] K. McCurley, Cryptographic key distribution and computation in class groups, Proceedings of NATO ASI Number Theory and applications, Kluwer Academic Publishers, 1989, pp. 459–479.

[Mer] L. Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124 (1996), 437–449.

[Mes1] J.-F. Mestre, Construction d'une courbe elliptique de rang ≥ 12, C. R. Acad. Sci. Paris 295 (1982), 643–644.

[Mes2] J.-F. Mestre, Formules explicites et minorations de conducteurs de variétés algébriques, Compositio Math. 58 (1986), 209–232.

[Mes3] J.-F. Mestre, Courbes elliptiques de rang ≥ 12 sur Q(t), C. R. Acad. Sci. Paris (1991), 171–174.

[Mes4] J.-F. Mestre, Un exemple de courbe elliptique sur Q de rang ≥ 15, C. R. Acad. Sci. Paris 314 (1992), 453–455.

[Mes5] J.-F. Mestre, private communication.

[Mig] M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157.

[Mil] G. Miller, Riemann's hypothesis and tests for primality, J. Comput. and System Sc. 13 (1976), 300–317.

[Mol-Wil] R. Mollin and H. Williams, Computation of the class number of a real quadratic field, Utilitas Math. 41 (1992), 259–308.

[Mon-Nar] J. Montes and E. Nart, On a theorem of Ore, Journal of Algebra 146 (1992), 318–339.

[Mon1] P. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), 519–521.

[Mon2] P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243–264.

[Mor1] F. Morain, Résolution d'équations de petit degré modulo de grands nombres premiers, Rapport de recherche INRIA 1085 (1989).

[Mor2] F. Morain, Courbes elliptiques et tests de primalité, Thesis, Univ. Claude Bernard, Lyon, 1990.

[Mor-Nic] F. Morain and J.-L. Nicolas, On Comacchia's algorithm for solving the Diophantine equation u2 + dv2 = m (to appear).

[Nag] K. Nagao, An example of elliptic curve over Q(T) with rank ≥ 13, Proc. Japan Acad. 70 (1994), 152–153.

[Nag-Kou] K. Nagao and T. Kouya, An example of elliptic curve over Q with rank ≥ 21, Proc. Japan Acad. 70 (1994), 104–105.

[Nic] J.-L. Nicolas, Etre ou ne pas être un carré, Dopo le Parole, (a collection of not always serious papers for A. K. Lenstra's doctorate), Amsterdam, 1984.

[Odl] A. M. Odlyzko, Bounds for discriminants and related estimates for class numbers, regulators and zeros of zeta-functions: a survey of recent results, Sém. Th. des Nombres Bordeaux (Série 2) 2 (1991), 117–141.

[Oes] J. Oesterle, Nombre de classes des corps quadratiques imaginaires, in Séminaire Bourbaki 1983–84, Astérisque 121–122, Soc. Math, de France, 1985, pp. 309–323.

[Oli1] M. Olivier, Corps sextiques primitifs, Ann. Institut Fourier 40 (1990), 757–767.

[Oli2] M. Olivier, The computation of sextic fields with a cubic subfield and no quadratic subfield, Math. Comp. 58 (1992), 419–432.

[Oli3] M. Olivier, Tables de corps sextiques contenant un sous-corps quadratique (I), Sém. Th. des Nombres Bordeaux (Série 2) 1 (1989), 205–250.

[Oli4] M. Olivier, Corps sextiques contenant un corps quadratique (II), Sém. Th. des Nombres Bordeaux (Série 2) 2 (1990), 49–102.

[Oli5] M. Olivier, Corps sextiques contenant un corps cubique (III), Sém. Th. des Nombres Bordeaux (Série 2) 3 (1991), 201–245.

[Oli6] M. Olivier, Corps sextiques primitifs (IV), Sém. Th. des Nombres Bordeaux (Série 2) 3 (1991), 381–404.

[Ore] Ö. Ore, Newtonsche Polygone in der Theorie der algebraischen Körper, Math. Ann. 99 (1928), 84–117.

[Poh1] M. Pohst, On the computation of number fields of small discriminants including the minimum discriminants of sixth degree fields, J. Number Theory 14 (1982), 99–117.

[Poh2] M. Pohst, A modification of the LLL-algorithm, J. Symb. Comp. 4 (1987), 123–128.

[Poh3] M. Pohst, On computing isomorphisms of equation orders, Math. Comp. 48 (1987), 309–314.

[Poh4] M. Pohst, A note on index divisors, in [PPWZ], 1991, pp. 173–182.

[Poh-Wei-Zas] M. Pohst, P. Weiler and H. Zassenhaus, On effective computation of fundamental units I and II, Math. Comp. 38 (1982), 275–329.

[Poh-Zasl] M. Pohst and H. Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraische Zahlkörper, J. Reine Angew. Math. 361 (1985), 50–72.

[Pol1] J. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Phil.Soc. 76 (1974), 521–528.

[Pol2] J. Pollard, A Monte-Carlo method for factorization, BIT 15 (1975), 331–334.

[Pom] C. Pomerance, Analysis and comparison of some integer factoring algorithms, in [MCC], 1983, pp. 89–139.

[Quer] J. Quer, Corps quadratiques de 3-rang 6 et courbes elliptiques de rang 12, C. R. Acad. Sci. Paris 305 (1987), 1215–1218.

[Rab] M. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128–138.

[Rib] K. Ribet, On modular representations of Gal(Q/Q) arising from modular forms, Invent. Math. 100 (1990), 431–476.

[Rub] K. Rubin, Tate-Shafarevitch groups and L-functions of elliptic curves with complex multiplication, Invent. Math. 93 (1987), 527–560.

[von Schm1] J. Graf v. Schmettow, Beiträge zur Klassengruppenberechnung, Dissertation, Univ. Düsseldorf, 1991.

[von Schm2] J. Graf v. Schmettow, KANT — a tool for computations in algebraic number fields, in [PPWZ], 1991, pp. 321–330.

[Schn] C.P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), 47–62.

[Schn-Euch] C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Proc. of the FCT 1991, LN in Comp. Sci. 529, Springer-Verlag, Berlin, Heidelberg, 1991, pp. 68–85.

[Schn-Len] C. P. Schnorr and H. W Lenstra, A Monte-Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), 289–312.

[Schön] A. Schönhage, Probabilistic computation of integer polynomial GCD, J. Algorithms 9 (1988), 365–371.

[Scho] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 43 (1985), 483–494.

[Scho2] R. Schoof, Counting points of elliptic curves over finite fields, J. Th. des Nombres Bordeaux (Série 2) 7 (1995), 219–254.

[SPD] A. Schwarz, M. Pohst and F. Diaz y Diaz, A table of quintic number fields, Math. Comp. 63 (1994), 361–376.

[Sel-Wun] J. Selfridge and M. Wunderlich, An efficient algorithm for testing large numbers for primality, Proc. Fourth Manitoba Conf. Numer. Math. (1974), 109–120.

[Ser1] J.-P. Serre, Sur les représentations modulaires de degré 2 de Gal(Q/Q), Duke Math. J. 54 (1987), 179–230.

[Sey1] M. Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminants, Math. Comp. 48 (1987), 757–780.

[Sey2] M. Seysen, Simultaneous reduction of a lattice basis and its reciprocal basis, Combinatorica 13 (1993), 363–376.

[Sha1] D. Shanks, Class number, a theory of factorization, and genera, Proc. Symp. in Pure Maths. 20, A.M.S., Providence, R.I., 1969, pp. 415–440.

[Sha2] D. Shanks, On Gauss and composition I and II, Number theory and applications, R. Mollin (ed.), Kluwer Academic Publishers, 1989, pp. 163–204.

[Sha3] D. Shanks, The infrastructure of a real quadratic field and its applications, Proc. 1972 Number theory conference, Boulder (1972), 217–224.

[Sha4] D. Shanks, Incredible identities, Fibon. Quart. 12 (1974).

[Sha-Wil] D. Shanks and H. Williams, A note on class number one in pure cubic fields, Math. Comp. 33 (1979), 1317–1320.

[Shi1] G. Shimura, On the zeta-function of an Abelian variety with complex multiplication, Ann. of Math. 94 (1971), 504–533.

[Shi2] G. Shimura, On elliptic curves with complex multiplication as factors of the Jacobians of modular function fields, Nagoya Math. J. 43 (1971), 199–208.

[Sie] C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arith. 1 (1935), 83–86.

[Sil1] R. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329–340.

[Sil2] J. Silverman, Computing heights on elliptic curves, Math. Comp. 51 (1988), 339–358.

[Soi] L. Soicher, The computation of Galois groups, Thesis, Concordia Univ., Montreal, 1981.

[Soi-McKay] L. Soicher and J. McKay, Computing Galois groups over the rationals, J. Number Theory 20 (1985), 273–281.

[Sol-Str] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 84–85; erratum ibid. 7 (1978), p. 118.

[Star] H. Stark, Class numbers of complex quadratic fields, in Modular Functions of one variable I, LN in Math. 320, Springer-Verlag, Berlin, Heidelberg, 1973, pp. 153–174.

[Stau] R. P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981–996.

[Tay-Wil] R. Taylor and A. Wiles, Ring-theoretic properties of certain Hecke algebras, Ann. of Math. 141 (1995), 553–572.

[Ten-Wil] M. Tennenhouse and H. Williams, A note on class number one in certain real quadratic and pure cubic fields, Math. Comp. 46 (1986), 333–336.

[Tra] B. Trager, Algebraic factoring and rational function integration, Proceedings of SYMSAC '76 (1976), 219–226.

[Val] B. Vallee, Une approche géométrique des algorithmes de réduction en petite dimension, Thesis, Univ. of Caen, 1986.

[Wag] C. Wagner, Class number 5, 6 and 7, Math. Comp. 65 (1996), 785–800.

[de Weg] B. de Weger, Algorithms for Diophantine equations, Dissertation, Centrum voor Wiskunde en Informatica, Amsterdam, 1988.

[Well] A. Weil, Number of solutions of equations in finite fields, Bull. A.M.S. 55 (1949), 497–508.

[Wie] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Information Theory 32 (1986), 54–62.

[Wiles] A. Wiles, Modular elliptic curves and Fermat's last theorem, Ann. of Math. 141 (1995), 443–551.

[Wil-Jud] H. Williams and J. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), 157–172 and 867–886.

[Wil-Zar] H. Williams and C. Zarnke, Some algorithms for solving a cubic congruence modulo p, Utilitas Math. 6 (1974), 285–306.

[Zag1] D. Zagier, On the values at negative integers of the zeta-function of a real quadratic field, Ens. Math. 22 (1976), 55–95.

[Zag2] D. Zagier, Modular forms whose Fourier coefficients involve zeta-functions of quadratic fields, Modular functions of one variable VI, LN in Math. 627, Springer-Verlag, Berlin, Heidelberg, New-York, 1977, pp. 105–169.

[Zag3] D. Zagier, Large integral points on elliptic curves, Math. Comp. 48 (1987), 425–436.

[Zim1] R. Zimmert, Ideale kleiner Norm in Idealklassen und eine Regulatorabschätzung, Invent. Math. 62 (1981), 367–380.

[Zip] R. Zippel, Simplification of expressions involving radicals, J. Symb. Comp. 1 (1985), 189–210.

Index
A B C D E F G H I J K L
M N O P Q R S T U V W Z

A

Abelian group, 66

addition chain, 11

addition theorem, 370

additive degeneracy, 373

adeles, 188

adjoint matrix, 54

Adleman, L., 445, 471, 501

affine subspace, 486

algebraic integer, 153

algebraic number, 153

algorithm, 1

ambiguous cycle, 270, 434

ambiguous form, 255, 433, 434

Antwerp IV, 367

approximation theorem, 192

Archimedean valuations, 187

Artinian rings, 303

Atkin, O., 32, 247, 252, 445, 471, 481

Axiom, 2, 507


B

baby step giant step, 240

Bach, E., 34, 254

bad reduction, 373

Bareiss, E., 52

Berge, A.-M., 175, 329

Berlekamp, E., 130

Bernardi, D., 305, 382, 394

Bignum, 2, 509

binary quadratic form, 225

Birch and Swinnerton-Dyer conjecture, 393

Birch, B., 392

birthday paradox, 480

bit operations, 1

Bosma, W., 466

Brauer-Siegel theorem, 216

Brent, R., 420, 427, 429, 441

Buchmann, J., 288, 303, 315, 352

Buhler, J., 501


C

Canfield, E., 481

canonical height, 411

canonical height pairing, 411

Cantor, D., 127

Carayol, H, 390

Carmichael numbers, 421

Cart an decomposition, 107

Cartan, E., 107

ceiling, 7

CFRAC, 477

character, 448

characteristic polynomial, 53, 162

Chinese remainder theorem, 19

Cholesky decomposition, 104

Chudnovsky, D. and G., 490

Cl(K), 208

class group, 207, 228

class number, 208

codifferent, 205

coefficient explosion, 5, 112, 114

Cohen, H., 168, 254, 288, 296, 352, 445

Collins, G., 118

column echelon form, 59

column vector, 7

comatrix, 54

compact representation of units, 279, 285

complementary error function, 238

completely split prime, 197

complex multiplication, 381

compositeness test, 419

composition, 243

conductor, 224

conductor-discriminant formula, 168

congruent number, 376

conjugate vector representation, 161

conjugates, 154

content, 116

continued fraction, 21, 265, 271, 426, 478

coordinate recurrence method, 254

Coppersmith, D., 480, 504

coprime elements, 116

coprime ideals, 182

Couveignes, J.-M., 405

Cremona, J., 394, 417

cycle of reduced forms, 262

cyclotomic field, 446


D

Davenport, H., 462

de Bruijn, N., 481

de Weger, B., 93

Dedekind domain, 185

Dedekind zeta function, 214

Dedekind's eta-function, 416

Dedekind, R., 305

deep insertion, 91

degenerate elliptic curve, 373

degree of a prime ideal, 197

Deligne, P., 387

denominator of a module, 74

Derive, 2, 507

determinant, 52

determinant of a lattice, 80

Diaz y Diaz, F., 168, 254, 288, 313, 352, 363

different, 205

Dirichlet character, 448

Dirichlet, P., 211

discriminant of a number field, 166

— of a polynomial, 119

— of a quadratic number, 384

— of an n-element set, 165

distance function, 279

distinct degree factorization, 126

divisibility (in a ring), 114

division polynomials, 405

double large prime variation, 494

doubly periodic function, 368

dual isogeny, 380

Duke, W, 298

Düllmann, S., 252, 254

Dwork, B., 388


E

early abort strategy, 259, 480

ECM, 487

Eichler, M., 236

Eisenstein polynomial, 315

elementary divisor, 76

elementary operations, 48

elimination, 48

Elkies, N., 405, 471

elliptic curve over K, 369

elliptic function, 368

elliptic integral, 367, 397

elliptic logarithm, 398

enlarging procedure, 304

equivalence of quadratic forms, 225

Erdos, P., 481

Euchner, M., 91

Euclid's algorithm, 12

Euclidean domain, 114

Euler product, 250

expected running time, 2

exponential time, 2


F

factor base, 260, 478

fast multiplication methods, 3

Fermat number, 424, 495

Fermat's last theorem, 151, 208, 392, 459

Fermat's little theorem, 421, 439, 450

Fermigier, S., 394

field membership problem, 179

Fincke, U., 105

floor, 7

Floyd, R., 427

FLT, 151, 208

fractional ideal, 183

Frobenius homomorphism, 309

functional equation for elliptic curves, 390

— — for number fields, 215

— — for quadratic fields, 238, 266, 267

— — sign of, 391

fundamental discriminant, 224

fundamental domain, 368

fundamental units, 210


G

Γ0(N), 390

Galois closure, 157

Galois group, 157, 322

GAP, 508

Gauss sum, 448

Gauss's lemma, 116

Gauss, K.F., 52

Gaussian elimination, 48

Gaussian pivoting, 48

Gaussian reduction, 23

GCD, 7, 115

Generalized Riemann Hypothesis, 34

genus field, 474

Germain, S., 151

Gmp, 2, 509

Goldfeld, D., 216, 234

Goldwasser, S., 445

Gram matrix, 80

Gram-Schmidt orthogonalization, 82

greatest common divisor, 7, 12, 115

GRH, 34

Gross, B., 216, 234, 385, 394

group ring, 446


H

h(K), 208

H(N), 234

H, 378

Hadamard's inequality, 51, 82

Hafner, J., 69, 70, 77, 252

hashing, 299

Hasse, H., 373, 462

Hasse-Weil L-function, 389

height, 411

Hensel's lemma, 137

Hermite normal form, 67

— — — of a Z-module, 67

— — — of a matrix, 67

Hermite's constant, 334

Hermite, C., 198

Hessenberg form, 55

Hilbert class field, 384, 416

Hilbert class polynomial, 415

HNF, 67

HNF-basis, 189

Huang, M. D., 445, 471

Hurwitz class number, 234


I

I(K), 208

ideal, 182

— class, 208

— equivalence, 207

— intersection, 207, 219

— inversion, 204

— product, 190

— representation, 188, 190

— two-element representation, 192

— valuation, 201

idele class group, 209

ideles, 188

image of a matrix, 58

index, 167

inert prime, 197

inessential discriminantal divisor, 199, 364

infinite prime, 198

infrastructure method, 279

integral basis, 166

integral domain, 114

integral ideal, 183

integral kernel, 74, 98

integrally closed, 185

intelligent Gaussian elimination, 480

intelligent Hermite reduction, 254

inverse image, 60

irreducible element, 114

irreducible polynomial, 124

isogeny, 379

isomorphism problem, 179

Iwasawa decomposition, 83


J

j(r), 378

j(E), 377

Jacobi sum, 448

Jacobi symbol, 28


K

Kant, 508

Karatsuba, A., 3

kernel of a matrix, 57

Kilian, J., 445

Knuth, D., 298

Kodaira type, 407

Kolyvagin, V., 394

Kouya, T., 394

Kraitchik, M., 478

Kronecker symbol, 28

Kronecker, L., 211


L

(P), 109

L-function, 266, 388, 389

L-series, 237

L(x), 254

LaMacchia, B., 89, 254

large prime variation, 258, 480

Laska, M., 409

lattice, 23, 80

— determinant of, 80

Legendre symbol, 27

— — generalized, 219

Legendre, A., 478

Lehman, S., 425

Lehmer, D. H., 13, 423, 443, 478

Lenstra, A. K., 84, 141, 494, 495

Lenstra, H. W., 84, 141, 184, 201, 296, 298, 303, 315, 320, 419, 442, 445, 466, 481, 484, 503

Leopoldt's conjecture, 216

lg, 7

Lisp, 2

LLL algorithm, 87

— integral, 94

LLL-reduced basis, 85

logarithmic embedding, 210

Louboutin, S., 301

Lovasz, L., 84, 141

Lucas, E., 443

Lucas-Lehmer test, 443

LUP form of a matrix, 50


M

Macsyma, 2, 507

Magma, 2, 508

Manasse, M., 494, 495

Manin's constant, 392

Manin, Yu., 392

Maple, 2, 507

Martinet, J., 217, 329

Mathematica, 2, 507

matrix representation, 160

maximal ideal, 184

maximal order, 186, 303

Mazur, B., 375

McCurley, K., 69, 70, 77, 252, 288

Mersenne number, 424, 443, 495

Mestre, J.-F., 394, 418

Mignotte, M., 134

Miller, G., 421

minimal polynomial, 153

Minkowski, H., 198

MLLL algorithm, 96

mod, 7

modular equation, 386

modular forms, 234, 390

modular functions, 379

modular invariant, 377

modular multiplication, 4

module, 188

— denominator, 188

modules product of, 189

Montgomery, P., 5, 429, 489, 492

Morain, F., 445, 471, 474

Mordell, L., 375

MPQS, 490

— self-initializing, 494

multi-precision, 2


N

Nagao, K., 394

narrow class group, 228

Neumann, W., 102

Newton polygon, 313

Newton's formulas, 163

Newton's method, 38, 45

NFS, 495

non-split multiplicative degeneracy, 373

norm of a fractional ideal, 187

— of an element, 162

— of an ideal, 182

normal closure, 157

NP-complete, 103

NUCOMP, 247

NUDUPL, 247

number field, 154

— — primitive, 335


O

Odlyzko, A., 254, 465

Oesterle, J., 295

Olivier, M., 171, 175, 254, 288, 313, 329, 333, 352, 513

order, 181

order of a group element, 24

orthogonal basis, 82

orthogonal matrix, 81


P

Ã(z), 368

p-adic factorisation, 363

p-adic regulator, 300

p-adic valuation, 186

Pari, 2, 508

partial quotients, 22

period lattice, 368, 398

permutation matrix, 50

PID, 183

pivot, 48, 65

place finite, 187

— infinite, 187

— of a number field, 187

p-maximal, 303

Pohst, M., 96, 304

Pollard, J., 426, 439, 495

Polya-Vinogradov inequality, 301, 476

polynomial time, 2

Pomerance, C., 445, 465, 481, 490, 501

powering algorithms, 8, 42, 466

Powers, R., 478

powersmooth number, 439

p-radical, 303

primality certificate, 470

prime element, 114

prime form, 252

prime ideal, 184

prime ideal theorem, 215

prime number theorem, 215

primitive algebraic integer, 274

primitive algebraic number, 497

primitive element, 155

primitive element problem, 181

primitive ideal, 225

primitive part, 116

primitive polynomial, 116

primitive quadratic form, 225

primitive root, 24

principal ideal, 183, 287

principal ideal domain, 114, 183

principal minors, 53

probabilistic algorithm, 2

product of ideals, 182

projective geometry over Z/NZ, 485

pseudo-division, 112

pseudo-prime, 422

Q

Q, 153

q, 378

QS, 490

quadratic form, 79, 225

— positive definite, 80

quadratic reciprocity law, 27

Quer, J., 297


R

2k-representation, 10

Rabin, M., 421

ramification index, 197

ramified prime, 197

rank, 66

rank of an elliptic curve, 375

Reduce, 2, 507

reduced basis, 84

reduced ideal, 300

reduced quadratic form, 231, 262

reduction of quadratic forms, 243

regular primes, 209

regular representation, 160

regulator, 211

— elliptic, 411

relative extensions, 329

residual degree, 197

resolvent polynomial, 323

resultant, 119

Ribet, K., 392

roots of unity, 209

row vector, 7

Rubin, K., 394

Rumely, R., 445


S

Schönhage, A., 3, 150

Schnorr, C., 91, 481

Schoof, R., 32, 405, 469

separable extension, 166

Serre, J.-R, 392

Shanks, D., 32, 241, 247, 251, 279, 288, 433, 434

Shimura, G., 392

side exit, 65

signature, 155

Silverman, J., 367

Simath, 508

singular number, 501

size of a polynomial, 168

small prime variation, 494

Smith normal form, 67, 75

smooth number, 439

SNF, 67, 75

Solovay, R., 421

SPAR, 481

sparse matrix, 254, 480

sparse representation, 109

special subset, 486

split multiplicative degeneracy, 373

splitting, 419

square form, 434

square root in Z, 38

— — modulo p, 31

standard fundamental domain, 231

standard representation, 159

Stark, H., 382

Stickelberger, L., 167, 198

Strassen, V., 3, 421

strong pseudo-prime, 422

Sturm, J., 155

sub-exponential algorithm, 2

sub-resultant algorithm, 118, 122

subfield problem, 174

supersingular, 382

supplement, 61

Swinnerton-Dyer, H., 392

Sylvester's matrix, 120

symmetric function, 162


T

Taniyama, T., 391

Taniyama—Weil conjecture, 391

Tate, J., 407

Tate-Shafarevitch group, 393

Taylor, R., 392

titanic numbers, 471

torsion subgroup, 66, 375

totally complex, 155

totally real, 155

trace, 162

transitive, 323

trial division, 419

triple Jacobi sum, 460

Tschirnhausen transformation, 324

two element representation, 193


U

Ubasic, 2, 508

UFD, 114

Unique factorization domain, 114

unit, 114, 209

unramified prime, 197

upper half-plane, 378


V

vp(I), 186

Vallée, B., 84

valuation, 201

van der Hulst, P., 466


W

Weber class polynomial, 417

Weber functions, 474

Weierstrass equation, 370

— minimal, 370, 406

Weil conjectures, 387

Weil curve, 392

Weil, A., 375, 387, 391

Wiedemann, D., 254

Wieferich congruence, 459

Wiles, A., 392

Williams, H., 279, 285

Winter, D., 445

Wolstenholme's theorem, 476


Z

Z-module, 66

Zagier, D., 216, 234, 236, 385, 394

Zassenhaus H., 127, 304

zeta function of a number field, 214

— — of a variety, 388

ZK, 154

ZQ, 153



Hosted by uCoz