Thèse de doctorat : Mathématiques pures : Metz : 2007. / Thèse soutenue sur ensemble de travaux. Bibliogr. p. [63]-64.

Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique / In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic

Les minorations de combinaison linéaire, à coefficients entiers, de logarithmes de nombres algébriques constituent un outil important dans la résolution effective de certaines classes d'équations diophantiennes. Le cas de deux logarithmes est à cet égard particulièrement utile. Nous utilisons ici, pour l'obtention de ces minorations, la méthode dite de Schneider avec multiplicité. La démonstration repose sur l'utilisation des déterminants d'interpolation et d'un lemme de zéros approprié à ce cadre. Le lemme de zéros exploité ici, dont la preuve reprend la construction originelle de D.W. Masser, s'avère dans notre cas plus efficace que les résultats généraux précédemment employés. Nous utilisons ensuite une méthode standard pour encadrer un déterminant non nul, afin d'obtenir une inégalité fondamentale faisant intervenir de nombreux paramètres arbitraires. Nous déduisons de cette dernière une liste de minorations totalement explicites de formes linéaires de logarithmes.

L'objectif de cette thèse est d'obtenir une démonstration effective d'un résultat de Cohen, Shiga et Wolfart, généralisant aux espaces de Siegel $\mathfrak{H}_{g}$ de degré $g$ quelconque le théorème classique de Schneider sur l'invariant modulaire $j(\tau)$. Un premier pas dans cette direction consiste, étant donnée une variété abélienne $\mathcal{A}$ définie sur $\overline{\mathbb{Q}}$ et paramétrée par un point $\tau$ de l'espace de Siegel, à minorer $|||\tau-\beta|||$ où $\beta$ est un point algébrique de l'espace de Siegel, en fonction des données géométriques du problème. C'est ce qui est réalisé ici, en affinant des outils d'indépendance linéaire de logarithmes de la méthode de Gel'fond-Baker.

Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné n'est pas nécessairement considéré comme disqualifié, et il convient d'actualiser avec soin l'état de l'art de la cryptanalyse. Les travaux de ce mémoire s'inscrivent dans cette optique. Nous décrivons en particulier comment nous avons atteint un record de calculs de logarithmes discrets: \GFn(607).<br /><br />Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépasse<br />le simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité.<br /><br />On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur \GF p.<br /><br />Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène.

