Mathématiques : Le Crible d’Ératosthène pour optimiser la recherche des nombres premiers
Français
Harald Andrés Helfgott est chargé de recherche au CNRS et à l’école normale supérieure à Paris et il propose d’utiliser une version modifiée du Crible d’Ératosthène pour optimiser la recherche des nombres premiers.
Suivez-nous sur notre page Facebook et notre canal Telegram
Les mathématiciens sont toujours obsédés par les nombres premiers. On distingue différentes méthodes pour les trouver, mais les ressources nécessaires deviennent de plus en plus importantes. Développé par Ératosthène de Cyrène, un mathématicien grec et un astronome aux environs de 240 avant l’ère commune et qui est connu pour avoir calculé la circonférence de la Terre, le crible d’Ératosthène permet de déterminer tous les nombres premiers entre certains ensembles de chiffres.
Pour faire fonctionner le crible, vous devez écrire une fourchette de nombres telle que 1 à 100 en ordre numérique et vous les croisez dans un certain ordre. Les multiples de 2 sauf le chiffre 2, les multiples de 3 sauf le chiffre 3 et ainsi de suite. Et vous commencez toujours le prochain chiffre avec celui qui n’a pas encore été croisé. Les nombres qui survivront dans ce crible seront tous des nombres premiers. Une méthode archaïque comparée aux procédures actuelles, mais Helfgott estime qu’on peut en faire un algorithme qui permet de trouver des nombres premiers en économisant la puissance de calcul.
Helfgott est surtout connu pour avoir proposé une preuve de la conjecture faible de Goldbach en 2013. Et c’était pendant ses travaux sur cette conjecture qu’il a commencé à penser au crible d’Ératosthène. Pour déterminer l’efficacité d’un algorithme de recherche de nombres premiers, on doit considérer 2 facteurs. Le nombre d’opérations par bit et le nombre de bits stocké dans la mémoire pendant l’exécution des instructions. Pour le premier facteur, le crible d’Ératosthène est assez efficace. Mais si on lui donne de grands ensembles de nombres, alors la consommation de mémoire crève le plafond et l’algorithme n’est plus efficace.
Mais Helfgott s’est inspiré d’une technique de calcul analytique appelé la méthode du cercle pour que le crible d’Ératosthène fonctionne avec peu de mémoire. En termes mathématiques, plutôt que d’utiliser un espace N, le crible utilise la racine cubique de N. Selon Helfgott, pour calculer tous les nombres premiers jusqu’au trillion, la version modifiée du crible nécessite quelques millions de bits au lieu de milliards de bits. Les principales idées ont été présentées pendant le XXI Latin American Colloquium of Algebra qui s’est tenu à Buenos Aires en juillet 2016.
Pour illustrer l’optimisation, on peut considérer que vous êtes un ordinateur et que vous utilisez des feuilles de papier pour stocker vos données en mémoire. Pour calculer les nombres premiers de 1 à 1 000 000, vous avez besoin de 200 rames de papier, soit 10 000 feuilles. Avec l’algorithme proposé par Helfgott, vous aurez besoin seulement d’un cinquième d’une rame, soit 100 feuilles de papier.
Même si cette optimisation sacrifie légèrement la vitesse, il est suffisamment performant pour qu’on compense la perte en utilisant la mémoire en cache plutôt que la RAM principale. Par rapport à d’autres méthodes pour trouver les nombres premiers, Helfgott ajoute que le crible d’Ératosthène peut être utilisé pour la factorisation. Cette dernière permet de décomposer n’importe quel nombre dans le produit des nombres premiers et c’est la base des méthodes de chiffrement.
Source : Scientific American
