You are here

Binary Quadratic Forms: An Algorithmic Approach

Johannes Buchmann and Ulrich Vollmer
Springer Verlag
Publication Date: 
Number of Pages: 
Algorithms and Computation in Mathematics 20
[Reviewed by
Allen Stenger
, on

This book is an uneasy combination of two things: (1) a very abstract, although historical, mathematical development of quadratic forms; (2) an analysis of several algorithms for computing interesting things about quadratic forms, concentrating on the structure of the class groups.

A binary quadratic form is a function ax2 + bxy + cy2 of two integer variables x, y where a, b, c are integer constants. Historically the key question is whether a particular form represents a particular number n, in other words, whether there are integers x, y with n = ax2 + bxy + cy2. For example, one might want to know if a particular number can be represented as the sum of two squares, x2 + y2, or to characterize the numbers that this form can represent. This representation question led to studying the collection of all quadratic forms with a given discriminant, and then to equivalence classes of forms, composition of forms, and class groups. The theory was later recast in terms of ideals in number fields, with quadratic forms as an application.

I found the treatment in this book very opaque, primarily I think because of the large amount of symbolism and abstract algebra terminology used. The book's Introduction claims that "only basic mathematical knowledge is required" (p. 2). This is a peculiar claim for a book that uses (without definition) such terms as "gamma-orbit" (p. 25) and "injective field-homomorphism" (p. 57).

The algorithmic sections of the book are generally clearly-written, and the analysis focuses on estimating the running times. The main weakness is that only one algorithm is given for each task, so there's no comparison of different methods. The book also never really explains why running times are important in quadratic forms, but hints that it has to do with cryptography.

Overall I am not very happy with this book. The mathematical theory in this book is classical, going back to Gauss, Dirichlet, Kummer, and Dedekind, although unfortunately the book does not give this history. Only about the last quarter of the book deals with algorithms, and despite the subtitle, the approach in the rest of the book is not algorithmic.

For the mathematical portions I think a much better book is Harvey Cohn's "Advanced Number Theory" (Wiley, 1962, reprinted by Dover). Cohn's book focuses on ideal theory, but with a very strong emphasis on quadratic fields, and it develops quadratic form theory as an application.

Allen Stenger is a math hobbyist, library propagandist, and retired computer programmer. He volunteers in his spare time at , a math help site that fosters inquiry learning. His mathematical interests are number theory and classical analysis.

1 Binary Quadratic Forms

2 Equivalence of Forms

3 Constructing Forms

4 Forms, Bases, Points, and Lattices

5 Reduction of Positive Definite Forms

6 Reduction of Indefinite Forms

7 Multiplicative Lattices

8 Quadratic Number Fields

9 Class Groups

10 Infrastructure

11 Subexponential Algorithms

12 Cryptographic Applications