Западные традиции книгопечатания, в отличие от русских, выносят оглавление и предисловие в отдельный блок с отдельной нумерацией римскими цифрами. Поэтому при склейке |
Acknowledgements | ||
Preface | ||
Chapter 1. Fundamental Number-Theoretic Algorithms | ||
1.1. | Introduction | 1 |
1.1.1. Algorithms | 1 | |
1.1.2. Multi-precision | 2 | |
1.1.3. Base Fields and Rings | 5 | |
1.1.4. Notations | 6 | |
1.2. | The Powering Algorithms | 8 |
1.3. | Euclid's Algorithms | 12 |
1.3.1. Euclid's and Lehmer's Algorithms | 12 | |
1.3.2. Euclid's Extended Algorithms | 16 | |
1.3.3. The Chinese Remainder Theorem | 19 | |
1.3.4. Continued Fraction Expansions of Real Numbers | 21 | |
1.4. | The Legendre Symbol | 24 |
1.4.1. The Groups (Z/nZ)* | 24 | |
1.4.2. The Legendre–Jacobi–Kronecker Symbol | 27 | |
1.5. | Computing Square Roots Modulo p | 31 |
1.5.1. The Algorithm of Tonelli and Shanks | 32 | |
1.5.2. The Algorithm of Cornacchia | 34 | |
1.6. | Solving Polynomial Equations Modulo p | 36 |
1.7. | Power Detection | 38 |
1.7.1. Integer Square Roots | 38 | |
1.7.2. Square Detection | 39 | |
1.7.3. Prime Power Detection | 41 | |
1.8. | Exercises for Chapter 1 | 42 |
Chapter 2. Algorithms for Linear Algebra and Lattices | ||
2.1. | Introduction | 46 |
2.2. | Linear Algebra Algorithms on Square Matrices | 47 |
2.2.1. Generalities on Linear Algebra Algorithms | 47 | |
2.2.2. Gaussian Elimination and Solving Linear Systems | 48 | |
2.2.3. Computing Determinants | 50 | |
2.2.4. Computing the Characteristic Polynomial | 53 | |
2.3. | Linear Algebra on General Matrices | 57 |
2.3.1. Kernel and Image | 57 | |
2.3.2. Inverse Image and Supplement | 60 | |
2.3.3. Operations on Subspaces | 62 | |
2.3.4. Remarks on Modules | 64 | |
2.4. | Z-Modules and the Hermite and Smith Normal Forms | 66 |
2.4.1. Introduction to Z-Modules | 66 | |
2.4.2. The Hermite Normal Form | 67 | |
2.4.3. Applications of the Hermite Normal Form | 73 | |
2.4.4. The Smith Normal Form and Applications | 75 | |
2.5. | Generalities on Lattices | 79 |
2.5.1. Lattices and Quadratic Forms | 79 | |
2.5.2. The Gram–Schmidt Orthogonalization Procedure | 82 | |
2.6. | Lattice Reduction Algorithms | 84 |
2.6.1. The LLL Algorithm | 84 | |
2.6.2. The LLL Algorithm with Deep Insertions | 90 | |
2.6.3. The Integral LLL Algorithm | 92 | |
2.6.4. LLL Algorithms for Linearly Dependent Vectors | 95 | |
2.7. | Applications of the LLL Algorithm | 97 |
2.7.1. Computing the Integer Kernel and Image of a Matrix | 97 | |
2.7.2. Linear and Algebraic Dependence Using LLL | 100 | |
2.7.3. Finding Small Vectors in Lattices | 103 | |
2.8. | Exercises for Chapter 2 | 106 |
Chapter 3. Algorithms on Polynomials | ||
3.1. | Basic Algorithms | 109 |
3.1.1. Representation of Polynomials | 109 | |
3.1.2. Multiplication of Polynomials | 110 | |
3.1.3. Division of Polynomials | 111 | |
3.2. | Euclid's Algorithms for Polynomials | 113 |
3.2.1. Polynomials over a Field | 113 | |
3.2.2. Unique Factorization Domains (UFD's) | 114 | |
3.2.3. Polynomials over Unique Factorization Domains | 116 | |
3.2.4. Euclid's Algorithm for Polynomials over a UFD | 117 | |
3.3. | The Sub-Resultant Algorithm | 118 |
3.3.1. Description of the Algorithm | 118 | |
3.3.2. Resultants and Discriminants | 119 | |
3.3.3. Resultants over a Non-Exact Domain | 123 | |
3.4. | Factorization of Polynomials Modulo p | 124 |
3.4.1. General Strategy | 124 | |
3.4.2. Squarefree Factorization | 125 | |
3.4.3. Distinct Degree Factorization | 126 | |
3.4.4. Final Splitting | 127 | |
3.5. | Factorization of Polynomials over Z or Q | 133 |
3.5.1. Bounds on Polynomial Factors | 134 | |
3.5.2. A First Approach to Factoring over Z | 135 | |
3.5.3. Factorization Modulo p^{e}: Hensel's Lemma | 137 | |
3.5.4. Factorization of Polynomials over Z | 139 | |
3.5.5. Discussion | 141 | |
3.6. | Additional Polynomial Algorithms | 142 |
3.6.1. Modular Methods for Computing GCD's | 142 | |
3.6.2. Factorization of Polynomials over a Number Field | 143 | |
3.6.3. A Root Finding Algorithm over Z | 146 | |
3.7. | Exercises for Chapter 3 | 148 |
Chapter 4. Algorithms for Algebraic Number Theory I | ||
4.1. | Algebraic Numbers and Number Fields | 153 |
4.1.1. Basic Definitions and Properties of Algebraic Numbers | 153 | |
4.1.2. Number Fields | 154 | |
4.2. | Representation and Operations on Algebraic Numbers | 158 |
4.2.1. Algebraic Numbers as Roots of their Minimal Polynomial | 158 | |
4.2.2. The Standard Representation of an Algebraic Number | 159 | |
4.2.3. The Matrix (or Regular) Representation of an Algebraic Number | 160 | |
4.2.4. The Conjugate Vector Representation of an Algebraic Number | 161 | |
4.3. | Trace, Norm and Characteristic Polynomial | 162 |
4.4. | Discriminants, Integral Bases and Polynomial Reduction | 165 |
4.4.1. Discriminants and Integral Bases | 165 | |
4.4.2. The Polynomial Reduction Algorithm | 168 | |
4.5. | The Subfield Problem and Applications | 174 |
4.5.1. The Subfield Problem Using the LLL Algorithm | 174 | |
4.5.2. The Subfield Problem Using Linear Algebra over C | 175 | |
4.5.3. The Subfield Problem Using Algebraic Algorithms | 177 | |
4.5.4. Applications of the Solutions to the Subfield Problem | 179 | |
4.6. | Orders and Ideals | 181 |
4.6.1. Basic Definitions | 181 | |
4.6.2. Ideals of Z_{K} | 186 | |
4.7. | Representation of Modules and Ideals | 188 |
4.7.1. Modules and the Hermite Normal Form | 188 | |
4.7.2. Representation of Ideals | 190 | |
4.8. | Decomposition of Prime Numbers I | 196 |
4.8.1. Definitions and Main Results | 196 | |
4.8.2. A Simple Algorithm for the Decomposition of Primes | 199 | |
4.8.3. Computing Valuations | 201 | |
4.8.4. Ideal Inversion and the Different | 204 | |
4.9. | Units and Ideal Classes | 207 |
4.9.1. The Class Group | 207 | |
4.9.2. Units and the Regulator | 209 | |
4.9.3. Conclusion: the Main Computational Tasks of Algebraic Number Theory | 217 | |
4.10. | Exercises for Chapter 4 | 217 |
Chapter 5. Algorithms for Quadratic Fields | ||
5.1. | Discriminant, Integral Basis and Decomposition of Primes | 223 |
5.2. | Ideals and Quadratic Forms | 225 |
5.3. | Class Numbers of Imaginary Quadratic Fields | 231 |
5.3.1. Computing Class Numbers Using Reduced Forms | 231 | |
5.3.2. Computing Class Numbers Using Modular Forms | 234 | |
5.3.3. Computing Class Numbers Using Analytic Formulas | 237 | |
5.4. | Class Groups of Imaginary Quadratic Fields | 240 |
5.4.1. Shanks's Baby Step Giant Step Method | 240 | |
5.4.2. Reduction and Composition of Quadratic Forms | 243 | |
5.4.3. Class Groups Using Shanks's Method | 250 | |
5.5. | McCurley's Sub-exponential Algorithm | 252 |
5.5.1. Outline of the Algorithm | 252 | |
5.5.2. Detailed Description of the Algorithm | 255 | |
5.5.3. Atkin's Variant | 260 | |
5.6. | Class Groups of Real Quadratic Fields | 262 |
5.6.1. Computing Class Numbers Using Reduced Forms | 262 | |
5.6.2. Computing Class Numbers Using Analytic Formulas | 266 | |
5.6.3. A Heuristic Method of Shanks | 268 | |
5.7. | Computation of the Fundamental Unit and of the Regulator | 269 |
5.7.1. Description of the Algorithms | 269 | |
5.7.2. Analysis of the Continued Fraction Algorithm | 271 | |
5.7.3. Computation of the Regulator | 278 | |
5.8. | The Infrastructure Method of Shanks | 279 |
5.8.1. The Distance Function | 279 | |
5.8.2. Description of the Algorithm | 283 | |
5.8.3. Compact Representation of the Fundamental Unit | 285 | |
5.8.4. Other Application and Generalization of the Distance Function | 287 | |
5.9. | Buchmann's Sub-exponential Algorithm | 288 |
5.9.1. Outline of the Algorithm | 289 | |
5.9.2. Detailed Description of Buchmann's Sub-exponential Algorithm | 291 | |
5.10. | The Cohen–Lenstra Heuristics | 295 |
5.10.1. Results and Heuristics for Imaginary Quadratic Fields | 295 | |
5.10.2. Results and Heuristics for Real Quadratic Fields | 297 | |
5.11. | Exercises for Chapter 5 | 298 |
Chapter 6. Algorithms for Algebraic Number Theory II | ||
6.1. | Computing the Maximal Order | 303 |
6.1.1. The Pohst–Zassenhaus Theorem | 303 | |
6.1.2. The Dedekind Criterion | 305 | |
6.1.3. Outline of the Round 2 Algorithm | 308 | |
6.1.4. Detailed Description of the Round 2 Algorithm | 311 | |
6.2. | Decomposition of Prime Numbers II | 312 |
6.2.1. Newton Polygons | 313 | |
6.2.2. Theoretical Description of the Buchmann–Lenstra Method | 315 | |
6.2.3. Multiplying and Dividing Ideals Modulo p | 317 | |
6.2.4. Splitting of Separable Algebras over F_{p} | 318 | |
6.2.5. Detailed Description of the Algorithm for Prime Decomposition | 320 | |
6.3. | Computing Galois Groups | 322 |
6.3.1. The Resolvent Method | 322 | |
6.3.2. Degree 3 | 325 | |
6.3.3. Degree 4 | 325 | |
6.3.4. Degree 5 | 328 | |
6.3.5. Degree 6 | 329 | |
6.3.6. Degree 7 | 331 | |
6.3.7. A List of Test Polynomials | 333 | |
6.4. | Examples of Families of Number Fields | 334 |
6.4.1. Making Tables of Number Fields | 334 | |
6.4.2. Cyclic Cubic Fields | 336 | |
6.4.3. Pure Cubic Fields | 343 | |
6.4.4. Decomposition of Primes in Pure Cubic Fields | 347 | |
6.4.5. General Cubic Fields | 351 | |
6.5. | Computing the Class Group, Regulator and Fundamental Units | 352 |
6.5.1. Ideal Reduction | 352 | |
6.5.2. Computing the Relation Matrix | 354 | |
6.5.3. Computing the Regulator and a System of Fundamental Units | 357 | |
6.5.4. The General Class Group and Unit Algorithm | 358 | |
6.5.5. The Principal Ideal Problem | 360 | |
6.6. | Exercises for Chapter 6 | 362 |
Chapter 7. Introduction to Elliptic Curves | ||
7.1. | Basic Definitions | 367 |
7.1.1. Introduction | 367 | |
7.1.2. Elliptic Integrals and Elliptic Functions | 367 | |
7.1.3. Elliptic Curves over a Field | 369 | |
7.1.4. Points on Elliptic Curves | 372 | |
7.2. | Complex Multiplication and Class Numbers | 376 |
7.2.1. Maps Between Complex Elliptic Curves | 377 | |
7.2.2. Isogenies | 379 | |
7.2.3. Complex Multiplication | 381 | |
7.2.4. Complex Multiplication and Hilbert Class Fields | 384 | |
7.2.5. Modular Equations | 385 | |
7.3. | Rank and L-functions | 386 |
7.3.1. The Zeta Function of a Variety | 387 | |
7.3.2. L-functions of Elliptic Curves | 388 | |
7.3.3. The Taniyama–Weil Conjecture | 390 | |
7.3.4. The Birch and Swinnerton–Dyer Conjecture | 392 | |
7.4. | Algorithms for Elliptic Curves | 394 |
7.4.1. Algorithms for Elliptic Curves over C | 394 | |
7.4.2. Algorithm for Reducing a General Cubic | 399 | |
7.4.3. Algorithms for Elliptic Curves over F_{p} | 403 | |
7.5. | Algorithms for Elliptic Curves over Q | 406 |
7.5.1. Tate's algorithm | 406 | |
7.5.2. Computing rational points | 410 | |
7.5.3. Algorithms for computing the L-function | 413 | |
7.6. | Algorithms for Elliptic Curves with Complex Multiplication | 414 |
7.6.1. Computing the Complex Values of j(τ) | 414 | |
7.6.2. Computing the Hilbert Class Polynomials | 415 | |
7.6.3. Computing Weber Class Polynomials | 416 | |
7.7. | Exercises for Chapter 7 | 417 |
Chapter 8. Factoring in the Dark Ages | ||
8.1. | Factoring and Primality Testing | 419 |
8.2. | Compositeness Tests | 421 |
8.3. | Primality Tests | 423 |
8.3.1. The Pocklington–Lehmer | 423 | |
8.3.2. Briefly, Other Tests | 424 | |
8.4. | Lehman's Method | 425 |
8.5. | Pollard's ρ Method | 426 |
8.5.1. Outline of the Method | 426 | |
8.5.2. Methods for Detecting Periodicity | 427 | |
8.5.3. Brent's Modified Algorithm | 429 | |
8.5.4. Analysis of the Algorithm | 430 | |
8.6. | Shanks's Class Group Method | 433 |
8.7. | Shanks's SQUFOF | 434 |
8.8. | The p–1-method | 438 |
8.8.1. The First Stage | 439 | |
8.8.2. The Second Stage | 440 | |
8.8.3. Other Algorithms of the Same Type | 441 | |
8.9. | Exercises for Chapter 8 | 442 |
Chapter 9. Modern Primality Tests | ||
9.1. | The Jacobi Sum Test | 446 |
9.1.1. Group Rings of Cyclotomic Extensions | 446 | |
9.1.2. Characters, Gauss Sums and Jacobi Sums | 448 | |
9.1.3. The Basic Test | 450 | |
9.1.4. Checking Condition L_{p} | 455 | |
9.1.5. The Use of Jacobi Sums | 457 | |
9.1.6. Detailed Description of the Algorithm | 463 | |
9.1.7. Discussion | 465 | |
9.2. | The Elliptic Curve Test | 467 |
9.2.1. The Goldwasser–Kilian Test | 467 | |
9.2.2. Atkin's Test | 471 | |
9.3. | Exercises for Chapter 9 | 475 |
Chapter 10. Modern Factoring Methods | ||
10.1. | The Continued Fraction Method | 477 |
10.2. | The Class Group Method | 481 |
10.2.1. Sketch of the Method | 481 | |
10.2.2. The Schnorr–Lenstra Factoring Method | 482 | |
10.3. | The Elliptic Curve Method | 484 |
10.3.1. Sketch of the Method | 484 | |
10.3.2. Elliptic Curves Modulo N | 485 | |
10.3.3. The ECM Factoring Method of Lenstra | 487 | |
10.3.4. Practical Considerations | 489 | |
10.4. | The Multiple Polynomial Quadratic Sieve | 490 |
10.4.1. The Basic Quadratic Sieve Algorithm | 491 | |
10.4.2. The Multiple Polynomial Quadratic Sieve | 492 | |
10.4.3. Improvements to the MPQS Algorithm | 494 | |
10.5. | The Number Field Sieve | 495 |
10.5.1. Introduction | 495 | |
10.5.2. Description of the Special NFS when | 496 | |
10.5.3. Description of the Special NFS when | 500 | |
10.5.4. Description of the General NFS | 501 | |
10.5.5. Miscellaneous Improvements to the Number Field Sieve | 503 | |
10.6. | Exercises for Chapter 10 | 504 |
Appendixes. | ||
Appendix A. Packages for Number Theory | 507 | |
Appendix B. Some Useful Tables | 513 | |
B.1. Table of Class Numbers of Complex Quadratic Fields | 513 | |
B.2. Table of Class Numbers and Units of Real Quadratic Fields | 515 | |
B.3. Table of Class Numbers and Units of Complex Cubic Fields | 519 | |
B.4. Table of Class Numbers and Units of Totally Real Cubic Fields | 521 | |
B.5. Table of Elliptic Curves | 524 | |
Bibliography | 527 | |
Index | 540 |
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
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
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
I have benefited from discussions with many other people on computational number theory, which in alphabetical order are,
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
I must thank a number of persons without whose help we would have been essentially incapable of using our workstations, in particular
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
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
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
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
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
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
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
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
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
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
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
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
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
Chapter 9 explains the theory and practice of the two modern primality testing algorithms, the
Chapter 10 is devoted to modern factoring methods, i.e. those which run in
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
For Chapter 6,
For Chapter 7, [Sil] and [Sil3] are excellent books, and contain numerous exercises. Another good reference is [Hus], as well as
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
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
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
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
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
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
Conclusions
My personal advice (which is certainly not objective) is the following. If you are on an
Where to obtain these packages
You can order Maple at the following address: Waterloo Maple Software, 160
You can order Mathematica from Wolfram Research, Inc. at the following address: Wolfram Research, 100 Trade Center Drive, Champaign, IL 61820, phone:
Macsyma exists in two flavors: the commercial versions (Macsyma, ALJABR, ParaMacs) are licensed from MIT, the non-commercial versions (Vaxima, Maxima, and
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:
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:
Derive is available from Soft Warehouse, Inc., 3615 Harding Avenue, Suite 505, Honolulu, Hawaii 96816, USA, phone:
You can obtain Ubasic by anonymous ftp at
The Calculus Calculator (CC) is developed by David Meredith, Department of Mathematics, San Francisco State University, 1600 Holloway Avenue, San Francisco, CA 94132, phone:
You can order Magma from The Secretary, Computational Algebra Group, Pure Mathematics, University of Sydney, NSW 2006, Australia, phone:
GAP is available free of charge through ftp from Aachen: the ordinary mail address is Lehrstuhl D für Mathematik, RWTH Aachen, Templergraben 64,
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
You can obtain Simath by anonymous ftp from
Numbers is developed by Ivo Düntsch, Moorlandstr. 59,
You can obtain Gmp (as well as all software from the Free Software Foundation) by anonymous ftp on
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:
Finally, you can obtain Pari by anonymous ftp from the sites
Internet addresses and numbers for ftp | ||
arisia.xerox.com | 13.1.64.94 | Boehm-Calc |
csvax.cs.caltech.edu | 131.215.131.131 | GNU Calc |
dione.rz.uni-osnabrueck.de | 131.173.128.15 | Numbers |
ftp.math.tu-berlin.de | 130.149.12.72 | Kant |
ftp.math.uni-sb.de | 134.96.32.23 | Simath |
math.ucla.edu | 128.97.4.254 | Pari |
megrez.ceremab.u-bordeaux.fr | 147.210.16.17 | Pari |
prep.ai.mit.edu | 18.71.0.38 | Gmp |
rascal.ics.utexas.edu | 128.83.138.20 | Maxima |
shape.mps.ohio-state.edu | 128.146.110.30 | Ubasic |
wuarchive.wustl.edu | 128.252.135.4 | Most packages |
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
The fifth table is a short table of elliptic curves extracted from [LN476]
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
For cubic fields see
For quartic fields see [Ford3],
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
Recall that the group of units of complex quadratic fields is equal to
The following table list triples
(–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) |
In the following table of real quadratic fields K we list the following data from left to right: the discriminant
d | h | R | N(ε) | ε |
5 | 1 | 0.4812 | –1 | (0,1) |
8 | 1 | 0.8814 | –1 | (1,1) |
12 | 1 | 1.317 | 1 | (2,1) |
13 | 1 | 1.195 | –1 | (1,1) |
17 | 1 | 2.095 | –1 | (3,2) |
21 | 1 | 1.567 | 1 | (2,1) |
24 | 1 | 2.292 | 1 | (5,2) |
28 | 1 | 2.769 | 1 | (8,3) |
29 | 1 | 1.647 | –1 | (2,1) |
33 | 1 | 3.828 | 1 | (19,8) |
37 | 1 | 2.492 | –1 | (5,2) |
· · · | ||||
492 | 2 | 5.497 | 1 | (122,11) |
493 | 2 | 4.710 | –1 | (53,5) |
497 | 1 | 14.69 | 1 | (1147975,107824) |
Any number field can be defined as
Let now K be a cubic field. Since we have chosen α primitive, there exists an integral basis of the form
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 | f | A | β | h | R | ε |
–23 | 1 | X^{ 3} + X^{ 2} – 1 | α^{2} | 1 | 0.2812 | (0,1,1) |
–31 | 1 | X^{ 3} – X^{ 2} – 1 | α^{2} | 1 | 0.3822 | (0,1,0) |
–44 | 1 | X^{ 3} – X^{ 2} – X – 1 | α^{2} | 1 | 0.6094 | (0,1,0) |
–59 | 1 | X^{ 3} + 2X – 1 | α^{2} | 1 | 0.7910 | (2,0,1) |
–76 | 1 | X^{ 3} – 2X – 2 | α^{2} | 1 | 1.019 | (1,1,0) |
–83 | 1 | X^{ 3} – X^{ 2} + X – 2 | α^{2} | 1 | 1.041 | (1,0,1) |
–87 | 1 | X^{ 3} + X^{ 2} + 2X – 1 | α^{2} | 1 | 0.9348 | (2,1,1) |
· · · | ||||||
–812 | 1 | X^{ 3} – X^{ 2} – 7X – 7 | α^{2} | 1 | 3.844 | (4,5,2) |
–815 | 1 | X^{ 3} – 7X – 9 | α^{2} | 1 | 5.064 | (20,22,7) |
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 | f | A | β | h | R | ε_{1} | ε_{2} |
49* | 1 | X^{ 3} + X^{ 2} – 2X – 1 | α^{2} | 1 | 0.5255 | (–1,1,1) | (2,0,–1) |
81* | 1 | X^{ 3} – 3X – 1 | α^{2} | 1 | 0.8493 | (2,1,–1) | (0,–1,0) |
148 | 1 | X^{ 3} – X^{ 2} – 3X – 1 | α^{2} | 1 | 1.662 | (0,1,0) | (2,0,–1) |
169* | 1 | X^{ 3} – X^{ 2} – 4X – 1 | α^{2} | 1 | 1.365 | (2,2,–1) | (0,–1,0) |
229 | 1 | X^{ 3} – 4X – 1 | α^{2} | 1 | 2.355 | (0,1,0) | (2,1,0) |
257 | 1 | X^{ 3} – 5X – 3 | α^{2} | 1 | 1.975 | (4,1,–1) | (5,1,–1) |
316 | 1 | X^{ 3} + X^{ 2} – 4X – 2 | α^{2} | 1 | 3.913 | (–3,1,1) | (–5,1,1) |
· · · | |||||||
3124 | 1 | X^{ 3} – 16X – 12 | α^{2}/2 | 1 | 19.56 | (–5,–1,1) | (115,121,–68) |
3132 | 1 | X^{ 3} – 18X – 20 | α^{2}/2 | 1 | 22.49 | (7,2,0) | (7,7,2) |
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
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
The Kodaira types and the constants c_{p} can be found by using Tate's Algorithm 7.5.1. The coefficients a_{p} of the
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
N | a_{1} | a_{2} | a_{3} | a_{4} | a_{6} | r | T | |
11 | A1 | 0 | –1 | 1 | –10 | –20 | 0 | 5 |
11 | A2 | 0 | –1 | 1 | –7820 | –263580 | 0 | 1 |
11 | A3 | 0 | –1 | 1 | 0 | 0 | 0 | 5 |
14 | A1 | 0 | –1 | 1 | 4 | –6 | 0 | 6 |
14 | A2 | 0 | –1 | 1 | –36 | –70 | 0 | 6 |
14 | A3 | 0 | –1 | 1 | –171 | –874 | 0 | 2 |
14 | A4 | 0 | –1 | 1 | –1 | 0 | 0 | 6 |
14 | A5 | 0 | –1 | 1 | –2731 | –55146 | 0 | 2 |
14 | A6 | 0 | –1 | 1 | –11 | 12 | 0 | 6 |
· · · | ||||||||
43 | A1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
44 | A1 | 0 | 1 | 0 | 3 | –1 | 0 | 3 |
44 | A2 | 0 | 1 | 0 | –77 | –289 | 0 | 1 |
[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),
[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
[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
[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
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—
[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
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
[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.
[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
[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
[Bri-Mor] J. Brillhart and M. Morrison, A method of factoring and the factorization of F_{7}, Math. Comp. 29 (1975), 183–205.
[BLS] J. Brillhart, D. H. Lehmer and J. Selfridge, New primality criteria and factorizations of
[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 Z_{p}, 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
[BLP] J. Buhler, H. W. Lenstra and C. Pomerance, Factoring integers with the number field sieve,
[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
[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
[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
[Cop2] D. Coppersmith, Solving homogeneous linear equations over
[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
[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
[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
[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
[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
[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
[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
[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
[Mes4] J.-F. Mestre, Un exemple de courbe elliptique sur Q de rang
[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
[Nag] K. Nagao, An example of elliptic curve over
[Nag-Kou] K. Nagao and T. Kouya, An example of elliptic curve over Q with rank
[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
[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
[Rab] M. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128–138.
[Rib] K. Ribet, On modular representations of
[Rub] K. Rubin, Tate-Shafarevitch groups and
[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
[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
[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
[Zag2] D. Zagier, Modular forms whose Fourier coefficients involve
[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.
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 |
2^{k}-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 |
v_{p}(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 Z_{K}, 154 Z_{Q}, 153 |