Cette thèse s'inscrit dans la lignée des travaux relatifs à la théorie des formes linéaires de logarithmes. Elle comporte deux parties ainsi que trois annexes. Dans la première partie, nous nous intéressons au cas général d'un groupe algébrique commutatif quelconque, défini sur la clôture algébrique de Q. Étant donné un tel groupe G, un hyperplan W de l'espace tangent à l'origine de G et $u$ un point complexe de cet espace tangent, dont l'image par l'exponentielle du groupe de Lie complexe G(C) est algébrique, nous obtenons une minoration de la distance de u à W, qui améliore les résultats connus auparavant et qui, en particulier, est optimale en la hauteur de l'hyperplan W. La démonstration repose sur la méthode de Baker ainsi que sur un nouvel argument de nature arithmétique (procédé de changement de variables de Chudnovsky) qui nous permet d'évaluer précisément les normes ultramétriques des nombres algébriques construits au cours de la preuve. Dans la seconde partie, nous étudions plus en détail le < non-homogène>> (dans lequel le groupe G est le produit direct du groupe $\mathbb{G}_{\mathrm{a}}$ et d'une variété abélienne) et nous établissons une nouvelle mesure, comparable à celle donnée dans la première partie mais totalement explicite en les invariants liés à la variété abélienne. La particularité de cette seconde partie est de mettre en oeuvre, pour la première fois dans ce contexte, la méthode des pentes de J.-B. Bost et certains résultats de géométrie d'Arakelov qui lui sont attachés.

L'objet général de ce travail est l'étude de la convergence des méthodes classiques<br />de calcul approché des racines d'un polynôme à coefficients complexes. Les méthodes<br />considérées sont celles de Bernoulli et de Graeffe-Dandelin. On montre que ces <br />questions de convergence sont liées à des problèmes diophantiens et que les<br />théorèmes d'aapproximation de Dirichlet et surtout la méthode de Baker fournissent<br />des résultats de convergence nouveaux qui s'appliquent aux polynômes à coefficients<br />entiers. De nombreux exemples calculés en MAPLE, y sont présentés et analysés.

Nous étudions ici deux problèmes diophantiens distincts. Le premier concerne les points entiers sur les courbes modulaires associées au normalisateur de sous-groupe de Cartan non déployé. Le deuxième concerne la recherche de point de multiplication complexe sur les droites. Dans les deux cas la méthode de résolution est algorithmique. On utilise la méthode de Baker sur les formes linéaires en logarithmes ainsi que des méthodes de réduction effectives. En particulier cette méthode permet d’obtenir les points entiers sur la courbe associée au normalisateur de sous-groupe de Cartan non déployé pour les niveaux compris entre 7 et 71. / We study here two diophantine problem. The first one deals with integral point on modular curves associated to normalizer of non-split Cartan subgroup. The second one is about finding singular moduli on straight line. In both cases, we solve theproblem in an algorithmic way. We use Baker’s method on linear form in logarithm and some effective technical of reduction. In particular this method gives integral points on the curve associated to normalizer of non-split Cartan subgroup for level between 7 and 71.

Dans cette thèse, nous appliquons des outils issus de la théorie d’Arakelov à l’étude de problèmes de géométrie diophantienne. Une notion centrale dans notre étude est la théorie des pentes des fibrés vectoriels hermitiens, introduite par Bost dans les années 90. Nous travaillons plus précisément avec sa généralisation dans le cadre adélique, inspirée par Zhang et développée par Gaudron. Ce mémoire s’articule autour de deux axes principaux. Le premier consiste en l’étude d’un remarquable théorème de géométrie diophantienne dû à Faltings etWüstholz, qui généralise le théorème du sous-espace de Schmidt. Nous commencerons par retranscrire la démonstration de Faltings et Wüstholz dans le langage de la théorie des pentes. Dans un second temps, nous établirons des variantes effectives de ce théorème, que nous appliquerons pour démontrer une généralisation effective du théorème de Liouville valable pour les points fermés d’une variété projective fixée. Ce résultat fournit en particulier une majoration explicite de la hauteur des points satisfaisant une inégalité analogue à celle du théorème de Liouville classique. Dans la seconde partie de cette thèse, nous établirons de nouvelles mesures d’indépendance linéaire de logarithmes dans un groupe algébrique commutatif, dans le cas dit rationnel.Notre approche utilise les arguments de la méthode de Baker revisitée par Philippon et Waldschmidt, combinés avec des outils de la théorie des pentes. Nous y intégrons un nouvel argument, inspiré par des travaux antérieurs de Bertrand et Philippon, nous permettant de contourner les difficultés introduites par le cas périodique. Cette approche évite le recours à une extrapolation sur les dérivations à la manière de Philippon et Waldschmidt. Nous parvenons ainsi à supprimer une hypothèse technique contraignante dans plusieurs théorèmes de Gaudron, tout en précisant les mesures obtenues. / In this thesis, we study diophantine geometry problems on projective varieties and commutative algebraic groups, by means of tools from Arakelov theory. A central notion in this work is the slope theory for hermitian vector bundles, introduced by Bost in the 1990s. More precisely, we work with its generalization in an adelic setting, inspired by Zhang and developed by Gaudron. This dissertation contains two major lines. The first one is devoted to the study of a remarkable theorem due to Faltings and Wüstholz, which generalizes Schmidt’s subspace theorem. We first reformulate the proof of Faltings and Wüstholz using the formalism of adelic vector bundles and the adelic slope method. We then establish some effective variants of the theorem, and we deduce an effective generalization of Liouville’s theorem for closed points on a projective variety defined over a number field. In particular, we give an explicit upper bound for the height of the points satisying a Liouville-type inequality. In the second part, we establish new measures of linear independence of logarithms over a commutative algebraic group. We focus our study on the rational case. Our approach combines Baker’s method (revisited by Philippon and Waldschmidt) with arguments from the slope theory. More importantly, we introduce a new argument to deal with the periodic case, inspired by previous works of Bertrand and Philippon. This method does not require the use of an extrapolation on derivations in the sense of Philippon-Waldschmidt. In this way, we are able to remove an important hypothesis in several theorems of Gaudron establishing lower bounds for linear forms in logarithms.

Dans cette thèse, on étudie deux types d'équations diophantiennes. Une première partie de notre étude porte sur la résolution des équations dites de Ramanujan-Nagell $Cx^2+b^{2m}D=y^n$. Une deuxième partie porte sur les équations dites de Ngell-Ljunggren\\ $\frac{x^p+y^p}{x+y}=p^ez^q$ incluant le cas diagonal $p=q$. Les nouveaux résultats obtenus seront appliqués aux équations de la forme $x^p+y^p=Bz^q$. L'équation de Catalan-Fermat (cas $B=1$) fera l'objet d'un traitement à part.