n°3, mai 1997
Si l'on cherche des formules donnant des nombres premiers, les polynômes du deuxième degré sont les " candidats " les plus simples et les plus performants. Il est facile de démontrer qu'un polynôme ne peut pas donner comme valeurs uniquement des nombres premiers, et la recherche de polynômes performants devient une course aux records :
1. trouver un plus grand n pour lequel on puisse donner un polynôme F et un intervalle de n valeurs consécutives de X pour lesquelles F(X) soit premier ;
2. pour n fixé (les " classiques " sont n = 50, 100, 1000), trouver un polynôme F et un intervalle de n valeurs consécutives de X sur lequel un plus grand nombre de valeurs de F(X) soient premières, (il est en outre imposé que les nombres premiers obtenus soient tous distincts).
Le premier problème est célèbre depuis qu'Euler a donné en 1772 le polynôme X 2 + X + 41, qui fournit 40 nombres premiers pour 40 valeurs consécutives de la variable (X = 0, 1,..., 39). Le record est actuellement à 45 (Ruby, 1993), et il y a peu d'espoir de le battre. Le deuxième problème a donné lieu à de nombreux records successifs, où ont alterné les amateurs et les professionnels. À l'occasion de l'exposition mille et un chiffres organisée par Cap-Sciences, François Dress et Michel Olivier, du laboratoire d'Algorithmique Arithmétique eXpérimentale (A2X) de l'Université Bordeaux 1, ont battu en décembre 1996 le record du 50 et celui du 1000. Pour ce dernier, ils ont trouvé le polynôme X 2 + X -1 354 363 (698 valeurs premières sur 1 000) qui possède en outre, de façon générale pour cette catégorie de problèmes, des propriétés tout à fait remarquables.