Accueil Prime I.T.

Les nombres premiers

Un nombre premier est un entier naturel qui ne se divise que par 1 et par lui-même.
Grâce à cette propriété mathématique, ces nombres sont à la base de la cryptographie moderne et sont souvent utilisés en informatique afin de rendre nos messages illisibles aux personnes extérieures et ainsi garder confidentiel tous "nos petits secrets" qui transitent de main en main (comme par exemple l'envoi du mot de passe de notre site réseau social préféré ou encore l'ordre de paiement entre le commerçant et la banque).

Mais comment trouver tous les nombres premiers compris entre 1 et N ?

Un des grands jeux mathématique et algorithmique est de trouver un maximum de ces nombres. Certains le font pour "la beauté du jeu et de l'esprit", d'autres pour les étudier car il reste encore beaucoup de questions sur ces nombres. C'est d'autant plus important qu'il faut s'assurer que la cryptographie basée sur les nombres premiers n'est pas cassable et que l'on ne retrouvera pas "nos petits secrets" dans la nature.
Il est à noter qu'il existe une infinité de nombres premiers, ci-dessous le nombre de nombre premier (Pi) jusqu'à 1 milliard pour se donner une idée :

Par test de primalité

Il existe plusieurs méthodes pour calculer une plage de nombres premiers entre 1 et N. L'une, relativement naïve, consiste à parcourir tous les nombres un par un et de tester pour chacun d'entre eux si celui-ci est premier ou non grâce à un algorithme dit de "test de primalité".
Le plus connu de ces tests est le "trial division" qui consiste à essayer de diviser le nombre choisi par tous les nombres inférieurs à sa racine carré. Si aucun diviseur n'est trouvé alors ce nombre est premier. (note : voyez-vous pourquoi "inférieurs à sa racine carré" ? A vous de trouver...). Cet algorithme fait partie de la famille des tests de primalité déterministe qui permet de dire à coup sûr si le nombre est premier ou non lorsque l'algorithme est terminé.
Cette famille est à mettre en opposition avec les tests de primalité probabiliste qui indique si le nombre à tester "à de forte chance" d'être premier ou non, l'un des plus utilisé est l'algorithme de Miller-Rabin.
Au niveau de l'efficacité, les algorithmes probabilistes sont les plus rapide mais ils offrent une idée de la primalité du nombre et non ce qu'il est vraiment. Au final tous ces algorithmes ne sont pas "si rapides que ça" car ils servent à déterminer la primalité de manière ponctuelle (ce nombre que je choisis est-il premier ou non ?) mais sont peu efficace lorsqu'il s'agit de calculer des plages de nombre premier.

Par crible

Bien évidement il est possible de mixer les 2 familles pour essayer d'améliorer les performances mais il y a beaucoup plus efficace, il s'agit des algorithmes de crible.
Le but de ces algorithmes est d'appliquer un crible aux nombres, c'est à dire de discriminer les nombres à partir de leurs propriétés, leurs positions ou leurs relations et ainsi élaborer un algorithme "tamis" qui ne laissera passer que les nombres non premiers (les composites) et donc gardera que les premiers.
Le plus connu est le crible d'Eratosthène, non seulement il est rapide mais en plus il est facile à comprendre car il ne rentre pas dans des considérations mathématiques ardues.
Il existe d'autres cribles dont le crible d'Atkin qui est considéré comme une version améliorée d'Eratosthène. Cet algorithme a été conçu récemment (période 2000) mais ses concepts mathématiques commencent à devenir difficiles et très peu d'informations de vulgarisation circulent dessus.
Au niveau de l'efficacité, les algorithmes par crible sont plus efficaces par contre ils ont un point faible (il en faut bien un...) : ils sont gourmands en espace mémoire car au lancement du crible, le programme doit rassembler tous les nombres de la plage 1..N en mémoire avant de pouvoir lancer le "tamis".

Le site

Sur ce site vous trouverez :

• Une version en ligne (php) du crible d'Eratosthène permettant de calculer des plages de nombres premiers jusqu'à 1000 milliards (nombre à 12 chiffres).
• Une explication du crible d'Eratosthène ainsi que plusieurs implémentations java de l'algorithme (standard et optimisé) permettant de trouver tous les nombres premiers jusqu'à 100 milliards.
• Enfin quelques implémentations et pistes sur Atkin.

Attention à l'effet d'optique entre la version en ligne php et les versions java d'Eratosthène. La version en ligne semble donner 10 fois plus de nombre que la version java mais en réalité elle est moins puissante... Car elle ne donne au mieux que des plages de 600 nombres premiers tandis que la version java donne la totalité (de 1 à N).
Pour obtenir quelque chose d'équivalent, il faudrait cliquer environ 1 milliard de fois sur le bouton "next" de la version en ligne pour avoir tous les nombres premier jusqu'a 1000 milliards.
Cela prendrait 16 années si on considère que le temps d'affichage entre 2 pages web est de 0,5 sec... :)