Advanced Search

La composition de Gauss donne une structure de groupe aux orbites de formes quadratiques binaires entières de discriminant $D$, sous l’action de ${\mathrm{SL}}_2$ par changement de variable, essentiellement le groupe des classes de l’ordre quadratique de discriminant $D$. Les domaines fondamentaux associés permettent calculs explicites et évaluation d’ordres moyens. Je présenterai les lois de composition supérieures découvertes par M. Bhargava à partir de la classification des espaces vectoriels préhomogènes réguliers,...

We describe practical algorithms from computational algebraic number theory, with applications to class field theory. These include basic arithmetic, approximation and uniformizers, discrete logarithms and computation of class fields. All algorithms have been implemented in the system.

Considérons le cardinal $h_3^{*}\left(\Delta \right)$ de l’ensemble des racines cubiques de l’unité dans le groupe des classes de $\mathbb{Q}\left(\sqrt{\Delta }\right)$, où $\Delta$ est un discriminant fondamental. Un résultat de Davenport et Heilbronn calcule la valeur moyenne de ces nombres quand $\Delta$ varie. On obtient ici géométriquement une borne explicite pour le reste, avec la possibilité supplémentaire de restreindre les $\Delta$ à des progressions arithmétiques. Des techniques de crible permettent alors d’évaluer la 3-partie des $\mathbb{Q}\left(\sqrt{\pm P_k}\right)$, où $P_k$ est pseudo-premier d’ordre $k$. On...

La théorie algébrique des nombres est née du désir de résoudre certaines équations diophantiennes en nombres entiers (typiquement, l’équation de Fermat). Elle introduit et étudie des structures algébriques associées aux extensions algébriques de $\mathbb{Q}$ ou de ${𝔽}_q\left(t\right)$, en y retrouvant la trace des propriétés des entiers ordinaires, par exemple la factorisation unique en produit de nombres premiers, sous une forme affaiblie. Je motiverai l’introduction des objets correspondants (anneaux d’entiers, groupes de...

We describe a simple procedure to find Aurifeuillian factors of values of cyclotomic polynomials ${\Phi }_d\left(a\right)$ for integers $a$ and $d\>0$. Assuming a suitable Riemann Hypothesis, the algorithm runs in deterministic time $\tilde{O}\left(d^{2}L\right)$, using $O\left(dL\right)$ space, where $L≔log(\left|a\right|+1)$.

We prove that van Hoeij’s original algorithm to factor univariate polynomials over the rationals runs in polynomial time, as well as natural variants. In particular, our approach also yields polynomial time complexity results for bivariate polynomials over a finite field.