Crible d'Atkin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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'Atkins 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

4x2 + y2 = p

admet un nombre impair de solutions positives (x, y).

Algorithme[modifier | modifier le code]

Quelques variables sont nécessaires :

  • le tableau des nombres premiers que l'on a trouvé, que l'on initialise avec les nombres premiers inférieurs à soixante ;
  • trois tableaux contenant les nombres qu'il reste à tester, selon le restes 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é[modifier | modifier le code]

Avec cet algorithme, la recherche des nombre 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[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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