627 results
-
Constructing elliptic curves by p-adic methods
Speaker : Peter Stevenhagen - University of Leiden
We will discuss a p-adic method to construct an elliptic curve over a finite field such that the group of rational points over the base field has some prescribed order N. The method uses ideas of Couveignes-Henocq, and is being developed and improved by my PhD student Reinier Broker. -
Hauteur des résultants toriques
Speaker : Martin Sombra - Université de Lyon I
Le résultant torique (ou creux) est un outil qui s'applique à la résolution des systèmes d'équations polynomiales. Ce fait a déclenché l'intérêt sur son calcul effectif; en même temps il est aussi étudié à cause de sa connexion avec les variétés toriques et les fonctions hypergéométriques.<br/> Dans cet exposé on présentera une borne pour la hauteur du résultant torique, définie comme le[…] -
Algebraic attacks and design of block ciphers, stream ciphers, and multivariate public key schemes
Speaker : Nicolas Courtois - Schlumberger
Following the famous 1949 paper of Shannon, breaking a "good" cipher should require: "as much work as solving a system of simultaneous equations in a large number of unknowns of a complex type". For most practical cryptosystems, the problem of recovering the key can indeed can be seen as solving a huge system of binary nonlinear equations. In general, solving such a problem is known to be NP-hard,[…] -
Un nouvel algortithme itératif rapide pour le PGCD de deux entiers
Speaker : Sidi Mohamed Sedeljmaci
Nous présentons un nouvel algorithme itératif pour le PGCD de deux entiers ou deux polynômes. Il est base sur une procédure itérative de type half-GCD qui évite la répétition d'appels récursifs. On procède progressivement a partir des bits de poids les plus forts. Quoique la complexité reste en $O(n \log2 n \log \log n$ pour deux entiers de $n$ bits, comme l'algorithme fameux de Schonhage, notre[…] -
Algorithme probabiliste d'Ajtai, Kumar et Sivakumar de recherche du plus court vecteur dans un réseau
Speaker : Damien Stehlé - INRIA Lorraine - ENS
Nous présenterons l'algorithme d'Ajtai, Kumar et Sivakumar pour résoudre le problème du plus court vecteur d'un réseau Euclidien. Ce problème a été prouvé NP-dur sous des réductions randomisées par Ajtai en 1996. Cet algorithme, présenté à STOC 2001, a une complexité probabiliste $2^O(n)$ en temps et en espace. Il bat donc la précédente borne de complexité ($n^{O(n)}$), qui correspond à l[…] -
Schémas de codage étendu pour canaux "wire-tap" et applications à l'identification biométrique
Speaker : Gilles Zémor - ENST
Un mécanisme traditionnel de mise en gage (commitment) consiste à publier $y=f(b)$ où $f$ est une fonction à sens unique et $b$ est un vecteur binaire destiné à rester caché jusqu'à ce qu'il soit révélé. La vérification que $f(b)=y$ empêche de révéler un vecteur différent de celui sur lequel on s'est engagé. Le problème d'une mise en gage {\em floue} (fuzzy commitment) se pose lorsqu'on souhaite[…]