résumé en anglais

On utilise une version de la fameuse méthode Viro pour construire des systèmes polynomiaux avec beaucoup de solutions positives. On montre que si un polytope P entier admet une triangulation régulière unimodulaire et bipartite, alors il existe un système polynomial dont toutes les équations ont P comme polytope de Newton et dont toutes les solutions dans le tore complexe sont en fait contenues dans l'orthant positif (système maximalement positif). On exhibe plusieurs familles de polytopes connues admettant de telles triangulations. Tous ces nouveaux exemples vérifient une conjecture faite par l'orateur sur les systèmes maximalement positifs. Si le temps le permet, on discutera aussi d'une construction de systèmes avec beaucoup de solutions positives utilisant une triangulation du polytope cyclique. C'est un travail en commun avec Pierre-Jean Spaenlehauer, INRIA Nancy.

résumé en anglais

résumé en anglais

La méthode de Chudnovsky & Chudnovsky fournit, aujourd'hui, les meilleures bornes de complexité bilinéaire pour la multiplication dans les grandes extensions de corps finis. Elle repose sur l'interpolation sur les courbes algébriques. Lorsqu'on fixe une courbe, on peut espérer construire des algorithmes qui atteignent au mieux une certaine complexité (avec des exceptions). Il semble qu'on arrive souvent à atteindre ce seuil. Nous illustrerons une méthode explicite pour y arriver.

résumé en anglais

Nous nous proposons de décrire nos travaux de thèse sur le calcul des polynômes modulaires en genre 2. Ces polynômes dépendent des invariants d'Igusa, qui sont une généralisation de la fonction j dans le genre 1, et permettent d'obtenir toutes les variétés abéliennes isogènes à une variété abélienne donnée. Dans un premier temps, nous reviendrons sur cette notion de polynôme en genre 1 et 2 et discuterons de leur calcul par une approche du type évaluation/interpolation. Dans un second temps, nous expliquerons comment généraliser ces polynômes à d'autres invariants et décrirons certaines de leurs propriétés, notamment le lien entre le dénominateur d'un coefficient du polynôme modulaire et les surfaces de Humbert.

résumé en anglais

résumé en anglais

résumé en anglais

résumé en anglais

