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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

or else to write to the author's address:

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

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

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

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

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

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

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

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

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

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

Conclusions

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

Where to obtain these packages

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

One can find at the URL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Studies in detail the complexity of number-theoretic algorithms.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A very nicely written little book on abstract algebra.

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

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

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

An advanced abstract introduction to the subject.

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

A nice introductory book on elliptic functions and elliptic curves.

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

A nice introductory book on modular forms.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

The long awaited sequel to [Sil].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[Buc-Len] J. Buchmann and H. W. Lenstra, Computing maximal orders and factoring over 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 Swinnerton-Dyer for an elliptic curve of rank 3, Math. Comp. 44 (1985), 473–481.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[Fer2] S. Fermigier, in preparation.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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