Abstract FR:

L'usage des courbes elliptiques a grandement modifie les problemes de la factorisation et de la preuve de primalite (par opposition a la presomption de primalite fournie par les tests dits de pseudo-primalite). La notion de pseudo-premiers elliptiques generalise naturellement les pseudo-premiers classiques et nous montrons que les techniques de pomerance pour produire des pseudo-premiers forts se generalisent egalement pour produire des pseudo-premiers elliptiques. De plus, il est possible de generaliser la notion de pseudo-premiers elliptiques en un test complet, qui inclut plusieurs tests de pseudo-primalite et qui s'applique a tous les nombres possibles. Nous en deduisons une variante de l'algorithme d'atkin qui generalise les idees de adelman-pomerance-rumely et cohen-lenstra dans le cas elliptique. Toutefois ce test se revele assez lent en pratique et met ainsi en relief les problemes de strategie lors de l'attaque des grands nombres premiers