ebook ebooks e-book e-books downloaden bei MyEbooks.ch downloaden

Binary Quadratic Forms An Algorithmic Approach

:	Johannes Buchmann, Ulrich Vollmer
:	Binary Quadratic Forms An Algorithmic Approach
:	Springer-Verlag
:	9783540463689
:	1
:	CHF 47.40
:

:	Arithmetik, Algebra
:	English

:	318
:	Wasserzeichen
:	PC/MAC/eReader/Tablet
:	PDF

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.Algorit micsolutionsandtheirpropertie became an object of study in their own right. Thisbookintertwinestheexposit onofoneveryclassicalstrandofn mber 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.

	Contents	5
	List of Figures	11
	List of Algorithms	12
	Introduction	14
	Content	16
	Acknowledgments	19
	Chapter references and further reading	19
	1 Binary Quadratic Forms	21
	1.1 Computational problems	21
	1.2 Discriminant	24
	1.3 Reducible forms with integer coefficients	27
	1.4 Applications	29
	1.5 Exercises	32
	Chapter references and further reading	32
	2 Equivalence of Forms	33
	2.1 Transformation of forms	33
	2.2 Equivalence	34
	2.3 Invariants of equivalence classes of forms	35
	2.4 Two special transformations	36
	2.5 Automorphisms of forms	38
	2.6 A strategy for finding proper representations	42
	2.7 Determining improper representations	44
	2.8 Ambiguous classes	44
	2.9 Exercises	45
	3 Constructing Forms	47
	3.1 Reduction to finding square roots of . modulo 4a	47
	3.2 The case a	47
	48	47
	3.3 Fundamental discriminants and conductor	49
	3.4 The case of a prime number	50
	3.5 The case of a prime power	61
	3.6 The case of a composite integer	65
	3.7 Exercises	66
	Chapter references and further reading	68
	4 Forms, Bases, Points, and Lattices	69
	4.1 Two-dimensional commutative R-algebras	69
	4.2 Irrational forms, bases, points and lattices	79
	4.3 Bases, points, and forms	81
	4.4 Lattices and forms	87
	4.5 Quadratic irrationalities and forms	91
	4.6 Quadratic lattices and forms	94
	4.7 Exercises	95
	5 Reduction of Positive Definite Forms	97
	5.1 Negative definite forms	97
	5.2 Normal forms	98
	5.3 Reduced forms and the reduction algorithm	99
	5.4 Properties of reduced forms	102
	5.5 The number of reduction steps	103
	5.6 Bit complexity of the reduction algorithm	104
	5.7 Uniqueness of re