Catálogo de publicaciones - libros

This book deals with algorithmic problems concerning binary quadratic forms with integer coe.cients the mathematical 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.

In this book we study

In Example 1.1.7, we were able to find the minimum of the form f using a transformation of variables. In this section, we generalize this approach. We introduce transformations that do not change the minimum of a form. Also, the numbers that can be represented by f remain the same. Those transformations will enable us to simplify the representation problem and the minimum problem.

In Chapter 2 we have explained a strategy for finding primitive representations of an integer by an integral form . In this strategy, the first step is to determine all integral forms () of discriminant Δ(). In this chapter, we explain how those forms can be found.

In this chapter we explain the correspondence between binary quadratic forms with real coefficients and points, R-bases, and lattices in the real plane. This correspondence will enable us to use quadratic number fields and the geometry of numbers in the theory of forms.

In this chapter we solve the problems of deciding equivalence and finding the minimum of forms of negative discriminant. First we show, that it suffices to solve those problems for positive definite forms. Then we solve the problems for positive definite forms using reduction theory.

In this chapter we explain reduction theory for indefinite forms which is quite different from reduction theory for positive definite forms. Reduced indefinite forms can only be used to decide equivalence of integral indefinite forms and the decision algorithm is much less efficient than in the positive definite case since reduction is no longer unique. Reduction theory also solves the minimum problem for integral indefinite forms.

Let ε {±1}, , and . In this chapter we define the product of lattices in A and characterize the two-dimensional lattices in A whose product is a lattice. By a form we mean an irrational form with real coefficients and non-zero discriminant. By an we mean an integer Δ with Δ ≡ 0, 1 mod 4 which is not a square in ℤ.

We have seen in Chapter 7 that the set of all lattices whose ring of multipliers is contained in a fixed maximal order is a monoid with respect to multiplication of lattices. In this chapter we study the algebraic structure of this monoid more closely. We also discuss the properties of the fields of fractions of quadratic orders.

Let Δ be a quadratic discriminant, that is, Δ is an integer that is not a square and Δ ≡ 0, 1 (mod 4). Let be the quadratic order of discriminant Δ and let be the field of fractions of . In this chapter we show that the set of equivalence classes of integral primitive forms of discriminant Δ and the set of equivalence classes of invertible -ideals are finite Abelian groups, and we will discuss computational problems concerning those groups such as extracting roots, computing element orders and discrete logarithms, and determining the group structure.