salle A. Turing CE4
9 February 2006 - 11h00
Racines primitives industrielles
by Jean-Guillaume Dumas from 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é.
Slides of the Presentation.
