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, …).