Nombre premier

Il existe une méthode simple pour trouver une liste de nombres premiers. C'est Eratosthène qui l'a créée. Elle porte le nom de Tamis d'Eratosthène. Il attrape les nombres qui ne sont pas premiers (comme un tamis) et laisse passer les nombres premiers.

La méthode fonctionne avec une liste de numéros, et un numéro spécial appelé b qui change au cours de la méthode. Au cours de la méthode, vous encerclez certains numéros de la liste et vous en rayez d'autres. Chaque nombre entouré est un nombre premier et chaque nombre barré est un nombre composite. Au début, tous les nombres sont simples : non encerclés et non barrés.

La méthode est toujours la même :

1. Sur une feuille de papier, écrivez tous les nombres entiers de 2 à celui qui est testé. N'écrivez pas le chiffre 1. Passez à l'étape suivante.
2. Commencez par un b égal à 2. Passez à l'étape suivante.
3. Encerclez b dans la liste. Passez à l'étape suivante.
4. En partant de b, comptez b de plus dans la liste et rayez ce chiffre. Répétez le comptage de b et le rature jusqu'à la fin de la liste. Passez à l'étape suivante.
• (Par exemple : Lorsque b est égal à 2, vous encerclez 2 et rayez 4, 6, 8, etc. Lorsque b est égal à 3, vous encerclerez 3 et vous rayerez 6, 9, 12, etc. 6 et 12 ont déjà été rayés. Rayez-les à nouveau).
5. Augmentez b de 1. Passez à l'étape suivante.
6. Si b a été rayé, retournez à l'étape précédente. Si b est un numéro de la liste qui n'a pas été rayé, passez à la 3ème étape. Si b n'est pas dans la liste, passez à l'étape finale.
7. (C'est la dernière étape.) Vous avez terminé. Tous les nombres premiers sont encerclés et tous les nombres composés sont barrés

A titre d'exemple, vous pourriez faire cette méthode sur une liste de numéros de 2 à 10. À la fin, les chiffres 2, 3, 5 et 7 seront encerclés. Ce sont des nombres premiers. Les nombres 4, 6, 8, 9 et 10 seront barrés. Ce sont des nombres composites.

Cette méthode ou algorithme prend trop de temps pour trouver de très grands nombres premiers. Mais elle est moins compliquée que les méthodes utilisées pour les très grands nombres premiers, comme le test de primalité de Fermat (un test pour voir si un nombre est premier ou non) ou le test de primalité de Miller-Rabin.

Les nombres premiers sont très importants en mathématiques et en informatique. Quelques utilisations dans le monde réel sont données ci-dessous. Les très longs nombres sont difficiles à résoudre. Il est difficile de trouver leurs facteurs premiers, donc la plupart du temps, les nombres qui sont probablement premiers sont utilisés pour le cryptage et les codes secrets.

• La plupart des gens ont une carte bancaire, où ils peuvent retirer de l'argent de leur compte, en utilisant un distributeur automatique. Cette carte est protégée par un code d'accès secret. Comme ce code doit être tenu secret, il ne peut pas être enregistré en clair sur la carte. Le cryptage est utilisé pour stocker le code de manière secrète. Ce cryptage utilise des multiplications, des divisions et la recherche de restes de grands nombres premiers. Un algorithme appelé RSA est souvent utilisé dans la pratique. Il utilise le théorème chinois du reste.

• Si quelqu'un possède une signature numérique pour son courrier électronique, le cryptage est utilisé. Cela permet de s'assurer que personne ne peut falsifier un courriel de cette personne. Avant la signature, une valeur de hachage du message est créée. Celle-ci est ensuite combinée avec une signature numérique pour produire un message signé. Les méthodes utilisées sont plus ou moins les mêmes que dans le premier cas ci-dessus.

• Trouver la plus grande prime connue jusqu'à présent est devenu une sorte de sport. Il peut être difficile de déterminer si un nombre est premier si le nombre est grand. Les plus grands nombres premiers connus à tout moment sont généralement des nombres premiers de Mersenne, car le test de Lucas-Lehmer, qui repose sur la forme spéciale des nombres de Mersenne, est le test de primalité le plus rapide connu. Un groupe qui recherche les nombres premiers de Mersenne se trouve ici [1].