Séminaire de Théorie des Nombres de Montpellier :

Le 29 mai 2006 à 14:00 - salle 431

Présentée par Williams Hugh C. - University of Calgary

« How to Determine Whether a Given Ideal is Principal »

Let $D$ be a positive nonsquare integer and let b be any ideal in the real quadratic field $\mathbb{Q}(\sqrt{D})$. If we are given a $\mathbb{Z}$-basis of b, it is an old problem to determine whether or not b is principal. The best unconditional result on this is that this can be done in time complexity $O(D^ {1/4+\epsilon})$. In order to do this, we must first evaluate the regulator R of the associated real quadratic number field $\mathbb{Q}(\sqrt{D})$. The problem of computing R can be very difficult, particularly when the field discriminant d becomes large. (Clearly, the actual value of the regulator can never be computed because it is a transcendental number; we are content with an approximate value that is within 1 of the actual value.) The best current method for computing R is Buchmann’s subexponential method. Unfortunately, the correctness for the value of R produced by this technique is dependent on the truth of a generalized Riemann hypothesis. The best unconditional algorithm (the value of R is unconditional, not the running time) for computing the regulator of a real quadratic field is Lenstra’s $O(D^{1/5+\epsilon})$ Las Vegas Algorithm. In this talk we describe a technique for rigorously verifying the regulator produced by the subexponential algorithm. This technique is of complexity $O(D^{ 1/6+\epsilon})$. Furthermore, these methods can be extended to the problem of determining rigorously for real quadratic fields of large discriminant whether or not a given ideal is principal. This can now be done by a Las Vegas algorithm of complexity $O(D^{1/6+\epsilon})$.
Lien vers le fichier de la présentation : IdealPrincipal.ppt