Binary Quadratic Forms

This book deals with algorithmic problems concerning binary quadratic forms 2 2 f(X,Y)= aX +bXY +cY with integer coefficients a, b, c, the mathemetical theories that permit the solution of these problems, and applications to cryptography. A considerable part of the theory is developed for forms with real coefficients and it is shown that forms with integer coefficients appear in a natural way. Much of the progress of number theory has been stimulated by the study of concrete computational problems. Deep theories were developed from the classic time of Euler and Gauss onwards to this day that made the solutions of many of these problems possible. Algorithmic solutions and their properties became an object of study in their own right.

This book intertwines the exposition of one very classical strand of number theory with the presentation and analysis of algorithms both classical and modern which solve its motivating problems. This algorithmic approach will lead the reader, we hope, not only to an understanding of theory and solution methods, but also to an appreciation of the efficiency with which solutions can be reached. The computer age has led to a marked advancement of algorithmic - search. On the one hand, computers make it feasible to solve very hard problems such as the solution of Pell equations with large coefficients. On the other, the application of number theory in public-key cryptography increased the urgency for establishing the complexity of several computational problems: many a computer system stays only secure as long as these problems remain intractable.