Buchmann / Vollmer Binary Quadratic Forms

An Algorithmic Approach
1. Auflage 2007
ISBN: 978-3-540-46368-9
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 20, 318 Seiten

Reihe: Algorithms and Computation in Mathematics

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.

Autoren/Hrsg.

Buchmann, Johannes

Vollmer, Ulrich

Inhaltsverzeichnis

1;Contents;5
2;List of Figures;11
3;List of Algorithms;12
4;Introduction;14
4.1;Content;16
4.2;Acknowledgments;19
4.3;Chapter references and further reading;19
5;1 Binary Quadratic Forms;21
5.1;1.1 Computational problems;21
5.2;1.2 Discriminant;24
5.3;1.3 Reducible forms with integer coefficients;27
5.4;1.4 Applications;29
5.5;1.5 Exercises;32
5.6;Chapter references and further reading;32
6;2 Equivalence of Forms;33
6.1;2.1 Transformation of forms;33
6.2;2.2 Equivalence;34
6.3;2.3 Invariants of equivalence classes of forms;35
6.4;2.4 Two special transformations;36
6.5;2.5 Automorphisms of forms;38
6.6;2.6 A strategy for finding proper representations;42
6.7;2.7 Determining improper representations;44
6.8;2.8 Ambiguous classes;44
6.9;2.9 Exercises;45
7;3 Constructing Forms;47
7.1;3.1 Reduction to finding square roots of . modulo 4a;47
7.2;3.2 The case a < 0;48
7.3;3.3 Fundamental discriminants and conductor;49
7.4;3.4 The case of a prime number;50
7.5;3.5 The case of a prime power;61
7.6;3.6 The case of a composite integer;65
7.7;3.7 Exercises;66
7.8;Chapter references and further reading;68
8;4 Forms, Bases, Points, and Lattices;69
8.1;4.1 Two-dimensional commutative R-algebras;69
8.2;4.2 Irrational forms, bases, points and lattices;79
8.3;4.3 Bases, points, and forms;81
8.4;4.4 Lattices and forms;87
8.5;4.5 Quadratic irrationalities and forms;91
8.6;4.6 Quadratic lattices and forms;94
8.7;4.7 Exercises;95
9;5 Reduction of Positive Definite Forms;97
9.1;5.1 Negative definite forms;97
9.2;5.2 Normal forms;98
9.3;5.3 Reduced forms and the reduction algorithm;99
9.4;5.4 Properties of reduced forms;102
9.5;5.5 The number of reduction steps;103
9.6;5.6 Bit complexity of the reduction algorithm;104
9.7;5.7 Uniqueness of reduced forms;106
9.8;5.8 Deciding equivalence;108
9.9;5.9 Solving the representation problem;109
9.10;5.10 Solving the minimum problem;110
9.11;5.11 Class number;110
9.12;5.12 Reduction of semidefinite forms;113
9.13;5.13 Geometry of reduction;114
9.14;5.14 The densest two-dimensional lattice packing;115
9.15;5.15 Exercises;116
9.16;Chapter references and further reading;117
10;6 Reduction of Indefinite Forms;118
10.1;6.1 Normal forms;118
10.2;6.2 Reduced forms;120
10.3;6.3 Another characterization of reduced forms;121
10.4;6.4 The reduction algorithm;123
10.5;6.5 The number of reduction steps;124
10.6;6.6 Complexity of reducing integral forms;126
10.7;6.7 Enumerating integral reduced forms of a given discriminant;129
10.8;6.8 Reduced forms in an equivalence class;131
10.9;6.9 Enumeration of the reduced forms in an equivalence class;137
10.10;6.10 Cycles of reduced forms;138
10.11;6.11 Deciding equivalence;142
10.12;6.12 The automorphism group;143
10.13;6.13 Complexity;145
10.14;6.14 Ambiguous cycles;147
10.15;6.15 Solution of the representation problem;149
10.16;6.16 Solving the minimum problem;150
10.17;6.17 Class number;151
10.18;6.18 Exercises;152
10.19;Chapter references and further reading;153
11;7 Multiplicative Lattices;154
11.1;7.1 Lattice operations;154
11.2;7.2 Quadratic orders;155
11.3;7.3 Multiplicative lattices;158
11.4;7.4 Composition of forms;164
11.5;7.5 Exercises;167
11.6;Chapter references and further reading;167
12;8 Quadratic Number Fields;168
12.1;8.1 Basics;168
12.2;8.2 Algebraic integers;170
12.3;8.3 Units of orders;171
12.4;8.4 Ideals of orders;174
12.5;8.5 Factorization of ideals;179
12.6;8.6 Unique factorization into prime ideals;182
12.7;8.7 Exercises;187
13;9 Class Groups;188
13.1;9.1 Ideal classes;188
13.2;9.2 Ambiguous ideals and classes;193
13.3;9.3 Fundamentals on class groups;195
13.4;9.4 Computing in finite Abelian groups;203
13.5;9.5 Generating systems;206
13.6;9.6 Computing a generating system in time |.|1/2+o(1);207
13.7;9.7 Computing the structure of a finite Abelian group;212
13.8;9.8 Exercises;225
13.9;Chapter references and further reading;226
14;10 Infrastructure;228
14.1;10.1 Geometry of reduction;228
14.2;10.2 A Terr algorithm;233
14.3;10.3 Further applications;241
14.4;10.4 Exercises;242
14.5;Chapter references and further reading;243
15;11 Subexponential Algorithms;244
15.1;11.1 The function Lx[ a, b];244
15.2;11.2 Preliminaries;245
15.3;11.3 The factor base;246
15.4;11.4 The imaginary quadratic case;248
15.5;11.5 The real quadratic case;259
15.6;11.6 Practice;278
15.7;11.7 Exercises;279
15.8;Chapter references and further reading;280
16;12 Cryptographic Applications;283
16.1;12.1 Problems;284
16.2;12.2 Cryptographic algorithms in imaginary-quadratic orders;287
16.3;12.3 Cryptographic algorithms in real-quadratic orders;290
16.4;12.4 Open Problems;292
16.5;12.5 Exercises;293
16.6;Chapter references and further reading;293
17;A Appendix;298
17.1;A.1 Vectors and matrices;298
17.2;A.2 Action of groups on sets;299
17.3;A.3 The lemma of Gauss;299
17.4;A.4 Lattices;300
17.5;A.5 Linear algebra over;302
17.6;A.6 Exercises;312
17.7;Chapter references and further reading;312
18;Bibliography;314
18.1;Books;314
18.2;Surveys;314
18.3;Other Referenced Works;315
19;Index;324