Solving the Pell equation (Q953181): Difference between revisions

As the title of the book indicates the main topic of the book is the resolution of the Diophantine equation \[ X^2-DY^2=1 \] for integral positive non-square \(D\). It is well known that all positive solutions \((X,Y)\) to this equation are of the form \[ X+Y\sqrt{D}=(X_0+Y_0\sqrt D)^n \] for some positive exponent \(n\), where \((X_0,Y_0)\) is the fundamental (smallest positive) solution. Therefore to solve the Pell equations completely it is enough to find this fundamental solution. For a beginner this sounds easy, but in fact by the Cohen-Lenstra heuristic [\textit{H. Cohen} and \textit{H. W. Lenstra jun.}, Heuristics on class groups of number fields. Number theory, Proc. Journ. arith., Noodwijkerhout/Neth. 1983, Lect. Notes Math. 1068, 33--62 (1984; Zbl 0558.12002)] we expect that the size of the fundamental solution grows exponentially and so it is far from being easy. But fortunately in the past many algorithms have been developed to compute the regulator efficiently. In particular, the subexponential algorithm due to [\textit{J. Buchmann}, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. Sémin. Théor. Nombres, Paris/Fr. 1988--89, Prog. Math. 91, 27--41 (1990; Zbl 0727.11059)] is worth mentioning. But also in cryptography Pell equations were used, e.g. [see \textit{M. O. Rabin}, Digitalized signatures. Foundations of secure computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977),155--168, Academic Press, New York etc. (1978; Zbl 0431.68085)]. The book under review is a modern treatment of these topics. So not only Pell equations are solved, but the authors also provide up-to-date algorithms to compute regulators, class numbers and class groups for quadratic fields with high discriminant. Although, as the authors write in the introduction, that the book is not intended to be a textbook an interested reader can learn a lot on the algorithmic algebraic number theory of quadratic fields. The book provides at many places ready to apply algorithms. So the reader is not left with the feeling, being unsure how to perform computations by himself, as it is the case in many other books on this topic. As the authors write in their preface, one of the aims of the book is to show the dramatic computational development of the topic since Shanks discovery of the so-called infrastructure of the ideal class till now. This aim is clearly reached by this book. The book consists of 17 chapters and one Appendix: In the first chapter (Introduction) the authors treat basic facts on the Pell equation \(X^2-DY^2=\pm 4\). In particular they prove the infinity of solutions and their structure. Also Lucas sequences are discussed. The second chapter (Early History of the Pell Equation), a second introduction, gives an overview of the history starting with Archimedes' ``Cattle Problem'' and ending with Fermat's contribution to the problem. In this chapter various ancient methods to solve Pell equations are explained. The third chapter deals with continued fraction expansions. Of particular interest are the fraction expansions of quadratic irrationalities of the form \(\frac{P+\sqrt{D}}Q\). Also the length of the period of continued fractions of quadratic irrationals is discussed in view of finding fundamental solutions to Pell equations. Chapter four describes the classical algebraic number theory of quadratic extensions. Chapter five continues these investigations. In particular, it is devoted to reduced ideals and techniques to compute them by using continued fractions. The last section of this chapter describes NUCOMP, i.e. the computation of the reduced product of two ideals. The authors present here a rather new version of Shanks' algorithm [\textit{D. Shanks}, Number theory and applications. II. Number theory and applications, Proc. NATO ASI, Banff/Can. 1988, NATO ASI Ser., Ser. C 265, 179--204 (1989; Zbl 0691.10011)]. According to the author's the sixth chapter deals with Pell equations that have small fundamental solutions. So they present a famous theorem of \textit{C. Størmer} [Christiania Vidensk. Skrifter. M. N. Klasse No. 2. Udgivet for Fridthjof Nansen's Fond. 48 p. (1897; JFM 28.0192.02)]. In the sequel they also deal with the length of the period of continued fractions of quadratic irrationals of the form \(\sqrt{f(X)}\). The chapter closes with a result of \textit{Y. Yamamoto} [Osaka J. Math. 8, 261--270 (1971; Zbl 0243.12001)] on the existence of families of quadratic fields having large regulator. In chapter seven the Cohen-Lenstra heuristics are studied and other theorems and conjectures concerning the structure of the ideal class group. The chapter also provides Shanks' celebrated baby-step giant-step algorithm to compute the regulator. Chapter eight is devoted to the celebrated class number formula. Therefore Dirichlet characters and \(L\)-functions are introduced. These analytic investigations are continued in chapter nine. In chapter ten the analytic class number formula is used to derive algorithms to determine the regulator. Once the regulator is found it is described how to find the class number (again using the analytic class number formula). So the computation of the class group is tackled next. The algorithms are given for the real quadratic case, but as the authors remark it is rather straightforward to extend the algorithms for the computation of the class number and class group to imaginary quadratic fields. Since the numeric aspect of the analytic class number formulas and in particular in the application to the computation of the regulator and class group, chapter 11 develops methods to keep track of error bounds in the computation of reduced ideals and the infrastructure. Moreover it shows how to deal rigorously with numeric errors appearing in the computations. These considerations are continued in chapter 12 and lead to compact representations, which play an important role in todays computational applications of quadratic fields. Chapter 13 is devoted to sub-exponential algorithms -- variants of the so-called index calculus algorithm -- to compute regulator, class number and class group of quadratic number fields. As the authors remark the algorithms depend all on the extended (ERH) and also generalized Riemann hypotheses (GRH). Also principal ideal testing (assuming ERH and GRH) is treated in this chapter. But in chapter 15 methods are proposed to verify these results unconditional. Chapter 14 deals with cryptosystems which are based on quadratic fields. In particular a variant of the Rabin cryptosystem is discussed, and variants of the Diffie-Hellman key exchange in the class group of imaginary quadratic fields and in the infrastructure of real quadratic fields are described. Also the usage of non-maximal orders to create trapdoor functions is explained. Chapter 16 is devoted to principal ideal testing (unconditional). As an application the equation \(X^2-DY^2=N\) is considered. The last chapter called Conclusion provides possible generalizations to Pell equations. Also open problems are discussed. Since many of the provided algorithms in this book are rather long, some of them have been placed in an appendix.