Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

1993 | Buch

Fundamental Number-Theoretic Algorithms Kapitel lesen Erstes Kapitel lesen

A Course in Computational Algebraic Number Theory

verfasst von: Henri Cohen

Verlag: Springer Berlin Heidelberg

Buchreihe : Graduate Texts in Mathematics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

With the advent of powerful computing tools and numerous advances in math­ ematics, 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 al­ gorithms. 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 appli­ cations, 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.

Inhaltsverzeichnis

Frontmatter
Chapter 1. Fundamental Number-Theoretic Algorithms
Abstract
This book describes in detail a number of algorithms used in algebraic number theory and the theory of elliptic curves. It also gives applications to problems such as factoring and primality testing. Although the algorithms and the theory behind them are sufficiently interesting in themselves, I strongly advise the reader to take the time to implement them on her/his favorite machine. Indeed, one gets a feel for an algorithm mainly after executing it several times. (This book does help by providing many tricks that will be useful for doing this.)
Henri Cohen
Chapter 2. Algorithms for Linear Algebra and Lattices
Abstract
In many algorithms, and in particular in number-theoretic ones, it is necessary to use algorithms to solve common problems of linear algebra. For example, solving a linear system of equations is such a problem. Apart from stability considerations, such problems and algorithms can be solved by a single algorithm independently of the base field (or more generally of the base ring if we work with modules). Those algorithms will naturally be called linear algebra algorithms.
Henri Cohen
Chapter 3. Algorithms on Polynomials
Abstract
Excellent book references on this subject are [Knul] and [GCL].
Henri Cohen
Chapter 4. Algorithms for Algebraic Number Theory I
Abstract
In this chapter, we give the necessary background on algebraic numbers, number fields, modules, ideals and units, and corresponding algorithms for them. Excellent basic textbooks on these subjects are, for example [Bo-Sh], [Cas-Frö], [Cohn], [Ire-Ros], [Marc], [Sam] however these have little algorithmic flavor. We will give proofs only when they help to understand an algorithm, and we urge the reader to refer to the above textbooks for the proofs which are not given.
Henri Cohen
Chapter 5. Algorithms for Quadratic Fields
Abstract
In this chapter, we consider the simplest of all number fields that are different from ℚ, i.e. quadratic fields. Since n = 2 = r 1 + 2r 2, the signature (r 1, r 2) of a quadratic field K is either (2, 0), in which case we will speak of real quadratic fields, or (0, 1), in which case we will speak of imaginary (or complex) quadratic fields. By Proposition 4.8.11 we know that imaginary quadratic fields are those of negative discriminant, and that real quadratic fields are those with positive discriminant.
Henri Cohen
Chapter 6. Algorithms for Algebraic Number Theory II
Abstract
We now leave the realm of quadratic fields where the main computational tasks of algebraic number theory mentioned at the end of Chapter 4 were relatively simple (although as we have seen many conjectures remain), and move on to general number fields.
Henri Cohen
Chapter 7. Introduction to Elliptic Curves
Abstract
The aim of this chapter is to give a brief survey of results, essentially without proofs, about elliptic curves, complex multiplication and their relations to class groups of imaginary quadratic fields. A few algorithms will be given (in Section 7.4, so as not to interrupt the flow of the presentation), but, unlike other chapters, the main emphasis will be on the theory (some of which will be needed in the next chapters). We also describe the superb landscape that is emerging in this theory, although much remains conjectural. It is worth noting that many of the recent advances on the subject (in particular the Birch and Swinnerton-Dyer conjecture) were direct consequences of number-theoretical experiments. This lends further support to the claim that number theory, even in its sophisticated areas, is an experimental as well as a theoretical science.
Henri Cohen
Chapter 8. Factoring in the Dark Ages
Abstract
I owe this title to a talk given by Hendrik Lenstra at MSRI Berkeley in the spring of 1990.
Henri Cohen
Chapter 9. Modern Primality Tests
Abstract
In Section 8.3, we studied various primality tests, essentially the N − 1 test, and saw that they require knowing the factorization of N − 1 (or N + 1, ... ), which are large numbers. Even though only partial factorizations are needed, the tests of Section 8.3 become impractical as soon as N has more than 100 digits, say. A breakthrough was made in 1980 by Adleman, Pomerance and Rumely, that enabled testing the primality of much larger numbers. The APR test was further simplified and improved by H. W. Lenstra and the author, and the resulting APRCL test was implemented in 1981 by A. K. Lenstra and the author, with the help of D. Winter. It is now possible to prove the primality of numbers with 1000 decimal digits in a not too unreasonable amount of time. The running time of this algorithm is O((ln N) C In in In N )for a suitable constant C. This is almost a polynomial time algorithm since for all practical purposes the function In In In N acts like a constant. (Note that the practical version of the algorithm is probabilistic, but that there exists a non-probabilistic but less practical version.)
Henri Cohen
Chapter 10. Modern Factoring Methods
Abstract
The aim of this chapter is to give an overview of the fastest factoring methods known today. This could be the object of a book in itself, hence it is unreasonable to be as detailed here as we have been in the preceding chapters. In particular, most methods will not be written down as formal algorithms as we have done before. We hope however that we will have given sufficient information so that the reader may understand the methods and be able to implement them, at least in unoptimized form. The reader who wants to implement these methods in a more optimized form is urged to read the abundant literature after reading this chapter, before doing so.
Henri Cohen
Backmatter
Metadaten
Titel
A Course in Computational Algebraic Number Theory
verfasst von
Henri Cohen
Copyright-Jahr
1993
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-662-02945-9
Print ISBN
978-3-642-08142-2
DOI
https://doi.org/10.1007/978-3-662-02945-9