Project Topics
Get Complete Project Material File(s) Now! »
Gauss and the equivalence classes of binary quadratic forms
Gauss was the first to compute the class number of quadratic number fields. However, that is not how he approached the problem: he was interested in binary quadratic forms. We make use of the Proposition 1.2.12 for the representation of quadratics number fields as K ÆQ( p D), where D is the fundamental discriminant of the quadratic field. Definition 2.1.1 ([Coh93, Definition 5.2.3]). A binary quadratic form f is a function f (x, y) Æ ax2Åbx y Åc y2 where a, b and c are integers, which is denoted more briefly by (a,b,c). We say that f is primitive if gcd(a,b,c) Æ 1. If f and g are two quadratic forms, we say that f and g are equivalent if there exists a matrix M Æ ¡ mi , j ¢ 2 SL2(Z)—i.e., an integral matrix of determinant equal to 1—such that g (x, y) Æ f (m1,1x Åm1,2y,m2,1x Åm2,2y).
This definition implies that being equivalent is an equivalence relation which preserves the discriminant D Æ b2 ¡4ac of the quadratic form. In addition, if D is a fundamental discriminant, then any quadratic formof discriminant D Æ b2 ¡4ac is primitive.
Before explaining how Gauss worked with these equivalence classes, we emphasize the link between ideals—and so class groups—in quadratic number fields and binary quadratic forms. Let D be a fundamental discriminant and let QFD denote the set of equivalence classes of binary quadratic forms of discriminant equal to D, that is QFD Æ © (a,b,c) j b2 ¡4ac ÆD ª± SL2(Z) .
Shanks’ Baby-Step–Giant-Step method
The problem of computing class groups was addressed for the first time by Shanks in 1969. By computing class groups, we mean that we are interested in the group structure, and not only in its cardinality. Indeed, until now, all the described methods only provide the class number, but nothing about the structure.
In [Sha69], Shanks introduces a new method for deriving the class group structure of an imaginary quadratic number field in time O ¡ jDj1/4Å » ¢ for any » È 0. This is the first occurrence in the literature of the now widespread Baby-Step–Giant-Step method, that has applications in various areas of number theory. His work brought two refinements, because it enables to obtain more information on the class group, and in less time.
The primary description is again for imaginary quadratic number fields. Let D Ç 0 be a fundamental discriminant. From the Class Number Formula (Equation (1.18)), we obtain a good enough approximation ˜h of the class number hK by computing a partial sum of the Dirichlet function associated to D. Shanks claimed that 217 terms generally suffice for having a relative error below 10¡3. For every small prime p such that the Legendre symbol satisfies ³ Dp ´ Æ 1, we set bp as a square root of D mod p that has the same parity with D, i.e., D ´ bp mod 2. Denoting by cp the integer such that b2p ¡D Æ 4pcp, we thus obtain a quadratic form fp Æ ¡ p,bp,cp.
Subexponential complexity, using index calculus method
The current best algorithms for class group computation rely on the index calculus method. It is also the case for factoring integers or computing discrete logarithms in finite fields. A brief summary is as follows:
1. Fix a factor base composed of small elements and that is large enough to generate all elements of the group.
2. Collect relations between those small elements, corresponding to linear equations.
3. Deduce the result sought performing linear algebra on the system built from the relations.
We givemore details about the different steps in case of class group computation. Afterwards, every contribution is examined with respect to this global strategy.
The factor base. We define the factor base B as the set of all prime ideals in OK that have a normbounded by a constant B. This boundmust be chosen such that the factor base generates the whole class group. As recalled in Section 2.2, Bach has shown that assuming ERH, the classes of ideals with a representative of normless than 12 ¡ logj¢Kj ¢2 suffice to generate the class group. However, as the ability to find relations in the collection step increases with the size of the factor base, we fix B Æ Łj¢Kj(¯,cb).
First example: imaginary quadratic number fields, byHafner andMcCurley
Again, the initial subexponential result was obtained for imaginary quadratic number fields, by Hafner and McCurley. As the prior results, they did not use ideals, but binary quadratic forms. We recall that in those fields, the regulator is 1, because the rank of the unit group is zero. Note that the results of Bach stated in Section 2.2 were not released at that time. However, this is not a problem because for quadratic number fields, the analysis was done by Lenstra and Schoof.
The factor base B is fixed as the set of the forms fp Æ (p,bp,cp) — as defined in Equation (2.2) — for all primes p · B Æ ŁjDj ³ 1 2 , p 2 ´ such that ³ Dp ´ Æ ¡1. Thanks to Lemma 2.1.8, we know that this set of forms is large enough to generate the whole class group. In fact, it is much larger than required to generate the class group: as we want to decompose forms over this set efficiently, we need such a size. The construction of the factor base is naive: it relies on an enumeration of all the primes below the bound. It follows from the Chebotarev’s density theorem [Che26] combined with Theorem 1.5.11 that the number of such primes can be expected to be B 2logB Æ LjDj ³ 1 2 ,4 ´. At the same time, we can use the enumeration of primes to find an approximation of hK. Using the techniques of Schoof [Sch82], we know that there exists a constant c1 such that computing the partial sumof the L-function up to c1 ¡ logjDj ¢2 suffices to find an approximation ˜h such that 3 4 Ç 22 7 hK b p Dc˜h Ç 3 2 .
Buchmann extension to all number fields
In [Buc90], Buchmann extends the idea of Hafner andMcCurley for arbitrary-degree number fields. No more binary quadratic forms are involved in the description, only ideals.
The way to derive the relations is similar to the collection performed for quadratic number fields, except that we do not require a diagonally-dominated matrix. Indeed, we build random ideals as power-products of elements of the factor base: A Æ Q pvi i . Then we find a reduced ideal A0 in the class of A. This reduction hinges on finding a shortest non-zero vector in A which runs in polynomial time (see Section 1.1.3)—it is exponential in the degree but the degree is fixed. Eventually if A0 splits over the factor base B, we have A0 Æ Q p v0 i i so that A ¢ (A0)¡1 Æ NY iÆ1 p vi¡v0.
Release the degree, by Biasse and Fieker
In [BF14], Biasse and Fieker modify the reduction algorithm: they use BKZ-reductions, offering a trade-off between the time spent in the reduction and the approximation factor of the short vectors. Thus they reach a complexity which allows both the degree and the discriminant of the field to tend to infinity. In addition, they replace trial divisions by more efficient methods such as ECM for the smoothness tests (see Section 1.4.4). That allows to reduce the complexity of the relation collection by a factor of order N.
For the linear algebra phase, they provide a deep study on the precision in [BF14, Section 4]. Based on the HNF computation recalled in Theorem 1.1.3, they show that assuming we have a full-rankmatrix of relations, we can derive the class group structure and an approximation of the regulator—and so verify our results—in time O(N!Å1) where N is the size of the factor base. Precision questions are handled using a p-adic approach, whereas another method using rational approximations is developed in [Bia14a]. Finally, they also give a way to provide a set of fundamental units, in compact representation.
We make use of their analysis on precision in the sequel. We do not give a detailed description of the relation collection here as we recall and improve it in Chapter 4. Biasse and Fieker achieved a Lj¢Kj ¡23 Å » ¢ complexity in the general case and Lj¢Kj ¡12 ¢ when the extension degree n satisfies the inequality n · (logj¢Kj)3/4¡ ».
We leave aside for the moment their q-descent strategy, recalled in Chapter 3. It consists in an improvement that allows to reduce the complexity to Lj¢Kj(a) with 13 · a · 12 when the number field is defined by a polynomial having small height [BF14, Theorem6.2].
Table of contents :
Abstract
(French) Résumé
(French) Introduction
1 Motivation
2 Organisation de la thèse et résultats
Introduction
1 Motivation
2 Contributions & Organization
I Preliminaries
1 Algebraic Number Theory Tools
1.1 Linear algebra & Lattices
1.2 Number fields & Polynomials
1.3 Orders & Ideals
1.4 Norms & Smoothness
1.5 Ideal classes & Units
2 Previous work on class group computations and related problems
2.1 Exponential strategies for quadratic number fields
2.2 Class group generation
2.3 Subexponential complexity, using index calculus method
2.4 Algorithms related to number fields
II Reducing the complexity of Class Group Computation
3 Reduction of the defining polynomial
3.1 Motivations and link with class group computation
3.2 An optimal algorithm for NF defining polynomial reduction
3.3 Complexity analysis
3.4 Application to class group computation
4 Refinements for complexities appearing in the literature for the general case
4.1 The classification defined by classes D is sufficient
4.2 The relation collection
4.3 Complexity analyses
4.4 Using HNF to get an even smaller complexity
5 Reducing the complexity using good defining polynomials
5.1 Motivation
5.2 Deriving relations by sieving
5.3 Complexity analyses
5.4 Conclusion on sieving strategy
5.5 Application to Principal Ideal Problem
III Applications to Cryptology
6 PIP solution in cyclotomic fields and cryptanalysis of an FHE scheme
6.1 Situation of the problem and cryptosystems that rely on SPIP
6.2 Solving the PIP or how to performa full key recovery?
6.3 Description of the algorithm
6.4 Complexity analysis
6.5 Implementation results
Bibliography
