Séminaire du 24 février 03, François Morain, LIX, École polytechnique.

La primalité est dans P

Le problème de la primalité est l'un des problèmes les plus simples et les plus anciens de la théorie des nombres. Plus récemment, il a servi de cas d'école pour la théorie de la complexité. Ainsi, en 20 ans, le problème "est premier" a descendu toutes les classes de complexité, pour finalement arriver dans la classe P, avec les travaux d'Agrawal, Kayal et Saxena. L'exposé permettra de passer en revue les différentes méthodes développées, qu'elles soient théoriques ou pratiques.