./12285> Faut voir, faut voir, si ça donne un truc en 10^100*n^(10^100), c'est certes polynomial, mais bon.... En tout cas ça motiverait les gens pour l'améliorer...

Il y a quelques années a été inventé l'algorithme AKS pour prouver en temps polynomial la primalité d'un entier, ce qui était une grande avancée théorique... Mais AKS n'était pas (et n'est toujours pas, je crois) compétitif par rapport aux meilleurs algorithmes non polynomiaux