Comment prouver qu'un entier n est premier en temps polynomial
en log n.
(Un exposé de Gilles Zémor au séminaire de théorie
des nombres de Chevaleret le 30 septembre 2002)
Résumé :
Agrawal, Kayal et Saxena ont tout récemment exhibé un algorithme
déterministe qui détermine en temps polynomial si un
entier est premier
ou non. Après avoir fait un tour d'horizon de ce qui était
connu
jusque là, nous détaillerons le résultat d'Agrawal
et al.