Nombre premier - liste de nombre premier

ANNEXE 1 Les Nombres Premiers : Ces nombres supérieurs à 1 divisibles uniquement par 1 et par eux même, jouent en cryptographie un rôle important, car ils sont à la base de la création de nombreuses clés. Nous allons donc étudier ici différents moyens d’en obtenir. 1. Le crible d’Eratosthène ( 276- 194 av. J.-C.): Pour obtenir tous les nombres premiers inférieurs à n, on va commencer par inscrire tous les entiers supérieurs à 1, et inférieurs à n. On va obtenir une liste commençant par 2. on retire tous les nombres étant divisibles par 2 sauf 2. Puis on passe au nombre suivant restant. On obtient 3. On retire de la liste tous les nombres divisibles par 3 sauf 3. Puis on passe au n nnombre suivant restant. 5 …..et ainsi de suite jusqu’à . Lorsque l’on a dépassé , tous les nombres restant dans la liste sont premiers. 2. Génération de nombres premiers : On choisit au hasard un nombre impair, et on le divise tour à tour par tous les nombres premiers inférieurs à sa racine. S’il n’est divisible par aucun d’entre eux, il est premier. Le problème de cette méthode est qu’il faut déjà chercher tous les nombres premiers inférieurs à la racine du nombre que l’on teste. 3. Génération de nombres pseudo-premiers : On choisit encore au hasard un nombre impair et on lui fait passer un test de primalité.