Fabien Laguillaumie (GREYC)

Nous présentons un algorithme original de factorisation des entiers de la forme p q 2 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