Binary Quadratic Forms: An Algorithmic Approach Volume 20

"The book deals with algorithmic problems related to binary quadratic forms, such as finding the representations of an integer by a form with integer coefficients, finding the minimum of a form with real coefficients and deciding equivalence of two forms." "In order to solve those problems, the book introduces the reader to important areas of number theory such as diophantine equations, reduction theory of quadratic forms, geometry of numbers and algebraic number theory. The book explains applications to cryptography . It requires only basic mathematical knowledge."--Jacket This book deals with algorithmic problems concerning binary quadratic forms 2 2 f(X,Y)= aX +bXY +cY with integer coe?cients a, b, c, the mathem- ical theories that permit the solution of these problems, and applications to cryptography. A considerable part of the theory is developed for forms with real coe?cients and it is shown that forms with integer coe?cients 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 ofmanyof theseproblemspossible.Algorithmicsolutionsandtheirproperties became an object of study in their own right. Thisbookintertwinestheexpositionofoneveryclassicalstrandofnumber 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 e?ciency 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 pr- lems such as the solution of Pell equations with large coe?cients. On the other, the application of number theory in public-key cryptography increased the urgency for establishing the complexity of several computational pr- lems: many a computer system stays only secure as long as these problems remain intractable.

The book deals with algorithmic problems related to binary quadratic forms. It uniquely focuses on the algorithmic aspects of the theory. The book introduces the reader to important areas of number theory such as diophantine equations, reduction theory of quadratic forms, geometry of numbers and algebraic number theory. The book explains applications to cryptography and requires only basic mathematical knowledge. The author is a world leader in number theory.

front-matter.pdf......Page 1 1.pdf......Page 13 2.pdf......Page 20 3.pdf......Page 32 4.pdf......Page 46 5.pdf......Page 68 6.pdf......Page 96 7.pdf......Page 117 8.pdf......Page 153 9.pdf......Page 167 10.pdf......Page 187 11.pdf......Page 227 12.pdf......Page 243 13.pdf......Page 282 back-matter.pdf......Page 297