Crible d'Atkin

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.

Stratégie

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).

Algorithme

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 4x² + y² = n ;
• dans la deuxième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x² + y² = n ;
• dans la troisième classe, on compte le nombre de couples x > 0 et y > 0, avec x > y, solutions de 3x² – y² = 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 p².

Enfin, on place les nombres restants dans la liste des nombres premiers.

Complexité

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.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sieve of Atkin » (voir la liste des auteurs).
• (en) A. O. L. Atkin et D. J. Bernstein, « Prime sieves using binary quadratic forms », Mathematics of Computation, vol. 73,‎ 1999, p. 1023-1030 (DOI http://dx.doi.org/10.1090/S0025-5718-03-01501-1, présentation en ligne).

Lien externe

(en) Primegen, par D. J. Bernstein (le crible d'Atkin optimisé en C)