Concept

Crible d'Atkin

Résumé
Le crible d'Atkin est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. C'est une version améliorée du crible d'Ératosthène, il fut créé en 1999 par A. O. L. Atkin et Daniel J. Bernstein. Le crible d'Ératosthène consiste à trouver les valeurs pouvant se réduire à la forme quadratique binaire réduite x⋅y (produit de deux entiers strictement supérieurs à 1). Le crible d'Atkin consiste lui à dénombrer les valeurs d'une forme quadratique binaire non-réduite. Par exemple, un entier sans facteur carré p qui est congru à 1 modulo 4 est premier si et seulement si l'équation 4x + y = p admet un nombre impair de solutions positives (x, y). Quelques variables sont nécessaires : le tableau des nombres premiers que l'on a trouvés, que l'on initialise avec les nombres premiers inférieurs à soixante ; trois tableaux contenant les nombres qu'il reste à tester, selon le reste dans la division euclidienne par soixante ; ils sont initialisés avec tous les entiers entre soixante et le dernier nombre qui nous intéresse, tel que le reste modulo soixante est dans l'une de ces trois listes (on ne considère que les restes premiers avec 60) : reste valant 1, 13, 17, 29, 37, 41, 49, ou 53, reste valant 7, 19, 31, ou 43, reste valant 11, 23, 47, ou 59. Après, pour chaque nombre n restant : dans la première classe, on compte le nombre de couples x > 0 et y > 0 solutions de 4x2 + y2 = n ; dans la deuxième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x2 + y2 = n ; dans la troisième classe, on compte le nombre de couples x > 0 et y > 0, avec x > y, solutions de 3x2 – y2 = n ; si le compte est pair, on supprime n de la liste. Ensuite, on applique un crible d'Ératosthène modifié : pour chaque nombre premier p supérieur à 7, on supprime tous les multiples de p2. Enfin, on place les nombres restants dans la liste des nombres premiers. Avec cet algorithme, la recherche des nombres premiers inférieurs à N a une complexité en temps en o(N) et une complexité en mémoire en O(Nα) avec α < 1.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (6)
Concepts associés (1)
Crible d'Ératosthène
Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. Le crible d'Atkin est plus rapide mais plus complexe. L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même). En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.
Cours associés (2)
MATH-521: Advanced analytic number theory
We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes
MATH-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC