Binary Quadratic Forms (eBook)

An Algorithmic Approach

Johannes Buchmann, Ulrich Vollmer (Autoren)

eBook Download: PDF

2007 | 2007
XIV, 318 Seiten
Springer Berlin (Verlag)
978-3-540-46368-9 (ISBN)

Infos

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.

Buchmann: Professor of Computer Science and Mathematics
   special areas number theory, computer algebra, cryptography
   associate editor Journal of Cryptology
          Leibniz Award of the Deutsche Forschungsgemeinschaft
   Author of 'Introduction to cryptography' UTM, translated into seven languages
          Member of Berlin-Brandenburg Academy of Sciences
          Member of Academy of Sciences and Literature, Mainz

Vollmer: Thesis and several articles on algorithms for Class Group and Regulator computation in quadratic fields.

Inhalt

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 < 0
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 reduced forms 106
5.8 Deciding equivalence 108
5.9 Solving the representation problem 109
5.10 Solving the minimum problem 110
5.11 Class number 110
5.12 Reduction of semidefinite forms 113
5.13 Geometry of reduction 114
5.14 The densest two-dimensional lattice packing 115
5.15 Exercises 116
Chapter references and further reading 117
6 Reduction of Indefinite Forms 118
6.1 Normal forms 118
6.2 Reduced forms 120
6.3 Another characterization of reduced forms 121
6.4 The reduction algorithm 123
6.5 The number of reduction steps 124
6.6 Complexity of reducing integral forms 126
6.7 Enumerating integral reduced forms of a given discriminant 129
6.8 Reduced forms in an equivalence class 131
6.9 Enumeration of the reduced forms in an equivalence class 137
6.10 Cycles of reduced forms 138
6.11 Deciding equivalence 142
6.12 The automorphism group 143
6.13 Complexity 145
6.14 Ambiguous cycles 147
6.15 Solution of the representation problem 149
6.16 Solving the minimum problem 150
6.17 Class number 151
6.18 Exercises 152
Chapter references and further reading 153
7 Multiplicative Lattices 154
7.1 Lattice operations 154
7.2 Quadratic orders 155
7.3 Multiplicative lattices 158
7.4 Composition of forms 164
7.5 Exercises 167
Chapter references and further reading 167
8 Quadratic Number Fields 168
8.1 Basics 168
8.2 Algebraic integers 170
8.3 Units of orders 171
8.4 Ideals of orders 174
8.5 Factorization of ideals 179
8.6 Unique factorization into prime ideals 182
8.7 Exercises 187
9 Class Groups 188
9.1 Ideal classes 188
9.2 Ambiguous ideals and classes 193
9.3 Fundamentals on class groups 195
9.4 Computing in finite Abelian groups 203
9.5 Generating systems 206
9.6 Computing a generating system in time |.|1/2+o(1) 207
9.7 Computing the structure of a finite Abelian group 212
9.8 Exercises 225
Chapter references and further reading 226
10 Infrastructure 228
10.1 Geometry of reduction 228
10.2 A Terr algorithm 233
10.3 Further applications 241
10.4 Exercises 242
Chapter references and further reading 243
11 Subexponential Algorithms 244
11.1 The function Lx[ a, b] 244
11.2 Preliminaries 245
11.3 The factor base 246
11.4 The imaginary quadratic case 248
11.5 The real quadratic case 259
11.6 Practice 278
11.7 Exercises 279
Chapter references and further reading 280
12 Cryptographic Applications 283
12.1 Problems 284
12.2 Cryptographic algorithms in imaginary-quadratic orders 287
12.3 Cryptographic algorithms in real-quadratic orders 290
12.4 Open Problems 292
12.5 Exercises 293
Chapter references and further reading 293
A Appendix 298
A.1 Vectors and matrices 298
A.2 Action of groups on sets 299
A.3 The lemma of Gauss 299
A.4 Lattices 300
A.5 Linear algebra over 302
A.6 Exercises 312
Chapter references and further reading 312
Bibliography 314
Books 314
Surveys 314
Other Referenced Works 315
Index 324

Produkt-Details

• Erscheint lt. Verlag: 22.6.2007
• Reihe/Serie: Algorithms and Computation in Mathematics
• Reihe/Serie: Algorithms and Computation in Mathematics
• Zusatzinfo: XIV, 318 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• Themenwelt: Mathematik / Informatik ► Mathematik ► Statistik
• Themenwelt: Technik
• Schlagworte: Algebra • algebraic number theory • Algorithmic Number Theory • algorithms • cryptography • Number Theory • quadratic forms
• ISBN-10: 3-540-46368-2 / 3540463682
• ISBN-13: 978-3-540-46368-9 / 9783540463689