Approximatting rings of integers in number fields

Buchmann, J. A. ; Lenstra, H. W. 

Journal de théorie des nombres de Bordeaux, Tome 6 (1994) no. 2, pp. 221-260

Abstract (VO)

In this paper we study the algorithmic problem of finding the ring of integers of a given algebraic number field. In practice, this problem is often considered to be well-solved, but theoretical results indicate that it is intractable for number fields that are defined by equations with very large coefficients. Such fields occur in the number field sieve algorithm for factoring integers. Applying a variant of a standard algorithm for finding rings of integers, one finds a subring of the number field that one may view as the “best guess” one has for the ring of integers. This best guess is probably often correct. Our main concern is what can be proved about this subring. We show that it has a particularly transparent local structure, which is reminiscent of the structure of tamely ramified extensions of local fields. A major portion of the paper is devoted to the study of rings that are “tame” in our more general sense. As a byproduct, we prove complexity results that elaborate upon a result of Chistov. The paper also includes a section that discusses polynomial time algorithms related to finitely generated abelian groups.

Résumé

Nous étudions dans cet article le problème algorithmique de la détermination de l'anneau des entiers d'un corps de nombres algébriques donné. En pratique, ce problème est souvent considéré comme résolu mais des résultats théoriques montrent que sa résolution ne peut être menée à terme lorsque le corps étudié est défini par les équations dont les coefficients sont très gros. Or de tels corps apparaissent dans l'algorithme du crible algébrique utilisé pour factoriser les entiers naturels. En appliquant une variante d'un algorithme standard donnant l'anneau des entiers, on obtient un sous-anneau du corps de nombres qui peut être regardé comme le meilleur candidat possible pour l'anneau des entiers. Ce meilleur candidat est probablement souvent le bon. Notre propos est d'exposer ce qui peut être prouvé sur ce sous-anneau. Nous montrons que sa structure locale est transparente et rappelle celle des extensions modérément ramifiées de corps locaux. La plus grande partie de cet article est consacrée à l'étude des anneaux qui sont «modérés» en un sens plus général que celui habituel. Chemin faisant nous établissons des résultats de complexité qui prolongent un théorème de Chistov. L'article inclut également une section qui discute des algorithmes en temps polynomial pour les groupes abéliens de type fini.

Détail

Keywords: maximal order, tame extensions, algorithm