Crible d'Ératosthène
En rayant. On écrit les entiers, on garde 2, on barre tous ses multiples ; le premier nombre non barré qui suit est premier à son tour, et l'on recommence. Aucune division, aucun test : seulement des additions répétées et une liste qui se vide.
En rayant. On écrit les entiers, on garde 2, on barre tous ses multiples ; le premier nombre non barré qui suit est premier à son tour, et l'on recommence. Aucune division, aucun test : seulement des additions répétées et une liste qui se vide.
Si un nombre inférieur à n est composé, il possède un facteur inférieur ou égal à la racine de n : deux facteurs plus grands donneraient un produit trop gros. Le reste de la liste est premier.
Cribler jusqu'à un entier suppose de garder la liste de tous ceux qui le précèdent. Les modules RSA font plus de six cents chiffres : cette liste dépasserait de très loin le nombre d'atomes de l'univers observable. On tire donc les grands nombres premiers au hasard et on les teste un par un, par des méthodes probabilistes comme celle de Miller et Rabin.