salle A. Turing CE4
9 février 2006 - 11h00
Racines primitives industrielles
par Jean-Guillaume Dumas de LJK
Résumé : E. Bach, suivant une idée de T. Itoh, a montré comment établir un petit ensemble de nombres modulo un premier p tel qu'au moins un élément de cet ensemble est un générateur de Z/pZ*. E. Bach suggère également qu'au moins la moitié des éléments de son ensemble devrait être des générateurs. Nous prouvons ici que des variantes de cet ensemble peuvent en effet contenir un ratio de racines primitives arbitrairement près de 1. Nous dérivons ainsi plusieurs algorithmes calculant les racines primitives, correctes avec une probabilité très élevée, en temps polynomial. En application un nouveau test de primalité probabiliste compétitif avec celui de Miller-Rabin est proposé.
Les tranparents de la presentation.
