Octobre 2009 Vendredi 16 octobre Zoubida Jadda (IRMAR) Nonlinéarité d’une classe de fonctions quaternaires et de fonctions booléennes Résumé Les fonctions booléennes de n variables à valeurs dans {0, 1} jouent un rôle important dans les protocoles de sécurité pour les générateurs pseudo- aléatoires des chiffrements par blocs et par flots. Trouver des fonctions booléennes avec des propriétés telles l’équilibrage ou une nonlinéarité optimale est un problème ouvert. Pour étudier ces propriétés, on va passer par l’intermédiaires des fonctions quaternaires de m variables à valeurs dans {0, 1, 2, 3}. On présente de nouveaux résultats sur ces fonctions quaternaires. On commence par donner une caractérisation des propriétés à partir de la fonction de walch et on définit formellement leur équilibrage et leur nonlinéarité sur Z4 . Une construction générale d’une classe de fonctions quaternaires est donnée à partir des classes cyclotomiques du groupe multiplicatif de l’anneau de Galois. Avec une configuration particulière, on obtient des fonctions quaternaires équilibrées avec une nonlinéarité bornée par 3.4^(m−1) − 2^m et 3.4^(m−1) − 2^(m −1) . En utilisant le gray map, on trouve des fonctions booléennes de 2m variables équilibrées avec une bonne nonlinéarité. Mots clés : Algèbre quaternaire, anneaux de Galois, fonctions booléennes, fonctions quaternaires, Gray map, nonlinéarité Novembre 2009 Vendredi 6 novembre Lionel Ducos (Poitiers) Utilisation d'outils constructifs dans une étude de la dimension de Krull des anneaux commutatifs. Introduction / Résumé La définition classique de la dimension de Krull fait intervenir pleinement l'ensemble des idéaux premiers d'un anneau commutatif. Or, dans le cadre général des anneaux commutatifs, l'existence d'un idéal premier repose sur l'axiome du choix. Mais cet axiome n'est pas admis dans la logique intuitionniste... Cela étant, nous donnerons une caractérisation constructive de la dimension de Krull d'un anneau, en ne faisant intervenir uniquement que des expressions polynomiales des éléments de l'anneau. Nous pourrons aborder quelques applications, notamment un théorème de Kronecker sur les idéaux radicalement de type fini ; le théorème <<stable range>> de Bass dans une version non noethérienne ; le théorème de transfert aux extensions entières ; une généralisation du théorème de l'idéal principal de Krull ; la dimension graduée des anneaux gradués... Vendredi 13 novembre, exceptionnellement à 10h45 André Leroy (Lens) Applications polynomiales non commutatives. Résumé. On survolera quelques thèmes relatifs aux apllications polynomiales associées aux polynômes de Ore. Voici quelques sujets qui seront abordés:    1. Evaluation d'un produit    2. Nombres des zéros d'un polynôme gauche    3. Transformations pseudo linéaires    4. Polynômes de Wedderburn et leurs applications    5. Factorisations    6. Autres applications Mars 2010 Vendredi 5 mars Yann Laigle-Chapuy (INRIA Rocquencourt) Polynômes de permutation Résumé L'étude  des  polynômes de  permutation  a  été  fortement relancée  grâce  aux application  possibles  en  cryptographie.  Dans cet  exposé  nous  rappelerons quelques  résultats  généraux  avant  de  nous  concentrer  sur  deux  familles particulières, les polynômes de la forme  $XL(X)$ et $L(X)/X$ où $L$  correspond à  une application  linéaire.  Nous verrons  dans quelle  cadre cryptographique ces familles apparaissent  avant d'énoncer nos résultats. Enfin nous présenterons quelques conjectures et problèmes ouverts. Vendredi 26 mars (en commun avec le séminaire de géométrie analytique) Alexey Ovchinnikov (City University of NY) Galois theory with difference parameters Abstract We the work of Dima Trushin on difference Nullstellensatz for difference closed pseudofields to construct a Galois theory of difference equations with difference parameters. Existing Galois theories for difference and differential equations with differential parameters developed by Cassidy, Singer, and Hardouin are based on differentially closed fields. Our results complement their work. Moreover, in our case difference closed fields are not a valid substitute due to their lack of quantifier elimination. To overcome this we are using difference simple rings that are products of fields (called pseudofields) instead. Avril 2010 Vendredi 2 avril (en commun avec le séminaire de cryptographie) Alain Couvreur (École Polytechnique, Laboratoire LIX) Paramètres des codes géométriques sur les surfaces et produit d'intersection. Résumé: En 1981, Goppa propose une construction de codes correcteurs d'erreurs à partir de courbes algébriques. Ces codes dits "géométriques" s'avèrent extrêmement performants et connaissent un succès remarquable depuis leur découverte. Si la construction de Goppa a rapidement été étendue aux variétés de dimension quelconque, les codes issus de variétés de dimension supérieure à 2 n'ont été que très rarement étudiés, essentiellement du fait des nombreuses difficultés que présente l'estimation de leurs paramètres. Dans cet exposé, après avoir rappelé quelques notions élémentaires de la théorie des codes sur les courbes, nous présenterons une méthode d'estimation des paramètres du dual d'un code géométrique sur une surface. Cette méthode combine théorie de l'intersection sur les surfaces et comptage de points rationnels de courbes sur des corps finis. Vendredi 9 avril, exceptionnellement, deux séminaires à 10h30 et à 15h 10h30 Guillaume Moroz (IRCCyN, Nantes) Calcul formel et géométrie réelle pour la robotique Résumé: Les mécanismes robotiques se modélisent naturellement par des systèmes d'équations et d'inégalités polynomiales. Dans le cadre de la conception de robots, on est intéressé par classer des familles paramétrées de mécanismes en fonction de propriétés géométriques. On montrera comment la variété discriminante combinée à la décomposition cylindrique algébrique permet d'obtenir des réponses à cette question. 15h00   (en commun avec le séminaire de cryptographie) Nicolas Gama (GREYC ENSICAEN) Résolution exacte du SVP par Extreme pruning (travail commun avec Phong Nguyen et Oded Regev) Resumé: Le problème du plus court vecteur (SVP), et aussi celui du plus proche vecteur (CVP) d'un réseau euclidien sont deux problèmes NP-difficiles, et sur lesquels la sécurité de nombreux cryptosystèmes se réduit instantanément. Dans cet exposé, nous étudions une méthode probabiliste pour résoudre exactement et en pratique ces problèmes, et qui repose sur l'énumération de points entiers dans des sphères et cylindres de grande dimension. Cet algorithme, bien qu'ayant asymptotiquement une complexité temporelle en 2^O(n2) et O(n2) en mémoire, s'avère bien plus rapide que les algorithmes basés sur un crible (souvent simplement exponentiels en temps mais aussi en mémoire). L'algorithme que nous présentons est une variante de l'algorithme de recherche exhaustive de Schnorr-Euchner, dans lequel l'arbre de recherche exhaustive a été élagué de très près, de sorte qu'il ne reste qu'une partie infinitésimale de l'arbre initial. Nous montrons que la probabilité que le plus court vecteur appartienne toujours à l'arbre élagué diminue bien plus lentement que la taille de l'arbre, ce qui représente un compromis temps-de-calcul/probabilité de succès plus que favorable. Par ailleurs, nous montrons comment une randomisation des entrées permet de compenser la faible probabilité de succès intrinsèque de l'algorithme sus-mentionné, et de de résoudre le SVP et le CVP dans n'importe quel réseau, et ceci en utilisant une approche MIMD ultra-parrallèle. Mai 2010 Lundi 3 mai - Vendredi 7 mai Journées nationales de calcul formel (JNCF) au CIRM Juin 2010 Mardi 1er juin, 10h30, en salle 4 Dima Grigoriev (Lille 1) Séries de Newton-Puiseux pour D-modules non-holonomes et factorisation Vendredi 4 juin Michel Coste (IRMAR) Evitement des singularités pour des robots parallèles plans