Западные традиции книгопечатания, в отличие от русских, выносят оглавление и предисловие в отдельный блок с отдельной нумерацией римскими цифрами. Поэтому при склейке
Fundamental Number-Theoretic Algorithms
|1.1.3. Base Fields and Rings||5|
|1.2.||The Powering Algorithms||8|
|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 LegendreJacobiKronecker 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.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|
Algorithms for Linear Algebra and Lattices
|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 GramSchmidt 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|
Algorithms on Polynomials
|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 pe: Hensel's Lemma||137|
|3.5.4. Factorization of Polynomials over Z||139|
|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|
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 ZK||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|
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 CohenLenstra 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|
Algorithms for Algebraic Number Theory II
|6.1.||Computing the Maximal Order||303|
|6.1.1. The PohstZassenhaus 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 BuchmannLenstra Method||315|
|6.2.3. Multiplying and Dividing Ideals Modulo p||317|
|6.2.4. Splitting of Separable Algebras over Fp||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|
Introduction to Elliptic Curves
|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.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 TaniyamaWeil Conjecture||390|
|7.3.4. The Birch and SwinnertonDyer 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 Fp||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|
Factoring in the Dark Ages
|8.1.||Factoring and Primality Testing||419|
|8.3.1. The PocklingtonLehmer ||423|
|8.3.2. Briefly, Other Tests||424|
|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.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|
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 Lp||455|
|9.1.5. The Use of Jacobi Sums||457|
|9.1.6. Detailed Description of the Algorithm||463|
|9.2.||The Elliptic Curve Test||467|
|9.2.1. The GoldwasserKilian Test||467|
|9.2.2. Atkin's Test||471|
|9.3.||Exercises for Chapter 9||475|
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 SchnorrLenstra 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.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|
|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|
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:
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
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|
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)|
|· · ·|
|(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
|· · ·|
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
|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
|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 cp can be found by using Tate's Algorithm 7.5.1. The coefficients ap 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
|· · ·|
[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
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), 6471.
[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), 173206.
[AGP] R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703722.
[Ang] I. Angell, A table of complex cubic fields, Bull. London Math. Soc. 5 (1973), 3738.
[Arn] F. Arnault, The RabinMiller primality test: composite numbers which pass it, Math. Comp. 64 (1995), 335361.
[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), 2968.
[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), 355380.
[Bar] E. Bareiss, Sylvester's identity and multistep integer-preserving Gaussian elimination, Math. Comp. 22 (1968), 565578.
[BeMaOl] A.-M. Bergé, J. Martinet and M. Olivier, The computation of sextic fields with a quadratic subfield, Math. Comp. 54 (1990), 869884.
[Ber] E. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713735.
[Bir-SwD] B. Birch and H. P. F. Swinnerton-Dyer, Notes on elliptic curves I, J. Reine Angew. Math. 212 (1963), 725; II, ibid. 218 (1965), 79108.
[BFHT] A. Borodin, R. Fagin, J. Hopcroft and M. Tompa, Decreasing the nesting depth of expressions involving square roots, J. Symb. Comp. 1 (1985), 169188.
[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), 897907.
[Brau] R. Brauer, On the Zeta-function of algebraic number fields I, Amer. J. Math. 69 (1947), 243250; II, ibid. 72 (1950), 739746.
[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), 176184.
[Bre3] R.P. Brent, The first occurence of large gaps between successive primes, Math. Comp. 27 (1973), 959963.
[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 F7, Math. Comp. 29 (1975), 183205.
[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. 379393.
[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), 2532.
[Buc1] J. Buchmann, A generalization of Voronoi's unit algorithm I and II, J. Number Theory 20 (1985), 177209.
[Buc2] J. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm, J. Number Theory 26 (1987), 830.
[Buc3] J. Buchmann, On the period length of the generalized Lagrange algorithm, J. Number Theory ,B>26 (1987), 3137.
[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. 5372.
[Buc-Ford] J. Buchmann and D. Ford, On the computation of totally real quartic fields of small discriminant, Math. Comp. 52 (1989), 161174.
[BFP] J. Buchmann, D. Ford and M. Pohst, Enumeration of quartic fields of small discriminant, Math. Comp. 61 (1993), 873879.
[Buc-Len] J. Buchmann and H. W. Lenstra, Computing maximal orders and factoring over Zp, preprint.
[Buc-Len2] J. Buchmann and H. W. Lenstra, Approximating rings of integers in number fields, J. Th. des Nombres Bordeaux (Série 2) 6 (1994), 221260.
[Buc-Pet] J. Buchmann and A. Petho, On the computation of independent units in number fields by Dirichlet's method, Math. Comp. 52 (1989), 149159.
[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), 387397.
[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. 159185.
[Buc-Wil] J. Buchmann and H. Williams, On principal ideal testing in algebraic number fields, J. Symb. Comp. 4 (1987), 1119.
[Bue1] D. Buell, The expectation of success using a Monte-Carlo factoring method some statistics on quadratic class numbers, Math. Comp. 43 (1984), 313327.
[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), 863911.
[CEP] E. R. Canfield, P. Erdos and C. Pomerance, On a problem of Oppenheim concerning "Factorisatio Numerorum", J. Number Theory 17 (1983), 128.
[Can-Zas] D. Cantor and H. Zassenhaus, A new algorithm for factoring polynomials over finite fields, Math. Comp. 36 (1981), 587592.
[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), 187237.
[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), 6393.
[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), 389402.
[Coh-Diaz] H. Cohen and F. Diaz y Diaz, A polynomial reduction algorithm, Sem. Th. Nombres Bordeaux (Série 2) 3 (1991), 351360.
[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 199091 (1993), 3546.
[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. 3362.
[Coh-Len2] H. Cohen and H. W. Lenstra, Primality testing and Jacobi sums, Math. Comp. 42 (1984), 297330.
[Coh-Len3] H. Cohen and A. K. Lenstra, Implementation of a new primality test, Math. Comp. 48 (1987), 103121.
[Coh-Mar1] H. Cohen and J. Martinet, Class groups of number fields: numerical heuristics, Math. Comp. 48 (1987), 123137.
[Coh-Mar2] H. Cohen and J. Martinet, Etude heuristique des groupes de classes des corps de nombres, J. Reine Angew. Math. 404 (1990), 3976.
[Coh-Mar3] H. Cohen and J. Martinet, Heuristics on class groups: some good primes are not too good, Math. Comp. 63 (1994), 329334.
[Col] G. Collins, The calculation of multivariate polynomial resultants, JACM 18 (1971), 515532.
[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), 273307.
[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), 801808 and S1S12.
[DKT] P. Domich, R. Kannan and L. Trotter, Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Research 12 (1987), 5059.
[Duk] W. Duke, Hyperbolic distribution functions and half-integral weight Maass forms, Invent. Math. 92 (1988), 7390.
[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), 153180.
[Enn-Turl] V. Ennola and R. Turunen, On totally real cubic fields, Math. Comp. 44 (1985), 495518.
[Enn-Tur2] V. Ennola and R. Turunen, On cyclic cubic fields, Math. Comp. 45 (1985), 585589.
[Fal] G. Faltings, Endlichkeitssätze fur abelsche Varietäten über Zahlkörpern, Invent. Math. 73 (1983), 349366.
[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), 463471.
[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), 6975.
[Ford3] D. Ford, Enumeration of totally complex quartic fields of small discriminant, in [PPWZ], 1991, pp. 129138.
[Fri] E. Friedman, Analytic formulas for the regulator of a number field, Invent. Math. 98 (1989), 599622.
[Gir] K. Girstmair, On invariant polynomials and their application in field theory, Math. Comp. 48 (1987), 781797.
[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), 316329.
[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), 89116.
[Gro-Zag1] B. Gross and D. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191220.
[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), 497562.
[Haf-McCur1] J. Hafner and K. McCurley, A rigorous subexponential algorithm for computation of class groups, Journal American Math. Soc. 2 (1989), 837850.
[Haf-McCur2] J. Hafner and K. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), 10681083.
[Has] H. Hasse, Arithmetische Theorie der kubischen Zahlkörper auf klassenkörpertheoretischer Grundlage, Math. Zeit. 31 (1930), 565582; Math. Abhandlungen, Walter de Gruyter, 1975, pp. 423440.
[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), 859881.
[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), 5767.
[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 19891990, Springer-Verlag, 1991, pp. 150202.
[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), 499507.
[Kol1] V. A. Kolyvagin, Finiteness of
[Kol2] V. A. Kolyvagin, Euler systems, Progress in Math. 87, Grothendieck Festschrift II, Birkhäuser, Boston, 1991, pp. 435483.
[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. 109133.
[Las] M. Laska, An algorithm for finding a minimal Weierstrass equation for an elliptic curve, Math. Comp. 38 (1982), 257260.
[Leh1] S. Lehman, Factoring large integers, Math. Comp. 28 (1974), 637646.
[Leh2] D. H. Lehmer, On Fermat's quotient, base two, Math. Comp. 36 (1981), 289290.
[Len1] H. W. Lenstra, On the computation of regulators and class numbers of quadratic fields, Lond. Math. Soc. Lect. Note Ser. 56 (1982), 123150.
[Len2] H. W. Lenstra, Divisors in residue classes, Math. Comp. 42 (1984), 331334.
[Len3] H. W. Lenstra, Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649673.
[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. 673715.
[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), 515534.
[LLMP] A. K. Lenstra, H. W. Lenstra, M. S. Manasse and J. M. Pollard, The Number Field Sieve, in [Len-Len2], 1993, pp. 1142.
[Llo-Quer] P. Llorente and J. Quer, On the 3-Sylow subgroup of the class group of quadratic fields, Math. Comp. 50 (1988), 321333.
[Mah] K. Mahler, On a class of non-linear functional equations connected with modular functions, J. Austral. Math. Soc. 22A (1976), 65118.
[Mart] J. Martinet, Méthodes géométriques dans la recherche des petits discriminants, Progress in Math. 59, 1985, pp. 147179.
[Maz] B. Mazur, Rational isogenies of prime degree, Invent. Math. 44 (1978), 129162.
[McCur] K. McCurley, Cryptographic key distribution and computation in class groups, Proceedings of NATO ASI Number Theory and applications, Kluwer Academic Publishers, 1989, pp. 459479.
[Mer] L. Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124 (1996), 437449.
[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), 209232.
[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), 11531157.
[Mil] G. Miller, Riemann's hypothesis and tests for primality, J. Comput. and System Sc. 13 (1976), 300317.
[Mol-Wil] R. Mollin and H. Williams, Computation of the class number of a real quadratic field, Utilitas Math. 41 (1992), 259308.
[Mon-Nar] J. Montes and E. Nart, On a theorem of Ore, Journal of Algebra 146 (1992), 318339.
[Mon1] P. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), 519521.
[Mon2] P. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comp. 48 (1987), 243264.
[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), 117141.
[Oes] J. Oesterle, Nombre de classes des corps quadratiques imaginaires, in Séminaire Bourbaki 198384, Astérisque 121122, Soc. Math, de France, 1985, pp. 309323.
[Oli1] M. Olivier, Corps sextiques primitifs, Ann. Institut Fourier 40 (1990), 757767.
[Oli2] M. Olivier, The computation of sextic fields with a cubic subfield and no quadratic subfield, Math. Comp. 58 (1992), 419432.
[Oli3] M. Olivier, Tables de corps sextiques contenant un sous-corps quadratique (I), Sém. Th. des Nombres Bordeaux (Série 2) 1 (1989), 205250.
[Oli4] M. Olivier, Corps sextiques contenant un corps quadratique (II), Sém. Th. des Nombres Bordeaux (Série 2) 2 (1990), 49102.
[Oli5] M. Olivier, Corps sextiques contenant un corps cubique (III), Sém. Th. des Nombres Bordeaux (Série 2) 3 (1991), 201245.
[Oli6] M. Olivier, Corps sextiques primitifs (IV), Sém. Th. des Nombres Bordeaux (Série 2) 3 (1991), 381404.
[Ore] Ö. Ore, Newtonsche Polygone in der Theorie der algebraischen Körper, Math. Ann. 99 (1928), 84117.
[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), 99117.
[Poh2] M. Pohst, A modification of the
[Poh3] M. Pohst, On computing isomorphisms of equation orders, Math. Comp. 48 (1987), 309314.
[Poh4] M. Pohst, A note on index divisors, in [PPWZ], 1991, pp. 173182.
[Poh-Wei-Zas] M. Pohst, P. Weiler and H. Zassenhaus, On effective computation of fundamental units I and II, Math. Comp. 38 (1982), 275329.
[Poh-Zasl] M. Pohst and H. Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraische Zahlkörper, J. Reine Angew. Math. 361 (1985), 5072.
[Pol1] J. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Phil.Soc. 76 (1974), 521528.
[Pol2] J. Pollard, A Monte-Carlo method for factorization, BIT 15 (1975), 331334.
[Pom] C. Pomerance, Analysis and comparison of some integer factoring algorithms, in [MCC], 1983, pp. 89139.
[Quer] J. Quer, Corps quadratiques de
[Rab] M. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128138.
[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. 321330.
[Schn] C.P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1988), 4762.
[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. 6885.
[Schn-Len] C. P. Schnorr and H. W Lenstra, A Monte-Carlo factoring algorithm with linear storage, Math. Comp. 43 (1984), 289312.
[Schön] A. Schönhage, Probabilistic computation of integer polynomial GCD, J. Algorithms 9 (1988), 365371.
[Scho] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 43 (1985), 483494.
[Scho2] R. Schoof, Counting points of elliptic curves over finite fields, J. Th. des Nombres Bordeaux (Série 2) 7 (1995), 219254.
[SPD] A. Schwarz, M. Pohst and F. Diaz y Diaz, A table of quintic number fields, Math. Comp. 63 (1994), 361376.
[Sel-Wun] J. Selfridge and M. Wunderlich, An efficient algorithm for testing large numbers for primality, Proc. Fourth Manitoba Conf. Numer. Math. (1974), 109120.
[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), 757780.
[Sey2] M. Seysen, Simultaneous reduction of a lattice basis and its reciprocal basis, Combinatorica 13 (1993), 363376.
[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. 415440.
[Sha2] D. Shanks, On Gauss and composition I and II, Number theory and applications, R. Mollin (ed.), Kluwer Academic Publishers, 1989, pp. 163204.
[Sha3] D. Shanks, The infrastructure of a real quadratic field and its applications, Proc. 1972 Number theory conference, Boulder (1972), 217224.
[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), 13171320.
[Shi1] G. Shimura, On the zeta-function of an Abelian variety with complex multiplication, Ann. of Math. 94 (1971), 504533.
[Shi2] G. Shimura, On elliptic curves with complex multiplication as factors of the Jacobians of modular function fields, Nagoya Math. J. 43 (1971), 199208.
[Sie] C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arith. 1 (1935), 8386.
[Sil1] R. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329340.
[Sil2] J. Silverman, Computing heights on elliptic curves, Math. Comp. 51 (1988), 339358.
[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), 273281.
[Sol-Str] R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), 8485; 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. 153174.
[Stau] R. P. Stauduhar, The determination of Galois groups, Math. Comp. 27 (1973), 981996.
[Tay-Wil] R. Taylor and A. Wiles, Ring-theoretic properties of certain Hecke algebras, Ann. of Math. 141 (1995), 553572.
[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), 333336.
[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), 785800.
[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), 497508.
[Wie] D. Wiedemann, Solving sparse linear equations over finite fields, IEEE Trans. Information Theory 32 (1986), 5462.
[Wiles] A. Wiles, Modular elliptic curves and Fermat's last theorem, Ann. of Math. 141 (1995), 443551.
[Wil-Jud] H. Williams and J. Judd, Some algorithms for prime testing using generalized Lehmer functions, Math. Comp. 30 (1976), 157172 and 867886.
[Wil-Zar] H. Williams and C. Zarnke, Some algorithms for solving a cubic congruence modulo p, Utilitas Math. 6 (1974), 285306.
[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), 425436.
[Zim1] R. Zimmert, Ideale kleiner Norm in Idealklassen und eine Regulatorabschätzung, Invent. Math. 62 (1981), 367380.
[Zip] R. Zippel, Simplification of expressions involving radicals, J. Symb. Comp. 1 (1985), 189210.
Abelian group, 66
addition chain, 11
addition theorem, 370
additive degeneracy, 373
adjoint matrix, 54
Adleman, L., 445, 471, 501
affine subspace, 486
algebraic integer, 153
algebraic number, 153
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
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
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
characteristic polynomial, 53, 162
Chinese remainder theorem, 19
Cholesky decomposition, 104
Chudnovsky, D. and G., 490
class group, 207, 228
class number, 208
coefficient explosion, 5, 112, 114
Cohen, H., 168, 254, 288, 296, 352, 445
Collins, G., 118
column echelon form, 59
column vector, 7
compact representation of units, 279, 285
complementary error function, 238
completely split prime, 197
complex multiplication, 381
compositeness test, 419
conductor-discriminant formula, 168
congruent number, 376
conjugate vector representation, 161
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
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 of a lattice, 80
Diaz y Diaz, F., 168, 254, 288, 313, 352, 363
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
early abort strategy, 259, 480
Eichler, M., 236
Eisenstein polynomial, 315
elementary divisor, 76
elementary operations, 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
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
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
Galois closure, 157
Galois group, 157, 322
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
Gross, B., 216, 234, 385, 394
group ring, 446
Hadamard's inequality, 51, 82
Hafner, J., 69, 70, 77, 252
Hasse, H., 373, 462
Hasse-Weil L-function, 389
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
Huang, M. D., 445, 471
Hurwitz class number, 234
intersection, 207, 219
representation, 188, 190
two-element representation, 192
idele class group, 209
image of a matrix, 58
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
isomorphism problem, 179
Iwasawa decomposition, 83
Jacobi sum, 448
Jacobi symbol, 28
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-function, 266, 388, 389
LaMacchia, B., 89, 254
large prime variation, 258, 480
Laska, M., 409
lattice, 23, 80
determinant of, 80
Legendre symbol, 27
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
LLL algorithm, 87
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
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
modular equation, 386
modular forms, 234, 390
modular functions, 379
modular invariant, 377
modular multiplication, 4
modules product of, 189
Montgomery, P., 5, 429, 489, 492
Morain, F., 445, 471, 474
Mordell, L., 375
Nagao, K., 394
narrow class group, 228
Neumann, W., 102
Newton polygon, 313
Newton's formulas, 163
Newton's method, 38, 45
non-split multiplicative degeneracy, 373
norm of a fractional ideal, 187
of an element, 162
of an ideal, 182
normal closure, 157
number field, 154
Odlyzko, A., 254, 465
Oesterle, J., 295
Olivier, M., 171, 175, 254, 288, 313, 329, 333, 352, 513
order of a group element, 24
orthogonal basis, 82
orthogonal matrix, 81
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
pivot, 48, 65
place finite, 187
of a number field, 187
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
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
quadratic form, 79, 225
positive definite, 80
quadratic reciprocity law, 27
Quer, J., 297
Rabin, M., 421
ramification index, 197
ramified prime, 197
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
relative extensions, 329
residual degree, 197
resolvent polynomial, 323
Ribet, K., 392
roots of unity, 209
row vector, 7
Rubin, K., 394
Rumely, R., 445
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
Silverman, J., 367
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
sparse matrix, 254, 480
sparse representation, 109
special subset, 486
split multiplicative degeneracy, 373
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
Swinnerton-Dyer, H., 392
Sylvester's matrix, 120
symmetric function, 162
Taniyama, T., 391
TaniyamaWeil 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
trial division, 419
triple Jacobi sum, 460
Tschirnhausen transformation, 324
two element representation, 193
Ubasic, 2, 508
Unique factorization domain, 114
unit, 114, 209
unramified prime, 197
upper half-plane, 378
Vallée, B., 84
van der Hulst, P., 466
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
Zagier, D., 216, 234, 236, 385, 394
Zassenhaus H., 127, 304
zeta function of a number field, 214
of a variety, 388