Non, tu n'as pas bien compris. Ce que l'on prouve, c'est qu'un nombre n'est pas premier.
Par contre, on n'a qu'une probabilité pour affirmer qu'un nombre est premier. Ce n'est pas symétrique.
Apparemment, le nouvel algorithme proposé permettrait de prouver qu'un nombre est premier, et donc de manière non probabiliste. Et en temps polynomial, ce qui est surprenant.
[^] # Re: Compléments
Posté par G. R. . En réponse à la dépêche Encore plus de Nombres Premiers. Évalué à 10.
Par contre, on n'a qu'une probabilité pour affirmer qu'un nombre est premier. Ce n'est pas symétrique.
Apparemment, le nouvel algorithme proposé permettrait de prouver qu'un nombre est premier, et donc de manière non probabiliste. Et en temps polynomial, ce qui est surprenant.