| Résume | Soit $N$ grand. Comment peut-on trouver un nombre premier entre $N$ et $2N$?Comme les nombres premiers sont assez denses, et comme on peut v\'erifier laprimalit\'e d'un nombre rapidement, donner un algorithme probabilistepour trouver un nombre premier rapidement est une tache tr\`es facile. Maiscomment obtenir un algorithme d\'eterministe?Nous verrons qu'il y a un algorithme qui marche en temps$O(N^{1/3+\epsilon})$ -- si le nombre de nombres premiers entre $N$ et $2N$ estimpair, mais pas si il est pair![Issu d'un projet Polymath [collaboration massive]. Les participantsprincipaux \'etaient E. Croot, H. Helfgott et T. Tao] |