L'idée d'utiliser la difficulté du décodage d'un code aléatoire comme primitive de cryptographie à clé publique à été introduite par McEliece en 1978. Le schéma de McEliece présente l'intérêt de résister aux attaques d'un hypothétique ordinateur quantique. De plus, ses vitesses de chiffrement et de déchiffrement sont bien meilleures que celles de schémas basés sur les problèmes de factorisation ou du logarithme discret. En contrepartie il présente l'inconvénient de nécessiter de très grandes tailles de clés.
La proposition originelle de McEliece repose sur l'utilisation des codes de Goppa binaires. Par la suite, d'autres familles de codes ont été proposées pour ce schéma de chiffrement dans le but de réduire la taille des clés. La principale exigence est d'avoir un algorithme de décodage rapide et corrigeant beaucoup d'erreurs. Par exemple (et cette liste est loin d'être exhaustive), les codes de Reed-Solomon généralisés, leur sous-codes et les codes Reed-Müller binaires. Tous ces systèmes sont soumis à des attaques en temps polynomial ou sous-exponentiel.
Les codes géométriques sont des codes d'évaluation de fonctions rationnelles sur des courbes algébriques. Leur bonne distance minimale ainsi que l'existence d'algorithmes de décodage efficace en fait d'intéressants candidats pour le schéma de McEliece, ce qui a motivé Janwa et Moreno à les proposer à des fins cryptographiques. Faure et Minder ont proposé une attaque structurelle de ce systèmes lorsque les codes proposés sont construit à partir de courbes de genre g < 3. Leur approche rend toutefois très difficile toute extension au cas de courbes de genre supérieur. Dans cet exposé je présenterai une attaque polynomiale du schéma de McEliece basé sur les codes géometriques.

L'évaluation d'un polynôme en une valeur peut se faire au moyen de différents schémas d'évaluation. Cet exposé présentera la bibliothèque fast_polynomial écrite en cython, interfacée pour sage et python. Cette implantation efficace d'évaluation de polynômes reprend et améliore en pratique les algorithmes rapides de type diviser pour régner. L'abstraction sous-jacente permet en outre de mêler facilement et efficacement différents schémas d'évaluation. La structure de donnée implantée maintient une faible utilisation mémoire et permet d'exploiter le parallélisme des architectures modernes. Je présenterai enfin les limitations et les améliorations possibles de la bibliothèque.

résumé en anglais

Soit B ≥ 2. Un entier n est dit B-friable si son plus grand facteur premier, noté P⁺(n) satisfait P⁺(n) ≤ B. Soit F ∈ Z[X₁, X₂] une forme binaire. Dans cet exposé, on s'intéressera à l'étude asymptotique du cardinal On établira tout d'abord des formules asymptotiques pour Ψ_F⁽¹⁾(X, B) lorsque F est de degré 3, dans une large région en (X, B). Dans un second temps, on étudiera la dépendance en F d'une telle quantité. Cette deuxième partie, directement liée à la phase de sélection polynomiale dans l'algorithme de factorisation NFS, est le fruit d'un travail en collaboration avec Razvan Barbulescu.

résumé en anglais

La sécurité des protocoles cryptographiques repose sur des problèmes difficiles et évolue en fonction des connaissances que l'on a sur ceux-ci. Cet exposé s'intéresse à l'un de ces problèmes de théorie des nombres : le problèmes du logarithme discret dans les corps finis.
L'objet de cet exposé est d'apporter un rapide aperçu des algorithmes actuels pour les corps de moyennes et grandes caractéristiques en vue d'étendre le crible spécial de corps de nombres (SNFS), qui ne portait, jusqu'ici, que sur des corps de cardinal premier. Notre SNFS s'étend sur tout le domaine d'exécution du crible de corps de nombres général (NFS), et en améliore la complexité asymptotique. Il permet le calcul de logarithmes discrets dans des corps finis dont la caractéristique admet une représentation creuse adéquate, ce qui autorise en particulier son application sur des corps finis issus de procédés de couplage.
Il s'agit d'un travail commun avec Antoine Joux.

Les applications en calcul exact, utilisent l'élimination de Gauss non seulement pour la résolution de systèmes réguliers, comme en calcul numérique, mais aussi, lorsque la matrice est singulière, pour calculer sa forme échelonnée. La structure en échelon, aussi appelée profil de rang en colonne, indique le premier sous-ensemble de vecteurs colonnes linéairement indépendants dans la matrice. Elle joue par exemple un rôle important dans le calcul de bases de Gröbner à partir de la matrice de Macaulay. Plus généralement nous définirons la matrice de profil de rang qui caractérise les profils de rangs ligne et colonne de toute sous-matrice dominante d'une matrice donnée.
La mise en oeuvre efficace de l'élimination de Gauss fait appel à de nombreuses variantes algorithmique concernant la découpe en blocs, le choix de permutation, la recherche des pivots ou l'ordonnancement des mises à jour. Nous présenterons des conditions suffisantes et le plus souvent nécessaires pour qu'un algorithme d'élimination puisse révéler les profils de rang en ligne, en colonnes ainsi que la matrice de profil de rang. En corollaire, nous présenterons deux nouveaux algorithmes, l'un récursif par découpe en quatre quadrant, l'autre itératif servant de cas de base, qui calculent une décomposition PLUQ révélant la matrice de profil de rang, de complexité sous-cubique, sensible au rang et en place.
La mise en oeuvre pour le calcul dans des petits corps finis améliore l'efficacité des implantations existantes et ouvre des perspectives nouvelles pour le parallélisme.

Lorsque l'on effectue le produit de deux éléments de F_qⁿ, on distingue deux types d'opérations élémentaires dans F_q : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire, et les opérations bilinéaires (multiplications de deux éléments de F_q qui dépendent chacun d'un des deux éléments de F_qⁿ dont on effectue le produit) comptabilisées par la complexité bilinéaire. Cette dernière notion de complexité est alors indépendante de la base de F_qⁿ sur F_q choisie.
L'algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire : il a permis d'établir que cette complexité est linéaire en le degré n de l'extension considérée, et en fournit désormais les meilleures bornes connues dans le cas d'extensions de degré grand relativement au cardinal du corps de base. On présentera donc cet algorithme ainsi que certaines de ses améliorations récentes, et on montrera comment il permet d'obtenir des bornes de complexité bilinéaire de la multiplication dans F_qⁿ sur F_q, uniformes en n.

La résolution de systèmes linéaires creux intervient dans beaucoup de domaines. Un des algorithmes les plus utilisés est celui de Wiedemann. Après un bref rappel de l'algorithme de Wiedemann par blocs, nous introduirons des nouveaux types de blocs permettant d'améliorer la complexité et d'obtenir un meilleur parallélisme. Cependant, l'opération principale est le produit matrice vecteur, nous présenterons un format de stockage de la matrice qui permet d'obtenir de bonne performance sur CPU. Finalement nous arborderons des méthodes pour réordonner les éléments non nuls afin de les concentrer.

Il existe plusieurs algorithmes pour calculer le symbole de Jacobi en temps quasi linéaire. L'objectif de mon stage était d'adapter un de ces algorithmes (l'algorithme de Richard Brent et Paul Zimmermann) en un algorithme quasi linéaire pour calculer le symbole de résiduosité cubique, qui est l'analogue du symbole de Jacobi pour les cubes.

Pendant près de 35 ans, l'algorithme le plus rapide qui était connu permettait de multiplier des grands nombres de taille n en un temps O(n log n log log n). Il s'agissait de l'algorithme de Schönhage-Strassen. En 2007, Martin Fürer publie un article où il explicite un algorithme permettant d'obtenir une complexité en O(n log n 2^O(log*n)). Un des problèmes théoriques est de savoir si on peut descendre à O(n log n log^*n) voire O(n log n), sachant que la borne inférieure O(n log n) n'est à ce jour qu'une conjecture. Un problème plus pratique est de savoir comment implémenter l'algorithme de Fürer de sorte à concurrencer les implémentations actuelles de Schönhage-Strassen. Ces 2 problèmes seront l'objet de la présentation.

résumé en anglais

Durant la seconde moitié du 20ème siècle, les systèmes de numération basés sur les développements en fractions continues ont été utilisés pour démontrer des propriétés sur la répartition de la suite (nα)_n∈N modulo 1, avec α réel. Dans cet exposé, nous allons utiliser certaines de ces propriétés pour deux applications.
La première application est la recherche de cas difficiles à arrondir de fonctions élémentaires. Plus particulièrement, nous nous intéresserons à l'algorithme de Lefèvre, son lien avec le théorème des trois longueurs, et son comportement divergent sur GPU. Nous proposerons ainsi un nouvel algorithme avec un flot de contrôle plus régulier permettant une accélération de 3.44x sur GPU par rapport au déploiement de l'algorithme de Lefèvre. Il s'agit d'un travail en collaboration avec Pierre Fortin et Stef Graillat.
La seconde application est l'arithmétique modulaire. Nous proposerons des algorithmes de multiplication et de division modulaires de complexité quadratique reposant sur l'écriture dans des bases issues de développements en fractions continues. Ces algorithmes se basent donc sur l'algorithme d'Euclide étendu et présentent l'avantage d'intégrer la réduction.

Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d’index dans le cas le plus simple : celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet une amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.

résumé en anglais

Cette exposé traite de la synchronisation de systèmes dynamiques dans une maître-esclave. Il s'agit d'un scénario typiquement rencontré en cryptographie. Une attention spécifique est portée sur l'autosynchronisation, comportement qui caractérise la synchronisation par le simple couplage maître-esclave et donc en l'absence de tout contrôle extérieur. Elle joue un rôle majeur dans les communications impliquant des chiffreurs par flot autosynchronisants. L'étude de l'autosynchronisation dans le contexte cryptographique s'appuie sur la théorie du contrôle. Un lien original entre l'autosynchronisation et le principe de chiffrement/déchiffrement en cryptographie est mis en évidence. Il fait appel à la propriété de platitude des systèmes dynamiques, un concept emprunté à l'automatique. On montre que les systèmes dynamiques plats définissent complètement l'ensemble des systèmes autosynchronisants et permettent d'élargir les structures existantes des chiffreurs autosynchronisants. La platitude est tout d'abord étudiée pour deux types de systèmes non linéaires : les systèmes linéaires commutés et à paramètres variants (LPV). La caractérisation des sorties plates s'appuie sur le concept de semigroupes nilpotents et un algorithme performant est proposé. Par la suite, l'autosynchronisation est étudiée dans le contexte booléen privilégié en cryptographie. On caractérise entièrement l'ensemble des fonctions booléennes autosynchronisantes. On montre qu'elle peuvent être classées en trois catégories et que jusque là, seule la première était connues et utilisée.

Un jeu de tuiles apériodique est une collection finie de pièces de puzzles qui permettent de couvrir le plan, mais pas de façon périodique. De tels jeux sont fondamentaux dans l'étude des pavages et on peut en général relier à chaque grand résultat de la théorie la découverte d'une nouvelle façon de créer un jeu apériodique.
Le plus petit connu contient 13 tuiles et a été inventé par Culik suivant une technique de Kari et utilise une propriété arithmétique très simple: Si on part d'un réel non nul et qu'on le multiplie par 2 ou divise par 3 un certain nombre de fois, on ne retombera jamais sur le réel initial.
Je vais présenter ici un programme que j'ai réalisé et qui prouve en temps humain qu'il faut au moins 10 tuiles pour réaliser un jeu apériodique. Le même programme peut sans doute montrer qu'il faut au moins 11 tuiles, mais on se heurte alors à deux difficultés: (a) le temps d'exécution commence à être inhumain (b) certains jeux à 10 tuiles ont l'air d'être apériodiques, et il faut montrer "à la main" qu'ils ne le sont pas.

résumé en anglais

Les systèmes polynomiaux multi-homogènes, déterminantiels et booléens jouent un rôle prépondérant dans plusieurs applications en Cryptologie, en Géométrie Réelle ou en Optimisation. Dans cet exposé, par des méthodes de calcul de bases de Gröbner et sous des hypothèses de généricité sur les coefficients de ces systèmes, je présente de nouvelles bornes de complexité asymptotique pour leur résolution :

• dans le cas déterminantiel et dans le cas bilinéaire, ces bornes permettent d'identifier des sous-familles de systèmes pour lesquelles la complexité de résolution est polynomiale en le nombre de solutions ;
• pour les systèmes quadratiques booléens, un nouvel algorithme de résolution est proposé. Pour un système de n équations en n variables, l'espérance de la complexité d'une variante probabiliste est O(2^0.792n), sous des hypothèses algébriques sur le système d'entrée. Ceci permet de résoudre exponentiellement plus rapidement que par recherche exhaustive.

L'obtention de ces bornes passe par une analyse de la structure algébrique des systèmes ; ceci conduit à des formules explicites pour la série de Hilbert générique des idéaux associés. Cette analyse sera illustrée par des applications en Cryptologie (cryptanalyse de MinRank, HFE et QUAD).
Travail commun avec Jean-Charles Faugère et Mohab Safey El Din (systèmes déterminantiels et multi-homogènes) et avec Magali Bardet, Jean-Charles Faugère et Bruno Salvy (systèmes booléens).

résumé en anglais

résumé en anglais

Pour la phase de sélection polynomiale, CADO-NFS utilise l'algorithme présenté par Kleinjung au workshop CADO en 2008. On décrira en détail cet algorithme, ainsi que les détails d'implantation dans CADO-NFS. Travail en commun avec Shi Bai (Australian National University) et Alain Filbois (SED Inria Nancy - Grand Est).

Le produit de polynômes et le produit de matrices sont deux des opérations les plus élémentaires en mathématiques ; l'étude de la complexité de ces calculs est au centre de l'informatique. Dans cet exposé, nous nous intéressons à la complexité de la multiplication d'opérateurs différentiels linéaires. Ces objets algébriques encodent les équations différentielles linéaires, et forment un anneau non commutatif qui partage de nombreuses propriétés avec l'anneau commutatif des polynômes usuels.
Pourtant, l'étude algorithmique des opérateurs différentiels linéaires est actuellement beaucoup moins avancée que dans le cas polynomial : la complexité de la multiplication a été abordée que récemment, mais pas complètement résolu. Le but de ce travail est de faire un pas pour combler cette lacune, et à résoudre une question ouverte posée par van der Hoeven.
Ce travail est commun avec Alin Bostan (INRIA) et Joris van der Hoeven (CNRS).

résumé en anglais

Certains problèmes relatifs aux courbes hyperelliptiques de genre 2 sur les corps finis peuvent être résolus algorithmiquement en effectuant des calculs dans un certain corps de nombre associé à la courbe hyperelliptique. Le corps considéré est alors un corps CM quartique, c'est à dire une extension quadratique imaginaire d'un corps quadratique réel. Nous présenterons des algorithmes destinés spécifiquement à accélérer les calculs dans ces corps.

résumé en anglais

résumé en anglais

résumé en anglais

résumé en anglais

L'utilisation des courbes elliptiques et hyperelliptiques en cryptographie nécessite de pouvoir calculer en un temps raisonnable l'ordre de la jacobienne de la courbe. T. Satoh proposa à Eurocrypt 2009 un algorithme polynomial pour vérifier si l'ordre de la jacobienne d'une courbe hyperelliptique de la forme Y² = X⁵ + aX³ + bX définie sur un corps fini F_q admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur F_q en partant de la fonction zeta de la jacobienne sur une extension où la jacobienne se partage en deux courbes elliptiques. L'approche de T. Satoh se généralise pour obtenir l'expression exacte de la fonction zeta de jacobienne de courbes hyperelliptiques de genre 2 de la forme ci-dessus et Y² = X⁶ + aX³ + b. Nous avons obtenu les expressions exactes des fonctions zeta par des résolutions successives d'équations de degré 2.
Les systèmes à bases de couplages utilisent des courbes elliptiques particulières présentant un petit degré de plongement par rapport à un grand sous-groupe d'ordre premier. Les formules explicites d'ordre des jacobiennes nous permettent de compléter les deux algorithmes de Freeman et Satoh pour générer des jacobiennes pour les couplages. Notre méthode utilise celles proposées pour construire des courbes elliptiques pour les couplages (la méthode de Cocks-Pinch et celle de Brezing-Weng).
Les formules exactes permettent de voir que les restrictions faites précédemment sur le degré de plongement sont valables pour une courbe elliptique et peuvent être réduites pour une jacobienne. Pour illuster notre méthode nous présentons des constructions intéressantes de paramètre ρ environ 4 pour une méthode à la Cocks-Pinch et environ 3 pour une méthode à la Brezing-Weng.

SSL/TLS est un protocole ayant pour but de créer un canal de communication authentifié, protégé en confidentialité et en intégrité. L'objectif initial de SSL/TLS était la sécurisation du protocole HTTP, mais son champ d'application s'est élargi depuis : protection d'autres services (SMTPS, LDAPS, etc.), création de réseaux privés virtuels (VPN), sécurisation de réseaux sans-fil (EAP-TLS).
Après un rapide historique des différentes versions de SSL/TLS et une description rapide du protocole, je présenterai un panorama des attaques connues, qu'elles portent sur le protocole en lui-même, les algorithmes cryptographiques, ou les certificats mis en oeuvre. Cette énumération des vulnérabilités de SSL/TLS permettra de déduire des recommandations pour une utilisation sécurisée de SSL/TLS.

résumé en anglais

résumé en anglais

La présentation portera sur la problématique générale des attaques sur les composants cryptos par observation de leurs canaux physiques (courant et champ électro-magnétique). L'accent sera porté sur l'approche par SNR ou rapport signal à bruit, une méthode permettant de quantifier la résistance d'une implémentation donnée inspirée de la théorie des communications numériques [Mangard et al., 2004]. On montrera comment il est possible de déterminer un ordre de grandeur théorique du nombre de mesures nécessaires à casser une implémentation donnée.
On présentera ensuite les principales familles de contre-mesures existantes (la désynchronisation, le masquage, les technologies alternatives au CMOS) et leurs effets respectifs en terme de rapport signal-à-bruit. On présentera en passant deux solutions de masquage de l'algorithme AES, une logicielle par recalcul de la boîte S, l'autre matérielle reposant sur sa définition algébrique.

Cet exposé a pour objectif de présenter quelques points intéressants de l'implémentation de l'algorithme de recherche exhaustive de formules pour le calcul d'applications bilinéaires présenté aux JAV 2012.

résumé en anglais

résumé en anglais

résumé en anglais

résumé en anglais

résumé en anglais

L'algorithme FFS, utilisé pour calculer le logarithme discret dans un corps fini, comporte une étape appelée cofactorisation. Il s'agit de traiter un grand nombre de couples de polynômes en testant leur friabilité et en les factorisant le cas échéant. Nous verrons comment l'entrée de cette étape a été modélisée et quelles stratégies ont été mises en place.

Nous rappellerons tout d'abord quelques rudiments de la théorie des codes correcteurs et des codes géométriques. Nous nous focaliserons ensuite sur le problème classique (et souvent difficile) de rechercher de bons codes de longueur n à coefficients dans F₂. Une approche classique consiste à choisir un bon code défini sur une extension F_2^m de F₂ et de le « descendre » sur F₂ via une opération arithmétique classique (restriction, trace, etc...)
Si le code défini sur F_2^m est un code géométrique construit sur une courbe de genre 0 et judicieusement choisi, l'opération de restriction à F₂ donne des codes bien meilleurs que dans le cas « générique ». Dans cet exposé, nous présenterons une généralisation de cette approche aux courbes de genre quelconque basée sur une utilisation l'opérateur de Cartier. Cette approche permet ainsi de construire d'intéressantes familles asymptotiquement bonnes de codes sur F₂.

L'implantation d'une expression arithmétique donnée en machine soulève plusieurs questions, notamment quant à la vitesse et la précision des calculs en arithmétique approchée. L'outil CGPE (Code Generation for Polynomial Evaluation) a été conçu dans le but de trouver des schémas d'évaluation satisfaisants pour un polynôme approximant une fonction donnée. Ces schémas doivent être rapides sur des processeurs entiers de type VLIW, et suffisamment précis pour permettre d'en déduire l'arrondi correct, au sens du standard IEEE 754-2008, ou l'arrondi fidèle pour la fonction de départ.
Dans cet exposé, nous verrons comment les schémas d'évaluation sont définis et manipulés au sein de CGPE. Ensuite, je montrerai comment l'ajout de contraintes numériques permet d'accéler la recherche dans CGPE. Enfin, je parlerai de la généralisation de cette approche pour s'attaquer au problème de minimisation du nombre d'opérations d'un type donné.

résumé en anglais

La réduction forte de réseaux est la clé de la plupart des attaques contre les cryptosystèmes basés sur les réseaux. Entre la réduction HKZ, forte mais trop coûteuse, et la réduction LLL, plus faible mais rapide, existent plusieurs tentatives d'obtenir des compromis efficaces. Celle qui semble atteindre le meilleur rapport temps/qualité est la réduction BKZ, introduite par Schnorr et Euchner en 1991. Cependant, aucune borne de complexité raisonnable sur cet algorithme n'était connue jusqu'à maintenant. Nous prouvons qu'après Õ(n³/k²) appels à une routine de HKZ-réduction, BKZ_k renvoie une base telle que la norme du premier vecteur est bornée par ≈ γ_k^n/2(k-1) × det(L)^1/n. Le principal outil de la preuve est l'analyse d'un système dynamique linéaire associé à cet algorithme.

Nous montrerons que certaines questions de combinatoire énumérative peuvent être traitées de façon systématique en utilisant une approche de type « mathématiques expérimentales » guidée par des algorithmes modernes du calcul formel. Nous décrirons la découverte et la preuve assistées par ordinateur de l'algébricité de la série génératrice des chemins confinés au quart de plan et utilisant des pas de longueur un vers l’est, l'ouest, le sud-ouest, ou le nord-est.

résumé en anglais

résumé en anglais

L'addition sur les courbes d'Edwards a apporté le premier exemple de loi d'addition qui puisse être définie, dans certains cas, quels que soient les points rationnels choisis. Cela a mené à considérer la notion de k-complétude pour les lois d'addition sur une variété abélienne A/k. Je présenterai les résultats obtenus avec David Kohel et Christophe Ritzenthaler. Nous montrons notamment la non existence d'une seule loi géométriquement complète et, si le groupe de Galois absolu de k est infini, l'existence d'un plongement projectif de A muni d'une loi d'addition k-complète.

résumé en anglais

résumé en anglais

Les processeurs graphiques (GPU) actuels sont des architectures parallèles qui offrent une importante puissance de calcul disponible à faible coût. Il est possible de détourner leur usage pour réaliser du calcul non graphique, donnant lieu au domaine du calcul généraliste sur processeur graphique (GPGPU).
Nous considérons d'une part des techniques logicielles pour tirer parti de l'ensemble des opérateurs arithmétiques spécifiques aux GPU dans le cadre du calcul scientifique, et d'autre part des adaptations matérielles aux GPU afin d'exécuter plus efficacement les applications généralistes.
En particulier, nous identifions la régularité comme une opportunité générale d'optimisation des architectures parallèles, et exposons son potentiel par la simulation d'une architecture GPU existante.
Nous considérons en particulier deux alternatives permettant d'exploiter cette régularité. D'une part, nous mettons au point un mécanisme matériel dynamique de dé-duplication des registres qui vise à améliorer l'efficacité énergétique des unités de calcul. D'autre part, nous présentons une analyse statique opérée à la compilation, qui permet de simplifier le matériel dédié au contrôle dans les GPU.

... ou le problème des courbes de genre 1 sans point réel.

Dans cet exposé, on présentera une variante de l'algorithme F4 pour le calcul de bases de Gröbner, permettant de résoudre plus rapidement des familles de systèmes polynomiaux ayant des expressions similaires. On donnera une illustration de l'efficacité de cette variante sur les problèmes de calculs d'indices sur courbes elliptiques, et plus particulièrement sur la courbe Oakley 'Well Known Group' 3 du standard IPSEC.

Dans de nombreux protocoles cryptographiques, notamment à base de couplages, il est nécessaire de disposer de fonctions de hachage à valeur dans le groupe des points d'une courbe elliptique (ou plus généralement dans la jacobienne d'une courbe hyperelliptique). Nous expliquerons comment il est possible de construire de telles fonctions à partir de fonctions de hachage plus classiques (à valeur dans des chaînes de bits) d'une façon qui préserve la sécurité des protocoles considérés. L'étude de ces fonctions et les preuves de sécurité associées mettent en jeu des outils mathématiques variés, depuis des calculs élémentaires dans les corps finis jusqu'à des résultats plus sophistiqués sur les sommes d'exponentielles et les fonctions L de courbes algébriques.

résumé en anglais

Travail efféctué lors d'un stage de Master 2 sous la direction de Jean-Charles Faugère et Guénaël Renault.
Dans la méthode de résolution du DLP sur une courbe elliptique par calcul d'indice (proposée par C. Diem et P. Gaudry indépendemment), une étape cruciale nécessite de décomposer des points sur cette courbe. Une méthode algébrique pour résoudre ce problème est de le modéliser sous forme de systèmes polynomiaux. Pour une courbe elliptique définie par une équation de Weierstrass, Diem et Gaudry modélisent le problème de décomposition d'un point à l'aide des polynômes de Semaev. Dans cet exposé, nous présenterons de nouvelles méthodes pour décrire ce problème sous forme de systèmes polynomiaux à partir de différentes représentations de courbes elliptiques. Nous mettrons en évidence des représentations de courbes telles que les systèmes polynomiaux obtenus ont une structure très particulière. Nous présenterons aussi les résultats pratiques pour la résolution des systèmes générés par chacunes des modélisations et représentations étudiées. Ces travaux permettent d'identifier les représentations qui apportent un gain sur la résolution du problème de décomposition d'un point.

La sélection polynomiale est la première étape du crible NFS et consiste à trouver un couple de polynômes dans Z[X], irréductibles, ayant un résultant égal à N le nombre à factoriser (ou à défaut, un petit multiple de N) et vérifiant certaines conditions sur la taille de leurs coefficients.
Tout d'abord je vous parlerai de la méthode de Peter Montgomery permettant de générer un couple de polynômes quadratiques « optimaux » pour le crible NFS.
Ensuite je vous exposerai différentes méthodes pouvant éventuellement mener à la génération de couples de polynômes de degré > 2.

La résolution des systèmes algébriques en deux variables est l'opération principale, et donc la partie bloquante, pour de nombreux algorithmes pour l'étude des courbes planes, qu'il s'agisse d'un simple tracé ou d'un calcul complet de topologie.
Après un résumé sur les motivations du moment, particulièrement un nouvel algorithme de calcul de topologie de courbes, deux composants essentiels seront détaillés :

• l'approximation numérique certifiée des solutions réelles d'un polynôme en une variable avec une très grosse précision, essentielle pour une résolution « récursive » d'ensembles triangulaires ou de paramétrisations rationnelles des systèmes considérés ;
• un calcul dédié de paramétrisation rationnelle des solutions.

En conclusion on résumera les progrès induits par ces nouveaux composants sur les algorithmes pour l'étude des courbes planes présentés en introduction.

L'enveloppe convexe d'une famille de points est le plus petit polygone les contenant. Il s'agit d'un objet naturel, largement étudié en géométrie algorithmique.
L'enveloppe convexe de n points du plan a au plus n sommets, ce qui se produit quand les points sont « en position convexe ». Imaginons maintenant que l'on parte d'une telle configuration – n points en position convexe – et que l'on perturbe chaque point aléatoirement en le remplaçant par un point pris, par exemple, dans un disque de rayon ε centré en sa précédente position. Combien de points restent, en moyenne, sur l'enveloppe convexe ?
Dans cet exposé, je présenterai quelques résultats obtenus avec Dominique Attali (GIPSA - Grenoble) et Olivier Devillers (INRIA - Sophia Antipolis) sur cette question, qui correspond à l'analyse de la complexité « lissée » (au sens de Tang et Spielman) de l'enveloppe convexe. Je montrerai aussi comment les lois que l'on peut obtenir dans ce cadre modélisent assez finement les phénomènes d'arrondis sur des grilles régulières.
Lien vers l'article correspondant.

On cherche à calculer une seconde décimale après la virgule de la constante de Masser-Gramain, qui est une généralisation en 2D de la constante d'Euler (travail en cours).

J'exposerai une voie d'attaque possible pour factoriser un produit N de deux entiers par des moyens analytiques. Les points essentiels de cette approche sont la définition d'une fonction arithmétique multiplicative (en fonction de N) et la théorie de la fonction zêta de Riemann, qui au moyen de son équation fonctionnelle permet d'isoler des termes principaux. En particulier, on arrive à devoir évaluer des séries multiples données par des fonctions analytiques. Certaines d'entre elles (les séries singulières mineures) ne posent pas de problème, mais je suis à la recherche d'un ingrédient (peut-être tiré du calcul numérique) pour évaluer les restantes (séries singulières majeures). En cas de succès, cela permettrait d'arriver à un algorithme déterministe avec un temps d'exécution prouvé vraisemblablement O(exp(log^c N)) pour tout c > 0.

Le thème principal de l'exposé est le calcul de la structure du groupe de classes d'idéaux de l'ordre maximal d'un corps de nombres.
Les meilleurs algorithmes connus à ce jour pour résoudre ce problème sont sous-exponentiels par rapport au logarithme du discriminant de l'ordre maximal. Nous nous intéresserons aussi au calcul du régulateur et à la résolution du problème du logarithme discret et du test de principalité d'idéaux dans l'ordre maximal. En dimension 2, nous étudierons les stratégies basées sur le crible quadratique dûes à Jacobson et leurs améliorations pratiques. Pour les corps de dimension arbitraire, nous verrons comment diminuer la complexité de la résolution de ces problèmes dans une certaine classe de corps de nombres.

résumé en anglais

résumé en anglais

Les courbes elliptiques, très utilisées en cryptographie à clé publique, se généralisent avec les variétés abéliennes. Un exemple important de variétés abéliennes est donné par les jacobiennes de courbes hyperelliptiques. Les fonctions thêta permettent de représenter les points d'une variété abélienne et fournissent les formules les plus rapides pour calculer dans les jacobiennes de courbe. Elles sont caractérisées par les thêta constantes correspondantes. Une question naturelle est d'obtenir des formules reliant une courbe sous forme de Weierstrass y² = f(x) et les thêta constantes correspondantes. Thomae a résolu ce problème pour le niveau (2, 2) : ses formules relient des puissances des thêta constantes aux racines de f.
J'expliquerai comment obtenir des formules pour les niveaux (r, r). Il est alors possible d'en déduire les thêta constantes de niveau r. Cette dernière étape peut être utilisé pour « descendre de niveau sans prendre d'isogénie » ce qui permet de calculer des r-isogénies.

résumé en anglais

résumé en anglais

résumé en anglais

Nous présentons un algorithme original de factorisation des entiers de la forme pq² utilisant des résultats classiques sur les formes quadratiques et des techniques de recherche de petites racines de polynômes. Cet algorithme est déterministe et sa complexité (heuristique), en générale exponentielle, dépend essentiellement du régulateur du corps quadratique de discriminant p. Certains cryptosystèmes basés sur l'arithmétique des corps quadratiques fournissent des données permettant de rendre la complexité de notre algorithme polynomiale sur ces entrées et donc de retrouver la clé secrète en quelques secondes sur un PC standard.
Travail en commun avec G. Castagnos, A. Joux et P. Nguyen

Les nombres de Cunningham permettent de plonger des corps de nombres de petit degré dans Z/NZ. Ceci nous permet de sortir des bornes données par le théorème de Mazur sur les torsions possibles des courbes elliptiques. Ensuite, nous exhibons une famille de courbes elliptiques avec le sous-groupe Z/4Z × Z/4Z de torsion défini sur Q(ζ₈) et de rang non nul ainsi qu'une famille avec le sous-groupe Z/6Z × Z/3Z de torsion défini sur Q(ζ₃) et de rang non nul. Ces familles ont été utilisées pour factoriser 2⁹⁷² + 1 et 2¹⁰⁴⁸ + 1. En chemin, nous donnons une représentation paramétrique des courbes avec un groupe de torsion tel que la courbe modulaire associée soit de genre 0 ou 1.

résumé en anglais

Dans la méthode des courbes elliptiques pour factoriser des entiers, on utilise en général des familles de courbes particulières qui permettent d'accélrer les calculs. La famille de Suyama est une de ces familles, dont l'efficacité est due à la présence d'un grand groupe de torsion. Nous proposons une démarche pour construire de nouvelles familles. En particulier, nous avons trouvé deux familles de courbes, chacune paramétrée par une courbe elliptique de rang 1, et offrant de meilleures propriétés que celles de Suyama.

résumé en anglais

résumé en anglais

Les architectures matérielles pour réaliser la cryptographie asymétrique sont intéressante pour de nombreux aspects (performance, embarcabilité, sécurité vis à vis des canaux auxiliaires...) et ont fait l'objet de recherches nombreuses ces dernières années. Dans cet exposé je propose une architecture utilisant les représentations RNS des nombres pour réaliser des multiplications scalaires sur courbes elliptiques quelconque définies sur GF(p). Cette architecture, simple et flexible, permet d'atteindre des temps de calculs très performants tout en restant raisonnables en terme d'encombrement.

résumé en anglais

résumé en anglais

résumé en anglais

La cryptographie sur courbes elliptiques et plus particulièrement à base de couplages a permis de développer un grand nombre de protocoles originaux. Le calcul d'un couplage est une opération non triviale et exigeante en ressources. Ces courbes sont définies sur des corps finis, ici de caractéristique 2 ou 3, et demandent ainsi une arithmétique spécifique à laquelle les processeurs généralistes ne sont pas adaptés. De ce fait il est intéressant d'étudier des opérateurs matériels pour les corps finis, et plus particulièrement la multiplication qui est l'un des goulots d'étranglement du calcul de couplage ($\eta_T$ pour notre cas). Afin d'obtenir des performances accrues, nous avons conçu une architecture basée sur un multiplieur parallèle et pipeliné. Nous étudions ici différents algorithmes de multiplication et leur implémentation sur FPGA. Cette approche nous a permis d'améliorer le temps de calcul d'un couplage et le produit temps-surface.

Une famille d'algorithmes dus (dans leur version générale) à David et Gregory Chudnovsky permet d'évaluer numériquement à grande précision — pour fixer les idées, mille ou dix mille décimales — les fonctions analytiques solutions d'équations différentielles linéaires à coefficients polynomiaux. Le point de départ est un algorithme efficace pour « dérouler » certaines suites récurrentes. Je présenterai ces différents algorithmes, devenus pour la plupart classiques, ainsi que quelques remarques sur leur complexité et leur implémentation.
Par ailleurs, je décrirai un procédé de calcul de bornes sur les suites satisfaisant des récurrences linéaires à coefficients polynomiaux. Dans le contexte des algorithmes précédents, celui-ci permet de contrôler finement le nombre de termes des développements de Taylor à prendre en compte pour garantir une certaine précision lors du prolongement analytique numérique. Il s'agit d'un travail en cours avec mon directeur de thèse Bruno Salvy.

résumé en anglais

http://www.jjj.de/arctan/arctanpage.html

Dans le cadre de l'étude de canaux dans un contexte non coopératif, nous nous intéressons à la reconstruction des codes correcteurs d'erreurs. Dans ce contexte, un observateur qui voudrait avoir connaissance d'informations échangées par des utilisateurs légitimes doit retrouver tous les paramètres de communication et de codage de canal afin de pouvoir décoder l'information circulant sur le canal. Du point de vue de l'attaquant, nous étudions les algorithmes permettant de retrouver sans connaissance a priori les paramètres du codeur de canal et plus particulièrement de codes en blocs linéaires. Nous verrons comment il est possible de retrouver la longueur et la synchronisation utilisée lors de la transmission et comment reconstruire le code en bloc utilisé. Du point de vue de la théorie de l'information, nous nous intéresserons aussi au problème de savoir combien de mots de codes bruités sont nécessaire à la reconstruction.

Depuis leur introduction au milieu des années 80, les courbes elliptiques sont devenues l'un des principaux outils de la cryptographie moderne. La principale opération (en termes de temps de calcul) de tout protocole utilisant les courbes elliptiques est la multiplication de point par un scalaire: le calcul de k*P=P+...+P, où k est un entier et P un point de la courbe. Afin d'effectuer cette opération de la manière la plus efficace possible, de nombreuses méthodes ont été proposées. Elles reposent, en général, sur l'algorithme dit "double-and-add" consistant à effectuer des séries de doublements entrecoupées d'additions, en fonction de la représentation binaire du scalaire k.
Dans cet exposé nous allons sortir des sentiers battus en nous intéressant à des méthodes de multiplication de point basées sur les chaînes d'additions différentielles. Celles-ci ont la particularités d'être principalement composées d'additions (au lieu de doublements), entrainant un plus grand nombre d'étapes de calcul, compensé par le fait qu'il est possible d'obtenir, sous certaines conditions, une addition plus efficace qu'un doublement. Nous verrons que cette approche apparait comme très prometteuse de prime abord, mais que certains problèmes (concernant la taille des chaînes notamment) restent à résoudre afin d'envisager une utilisation concrète.

Je présenterai un système de numération où les entiers sont représentés comme une somme de puissances combinées de 2 et de 3. Ce système, appellé "double-base number system", permet dans certains cas d'accélérer la multiplication scalaire sur les courbes elliptiques. Je reviendrai très rapidement sur ces motivations avant de m'intéresser à des problèmes d'approximation diophantienne liés à ce système. Je présenterai un algorithme optimal pour de calculer l'entier de la forme 2^a3^b le plus proche d'un entier donne, basé sur un autre système de numération "exotique", (peu) connu sous le nom de système d'Ostrowski. Dans une seconde partie, je m'intéresserai ensuite à des questions d'ordre combinatoire, en particulier à dénombrer le nombre de partitions {2,3}-aires chaînées.

Dans certains systèmes formels, les mécanismes de conversion et de réflexion permettent l'évaluation "rapide" de fonctions et l'utilisation de leur valeurs au sein de preuves. Ces mécanismes peuvent alors remplacer avantageusement l'approche déductive traditionnelle en substituant des calculs aux applications de théorème. Afin d'adapter cette approche aux preuves manipulant des nombres réels, une bibliothèque d'arithmétique flottante a été développée pour l'assistant de preuves Coq. Elle fournit les opérateurs arithmétiques de base et quelques fonctions élémentaires, le tout en multi-précision et en base quelconque. Les calculs sont effectifs et réalisés au sein du formalisme de Coq. Une bibliothèque d'arithmétique d'intervalles a été construite par dessus. En conjonction avec des méthodes de différentiation, elle offre à l'utilisateur des tactiques Coq permettant de prouver automatiquement des inégalités sur des expressions à valeurs réelles.

En 1996, Coppersmith introduit deux techniques basées sur la réduction de réseaux permettant de retrouver de petites racines d'équations polynomiales. Une de ces techiques s'applique au cas d'équations modulaires en une variable, l'autre concerne les équations entières à deux variables. Depuis, ces méthodes ont été utilisées dans de nombreuses applications cryptographiques. Pour certaines de ces applications, qui font intervenir plus de deux variables, des extensions des méthodes de Coppersmith ont été proposées. Malheureusement, ces méthodes sont heuristiques et ne permettent pas toujours de retrouver les racines recherchées quand le nombre de variables est supérieur à deux.
Dans cette présentation, nous proposons une nouvelle variante de l'algorithme de Coppersmith dans le cas d'équations entières faisant intervenir trois variables et nous étudions son applicabilité. Nous nous intéressons notamment à des attaques sur RSA dans le cas d'exposants petits. Cette méthode utilise non seulement la réduction de réseaux mais également le calcul de bases de Gröbner. En principe, elle peut être généralisée dans le cas de quatre variables ou plus.

La co-induction en Coq fournit un cadre de travail confortable pour décrire des algorithmes certifiés pour l'arithmétique réelle exacte.
La bibliothèque que nous décrivons s'inspire d'expériences précédentes utilisant des séquences infinies de chiffres redondants en base 2 et les généralise par l'utilisation de bases entières arbitraires.
L'objectif est de pouvoir utiliser les opérations rapides des entiers natifs et de fournir ainsi des calculs efficaces sur les nombres réels à l'interieur du système Coq.
Nous décrirons la représentation utilisée ainsi que quelques algorithmes, en particulier une technique de calcul des series entières convergentes.

Nous présentons le DBNS (Double-Base Number system) et ses applications la cryptographie, en particulier pour accélérer la multiplication scalaire sur courbes elliptiques. Après une brève introduction, nous détaillerons 2 applications pratiques :

• un algorithme de multiplication scalaire rapide pour des courbes génériques lorsque des précalculs sont autorisés. Ce travail repose sur le concept de DBNS étendu qui est une généralisation naturelle du DBNS.
• le premier algorithme de multiplication scalaire de complexité sous-linéaire. Cette méthode exploite une généralisation du DBNS aux courbes de Koblitz

Depuis l'introduction du produit matriciel de complexité sous-cubique, des algorithmes par bloc ont été conçus pour réduire la complexité de la plupart des problèmes classique d'algèbre linéaire à celle du produit de matrice: O(n^w). Cependant, jusqu'à récemment, le meilleur algorithme pour le calcul du polynôme caractéristique exigeait un nombre logarithmique de produit matriciels, impliquant une complexité de O(n^w log n) opérations dans le corps de base. Nous présenterons un nouvel algorithme probabiliste de type Las Vegas, calculant le polynôme caractéristique dans un corps suffisamment grand. Grâce à un nouveau type de réduction, il atteint la complexité O(n^w).
Les réductions au produit matriciel sont par ailleurs d'un grand intérêt pratique car elle permettent l'utilisation de noyaux efficaces pour cette opération (combinant optimisation de cache et produit sous-cubique). Nous présenterons ainsi les principes de la bibliothèque FFLAS-FFPACK pour l'algèbre linéaire dense dans un corps fini. En particulier, dans ce contexte, une implémentation du nouvel algorithme de calcul du polynôme caractéristique, permet d'améliorer radicalement les temps de calcul des meilleures implémentations précédentes.

Cet exposé correspond à un travail réalisé avec David Lubicz. Il présente un nouveau schéma de diffusion (broadcast) avec révocations éphémères (stateless receivers). Contrairement aux schémas traditionnels dans le même cadre (Complete Subtree, Subset Difference), l'émetteur utilise des attributs pour décrire l'ensemble des destinataires. Ainsi, lorsque l'émetteur souhaite révoquer une catégorie d'utilisateurs, il peut le faire en utilisant simplement l'attribut relatif à cette catégorie, et non en révoquant individuellement chacun des membres de la catégorie.
Dans les schémas existants à base d'attributs, le déchiffrement représente un coût calculatoire important pour les destinataires, par le calcul de nombreux couplages. Le schéma présenté utilise une approche différente, et permet de limiter le déchiffrement à essentiellement 3 couplages.

résumé en anglais

résumé en anglais

Jusqu'à présent, le consensus est que, dans les processeurs généralistes, les fonctions élémentaires en virgule flottante soient implémentées grâce à des algorithmes "micro-codés" --c'est-à-dire utilisant les opérations de base de l'unité flottante-- et non par des opérateurs matériels dédiés. Ce choix s'explique par le surcoût important en silicium qu'auraient de tels opérateurs par rapport à l'utilisation somme toute restreinte de ces opérations.

Pour certaines applications spécifiques très calculatoires reposant lourdement sur ces fonctions, un tel choix peut s'avérer être un véritable handicap. Cependant, la capacité d'intégration des circuits FPGA (pour Field-Programmable Gate Arrays) est aujourd'hui suffisante pour les utiliser comme de véritables co-processeurs reconfigurables, permettant ainsi de "compléter" les unités de calcul des processeurs généralistes selon les besoins de chaque application.

Lors de cet exposé, après avoir brièvement présenté les FPGA et leur architecture générale, je détaillerai, à travers l'exemple de la fonction exponentielle, les diverses problématiques qui entrent en jeu lors de la conception et l'implémentation d'algorithmes dédiés au matériel. Je donnerai enfin les résultats obtenus qui, montrant un facteur d'accélération de l'ordre de 100 par rapport à un processeur généraliste, nous encouragent à poursuivre nos travaux dans cette direction.

résumé en anglais

Dans cet exposé, nous expliquerons comment calculer effectivement des équations donnant un plongement projectif de l'espace des variétés abéliennes munies d'une certaine structure de niveau et caractériser dans cet espace les relevés canoniques. Nous donnerons des applications algorithmiques.

résumé en anglais

résumé en anglais

résumé en anglais

Le problème (SVP) de trouver un vecteur non nul le plus court d'un réseau de $\R^n$ de dimension $d$ est un problème très classique ; au cours des dix dernières années, de nombreux travaux ont montré des bornes inférieures sur la complexité de ce problème. Ces résultats sont à la base des arguments de sécurité d'un certain nombre de cryptosystèmes (Ajtai-Dwork, NTRU). Le meilleur algorithme pratique pour ce problème, dû à Kannan, consiste à énumérer des points dans un ellipsoïde. Son analyse consiste classiquement à borner le nombre de points par le volume, qui est à son tour estimé par le volume du pavé circonscrit, donnant une complexité de $\tilde{O}(d^{d/2(1+o(1))})$. Nous montrons qu'une analyse plus fine conduit \`a une complexit\'e de $\tilde{O}(d^{d/(2e)(1+o(1))})$; ce résultat permet également d'améliorer la complexité des algorithmes de recherche du vecteur le plus proche (CVP), ou de calcul de bases "blocs-réduites" à la Schnorr.

Parce que les nombres manipulés en machine ont généralement un domaine et une précision limités, il est nécessaire de certifier soigneusement que les applications les utilisant se comportent correctement. Réaliser une telle certification à la main est un travail propice à de nombreuses erreurs. Les méthodes formelles permettent de garantir l'absence de ces erreurs, mais le processus de certification est alors long, fastidieux et généralement réservé à des spécialistes.
Le travail présenté dans cet exposé vise à rendre ces méthodes accessibles en automatisant leur application. L'approche adoptée s'appuie sur une arithmétique d'intervalles accompagnée d'une base de théorèmes sur les propriétés des arithmétiques approchées et d'un mécanisme de réécriture d'expressions permettant le calcul de bornes fines sur les erreurs d'arrondi.
Ce travail s'est concrétisé par le développement de l'outil Gappa d'aide à la certification. Il permet de vérifier les propriétés de codes numériques qui utilisent de l'arithmétique à virgule fixe ou à virgule flottante. Cette vérification s'accompagne de la génération d'une preuve formelle de ces propriétés utilisable par l'assistant de preuves Coq.
Gappa a été utilisé avec succès pour certifier la correction de fonctions dans les bibliothèques CRlibm, CGAL et FLIP par exemple.

Le développement d'algorithmes numériques nécessite de borner certaines fonctions, en particulier les fonctions représentant une erreur d'approximation. Ce problème se réduit au calcul de la norme infinie de la fonction d'erreur. Par exemple, le développement de fonctions élémentaires, tant au niveau logiciel que matériel, utilise ce genre de calcul.
Il existe déjà des implémentations de la norme infinie fournissant une très bonne approximation de la valeur réelle de la norme. Cependant, il n'existe pas d'algorithme capable de fournir un résultat à la fois précis et sûr. On entend par *sûr*, un algorithme qui renvoie une valeur majorant la norme réelle et qui fournit par ailleurs un certificat prouvant la validité de cette majoration.
Nous proposons un algorithme de calcul de la norme infinie utilisant l'arithmétique d'intervalles. Cet algorithme est optimisé pour les fonctions correspondant à une erreur relative ou absolue, c'est-à-dire des fonctions numériquement très mal conditionnées du fait d'importantes cancellations. Notre algorithme peut aussi, dans une certaine mesure, travailler avec des fonctions numériquement instables à proximité de certains points où elles ne sont définies que par continuité.
Enfin, notre algorithme peut retenir l'arbre des calculs qu'il a effectués afin de produire une preuve de correction du résultat de son calcul.

L'arrondi correct des fonctions élémentaires en double précision demande l'approximation de la fonction avant l'arrondi final à une précision d'environ 2^-120. Le format le plus précis dont l'implémentation est requise par la norme IEEE 754 est la double précision avec 53 bits de mantisse. Le téchniques traditionelles de type double-double ne suffisent donc pas. On s'intéressera alors en premier lieu au format triple-double et ses avantages devant un format multiprécision à base de calcul entier.
Ces avantages en terme de performance entraînent certains inconvénients. L'approche de preuve se base sur un ensemble de théorèmes -- deux par opérateur triple-double -- qui établissent un lien entre la précision de l'opérateur et une borne de chevauchement des composantes du triple-double ainsi qu'entre les bornes de chevauchement elles-même. L'instantiation de ces théorèmes paramétrés est tout de même fastidieuse ce qui provoque des erreurs dans la preuve du code produit.
On verra que l'évaluation de Horner de polynômes d'approximation d'une fonction variant peu dans un domaine donné est un problème très bien conditionné. D'une part, on peut exploiter ce bon comportement pour une utilisation mixte de code double, double-double et triple-double précision donnant de bonnes performances. D'autre part, le bon conditionnement permet d'automatiser le processus de développement du code pour l'évaluation en formats mixtes et de la preuve formelle de la borne d'erreur arithmétique.
L'automatisation accélère le processus de développement d'une fonction élémentaire non seulement en surmontant les quelques problèmes liés au format triple-double mais aussi en permettant d'essayer rapidement plusieurs moyens d'approcher une fonction donnée.
Les résultats montrés sont la combinaison fructueuse de plusieurs travaux, entre autre, l'implémentation et la preuve d'opérateurs triple-double, la maturité de leur exploitation, en particulier concernant leur preuve en Gappa, et l'implémentation d'une norme infinie suffisamment fiable.

Pour calculer des valeurs approchées numériques des fonctions mathématiques usuelles, on remplace généralement la fonction par une autre, très proche et plus facile à calculer. Ainsi, l'élaboration d'un algorithme numérique pour évaluer la fonction suit généralement les étapes suivantes :

1. on détermine sur quel intervalle on souhaitera évaluer la fonction ;
2. on détermine avec quelle précision on souhaite connaître les valeurs de la fonction ;
3. on cherche un approximant fournissant la précision requise sur l'intervalle choisi.
4. on cherche un bon algorithme pour évaluer l'approximant.

Pour la troisième étape, on choisit généralement un polynôme (notamment parce que la quatrième étape a été très bien étudiée dans le cas où l'approximant est un polynôme et on sait la traiter de manière satisfaisante).

Les coefficients du polynôme doivent être stockés dans la mémoire de l'ordinateur et doivent donc être représentables sous forme de nombres flottants. Nous nous intéressons au problème de la recherche d'un très bon polynôme à coefficients représentables en machine, pour approcher une fonction continue. En utilisant la théorie des réseaux de points (et l'algorithme LLL de A. Lenstra, H. Lenstra et L. Lovasz) nous proposons un algorithme permettant d'obtenir un tel polynôme. Nous illustrerons les avantages et les défauts de l'algorithme sur un exemple complet.

Les registres à décalage sont des circuits très courants en électronique. Ils sont toujours associés à des circuits (combinatoires ou séquentiels) de rétroaction. Parmi tous ces circuits, les registres à décalage à rétroaction linéraire (Linear Feedback Shift Registers - LFSRs) sont les plus répandus. Ils sont présents dans tous les systèmes de communication pour le brassage des données, l'étalement de spectre, les chiffrements à flot ou la vérification matérielle (Built-in Self Test)... Malgré cette popularité, l'impact des propriétés des LFSRs n'a jamais été vraiment étudié en terme d'implantation. J'ai travaillé sur la synthèse des LFSRs sur les FPGA Xilinx Spartan2E en terme de surface, de chemin critique et de débit. L'étude des implantations haut débit est très importante pour la synthèse logicielle. Je décrirais les propriétés que l'on peut observer pour les deux types de synthèse. Pour conclure, je décrirais certain travaux en cours sur les registres à rétroaction non-lineaire comme les FCSRs (Feedback with Carry Shift Registers).

résumé en anglais

Les algorithmes de chiffrement par bloc sont abondamment utilises dans les communications modernes et assurent la confidentalite des donnees. Un algorithme de chiffrement par bloc est une permutation dependant d'un parametre appele cle secrete. Differentes methodes ont ete proposees pour mettre en defaut la securite de ces algorithmes. Parmi les methodes statistiques, on retrouve notamment la cryptanalyse lineaire et differentielle. Ces methodes se basent sur la recherche d'expressions simples appelees caracteristiques. Ces expressions sont probabilistes et donnent de l'information sur la cle secrete a partir de paires clair/chiffre. L'evaluation de l'efficacite de ces methodes permettent de mettre en evidence les proprietes algebriques auquelles les composantes de l'algorithme de chiffrement doivent satisfaire afin de rendre l'algorithme le plus resistant possible aux attaques connues.
Nous commencerons l'expose par une breve introduction a la cryptographie. Nous decrirons ensuite les reseaux de Feistel, une des classes importantes d'algorithmes de chiffrement par bloc dont le precedent standard americain DES fait partie. Nous poursuivrons l'expose en esquissant les principes de la cryptanalyse lineaire. En outre, nous presenterons une generalisation de cette methode developpee par Biryukov, De Canniere et moi-meme et publiee a la conference Crypto 2004. Nous terminerons par un bref rappel de theorie de Fourier et nous decrirons les criteres de conception induits par la cryptanalyse lineaire.

L'algorithme le plus efficace d'un point de vue complexité pour l'évaluation d'un polynôme est l'algorithme de Horner. On sait de plus qu'il est inverse-stable. Néanmoins, l'évaluation polynomiale peut être extrêmement mal conditionnée ; c'est le cas par exemple lorsque l'on se situe près d'une racine multiple. Or évaluer un polynôme de manière précise peut être une tâche cruciale par exemple pour le critère d'arrêt des méthodes itératives de type Newton pour la recherche de zéros. Les solutions existantes utilisent toutes des bibliothèques multiprécisions qui permettent d'augmenter la précision des calculs mais souvent au prix d'un surcoût très élevé.
Nous proposons un algorithme de Horner compensé qui permet d'évaluer de façon précise et rapide un polynôme à coefficients flottants. La précision du résultat calculé est similaire à celle donnée en effectuant l'évaluation classique par le schéma de Horner avec une précision double de la précision courante. Notre algorithme est deux fois plus rapide que les implémentations existantes donnant la même précision pour le résultat. Nous présentons aussi un algorithme pour calculer en arithmétique flottante IEEE 754 une borne d'erreur certifiée. Par certifiée, on entend que la borne calculée majore effectivement l'erreur de l'évaluation par l'algorithme de Horner compensé. Des expérimentations avec des polynômes très mal conditionnés illustrent ces résultats théoriques. Nos algorithmes n'utilisent qu'une seule précision courante et sont portables si l'on suppose que l'arithmétique flottante est conforme au standard IEEE 754.

résumé en anglais

Cet exposé traitera de l'analyse de la complexité moyenne (nombre d'itérations, complexité en bits) d'algorithmes de pgcd sur les entiers. Les premiers travaux dans ce domaine remontent aux années 70, avec les premières analyses de l'algorithme d'Euclide par Dixon et Heilbronn, puis les analyses de ses variantes par Knuth et Yao, Brent, Rieger. Depuis une dizaine d'année s'est développée autour des travaux de Brigitte Vallée une technique efficace d'analyse de tels algorithmes, l'analyse dynamique, basée sur une modélisation des algorithmes en systèmes dynamiques. L'avantage de cette méthode est qu'elle permet de remplacer l'étude analytique de séries génératrices (difficile dans ce contexte) par l'étude spectrale d'un opérateur de transfert, outil classique en théorie des systèmes dynamiques. Je présenterai donc cette méthode d'analyse que j'illustrerai par des résultats récents qu'elle a permis d'obtenir. Je parlerai dans un premier temps de l'analyse de l'algorithme d'Euclide interrompu : on étudie l'évolution des principales grandeurs (quotients, tailles des restes) au cours de l'exécution de l'algorithme. Cette étude permet en outre d'obtenir des résultats interessants sur les versions accélérées de l'algorithme d'Euclide (algorithmes de Lehmer-Euclide, Knuth-Schönhage). Puis je présenterai l'analyse en moyenne de l'algorithme LSB, mis au point et utilisé par Stehlé et Zimmermann dans leur algorithme rapide de calcul de pgcd. L'analyse de cet algorithme diffère des analyses classiques, puisqu'elle fait appel à des argument issus de la théorie de produits de matrices aléatoires. Les différents résultats présentés ici ont été obtenus en collaboration avec Brigitte Vallée, Véronique Maume-Deschamps et Loïck Lohte.

TBA

Les protocoles de cryptographie à clé publique utilisent des opérateurs arithmétiques sur des corps (ECC) ou des anneaux (RSA). De nombreuses classes de moduli offrent des propriétés intéressantes pour effectuer cette arithmétique modulaire: les nombres de Mersenne, les pseudo nombres de Mersenne, les nombres de Mersenne généralisés... Dans ce contexte, nous proposons un nouveau système de représentation. Celui ci est adapté à l'arithmétique modulaire. Après analyse de ce système, nous proposons deux axes d'utilisation de ce système de représentation modulaire. Dans un premier temps, une nouvelle classe de moduli peut être créée à partir de ce système de représentation. Cette classe est à la fois efficace et suffisamment dense pour répondre aux contraintes d'utilisation des protocoles d'ECC. Dans un second temps et à partir de la théorie des réseaux euclidiens, nous présentons un théorème d'existence de représentation faiblement redondante dans ce système. C'est à partir de ce théorème que nous proposons différentes solutions à des problèmes classiques de l' arithmétique modulaire, pour le protocole RSA entre autre.

Les fonctions booléennes symétriques sont les fonctions dont la valeur ne dépend que du poids du vecteur d'entrée. Ces fonctions peuvent être représentées plus simplement, que ce soit par leur forme algébrique normale ou leur vecteur des valeurs, que des fonctions booléennes générales --- vecteurs de taille (n+1) contre des vecteurs de taille 2^n en général. En outre, ces fonctions ont une complexité en nombre de portes qui est linéaire en le nombre de variables d'entrées [Muller_Preparata75]. Ces qualités en font par exemple, des candidates potentielles comme fonctions de filtrage dans un chiffrement à flot. C'est pourquoi une étude systématique des propriétés cryptographiques de ces fonctions est nécessaire. Des résultats concernant la non-linéarité maximale des fonctions booléennes symétriques sont connus [Savicky 1994, Maitra-Sarkar 2002], ainsi que des familles infinies de fonctions symétriques sans correlation et résilientes [Gopalakrishnan-Hoffman-Stinson 1993, von zur Gathen-Roche 1997, Maitra-Sarkar 2003]. L'étude que nous présentons (travaux en commun avec Anne Canteaut) est basé sur un théorème qui établit un lien entre le degré algébrique des fonctions symétriques et la périodicité de leur vecteur des valeurs simplifié (vecteur des valeurs prises pour les différents poids des vecteurs d'entrée). Ce théorème nous a permis d'explorer de manière systématique différentes propriétés cryptographiques (non-linéarité, résilience, critère de propagation) et d'établir plusieurs nouveaux résultats pour ces fonctions. Par ailleurs, le calcul explicite du spectre de Walsh des fonctions booléennes symétriques de degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les fonctions symétriques équilibrées de degré inférieur ou égal à 7, indépendamment du nombre de variables.

résumé en anglais

Le calcul de polynômes de classe est l'étape principale dans la construction de courbes elliptiques par la méthode de la multiplication complexe. Ces courbes peuvent servir comme base de cryptosystèmes, dans les preuves de primalité ou pour tricher dans la chasse au record de factorisation avec ECM. Je donne la complexité des algorithmes usuels pour calculer ces polynômes, ainsi qu'un algorithme asymptotiquement optimal, mais pratiquement lent.

résumé en anglais

Je vais essayer de présenter quelques aspects de la récente preuve en Coq du théorème des quatre couleurs. En particulier de l'exploitation de résultats calculatoires à l'intérieur du raisonnement mathématique.

En 1998 Thomas Hales a annoncé d'avoir prouvé la conjecture de Kepler. Sa preuve s'appuie sur des inégalités dans les nombre réels, qui sont vérifiées par des algorithmes d'optimisation. Ces méthodes se basent sur l'arithmétique d'intervalles avec certains raffinements: prise en compte de monotonies, considération du gradient etc. Une formalisation (encore partielle) de ces algorithmes est présentée. Elle se sert des nombres réels (représentés comme suites de Cauchy) comme bornes d'intervalles et évite ainsi les problèmes d'arrondi, indispensable pour le développement de preuves formelles. Le but ultime de ce travail est de prouver toutes les inégalités surgissant dans la preuve de Hales.

Les signatures numériques classiques ont la propriété, parfois indésirable, d'être universellement vérifiables par toute personne possédant la clé publique du signataire. Récemment, en collaboration avec F. Laguillaumie et P. Paillier, nous avons proposé des signatures dont la vérification ne peut s'effectuer sans interaction avec le signataire. La sécurité de ces signatures repose sur la difficulté présumée de la variante « xyz » du problème Diffie-Hellman classique. Dans cet exposé, nous présenterons le problème algorithmique dans son contexte cryptographique et nous donnerons des arguments en faveur de sa difficulté (sécurité générique, sécurité sur les bits, ...)

Sur le corps des complexes, une courbe de genre g est isomorphe à un tore à g trous, i.e., à un quotient de la forme C^g/(Z^g.1⊕Z^g.τ) où τ est une matrice g×g appelée matrice de Riemann.

Dans le cas du genre g=1, le calcul de τ à partir de l'équation d'une courbe elliptique est l'une des applications classiques de la moyenne arithmético-géométrique (AGM), que l'on peut interpréter en considérant des fonctions appelées theta constantes.

Nous montrons comment tout ceci peut se transposer au genre supérieur en considérant une généralisation de l'AGM connue sous le nom de moyenne de Borchardt.

En particulier, nous donnons un algorithme permettant le calcul de matrices de Riemann en genre 2 en temps quasi-linéaire, algorithme particulièrement simple à implanter.

Nous montrons aussi comment ces techniques permettent d'évaluer rapidement des formes et fonctions modulaires, en genre 1 et en genre 2, et nous discutons des applications (constructions de courbes CM, calculs explicites d'isogénies, …).