CCIS Seminar - Thursday 9 February 2006 - salle A. Turing CE4
11:00:00 - Salle de salle A. Turing CE4

Jean-Guillaume Dumas, LJK

Racines primitives industrielles

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é.


Home page CCIS Seminars
How to come to salle A. Turing CE4 - http://www-verimag.imag.fr/Plan-d-acces.html?lang=fr