En admettant la conjecture de Dickson, nous démontrons que, pour chaque couple d’entiers $q\>0$ et $k\>0$, il existe une partie infinie $L_{q,k}\subset \mathbb{N}$ telle que, pour chacun des entiers $n\in L_{q,k}$ et tout entier $s$ tel que $0\<\left|s\right|\le q$, on ait $n+s=\left|s\right|t_1...t_k$ où $t_1\<...\<t_k$ sont des nombres premiers. De même, pour chaque couple d’entiers $q\>0$ et $k\>0$, il existe une partie infinie $M_{q,k}\subset \mathbb{N}$ telle que, pour chacun des entiers $n\in M_{q,k}$ et tout entier $s$ (nul ou non ) de l’intervalle $\left[-q,q\right]$, on ait $n+s=l{t}_1...t_k$ où $t_1\<...\<t_k$ sont des nombres premiers et l’entier $l$ appartient à l’intervalle $\left[1,2q+1\right]$. La lecture non standard...

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. À la fin des années 1970, Adleman, Pomerance et Rumely ont donné le premier algorithme de primalité déterministe, dont le temps de calcul était presque polynomial. Il a fallu 20 années supplémentaires pour qu’Agrawal, Kayal et Saxena donnent un algorithme déterministe de temps de calcul polynomial. L’exposé présentera ces travaux, et il fera également le point sur les différents autres...