Crible de primalité moderne qui utilise l'arithmétique modulaire et des conditions de résidus quadratiques pour identifier des candidats premiers jusqu'à une limite N, suivi d'un enlèvement des multiples de carrés pour conserver les premiers ; il peut être plus rapide que le crible classique pour de grandes limites optimisées.

Principe

Appliquer des règles fondées sur x^2 + y^2, 3x^2 − y^2 et 3x^2 + y^2 modulo de petits modules pour basculer les bits de candidatures des entiers satisfaisant certaines congruences, puis supprimer les multiples de carrés pour finaliser la liste des premiers.

Démonstration

Pour N ≤ 50 l'algorithme bascule des candidats selon de petites paires x,y satisfaisant les congruences quadratiques ; après basculements et suppression des multiples de carrés les restants incluent des premiers comme 5,7,11,13,17,19,23,29,31,37,41,43,47.

Mauvaise application

Implémenter les règles d'Atkin incorrectement (conditions de congruence erronées ou omission de la suppression des carrés), ou employer Atkin pour un N très petit où les frais généraux le rendent plus lent qu'Ératosthène.

Conséquence

Implémenté et paramétré correctement, Atkin peut offrir de meilleurs constantes asymptotiques et comportement cache pour de très grandes plages de criblage, produisant une liste de premiers correcte après suppression des carrés et validation.

Inversion

La réversion consiste à se fier uniquement au basculement des congruences sans l'étape finale d'élimination des carrés — on obtient alors de nombreux candidats pseudopremiers et une liste incorrecte.

Limite

Destiné à énumérer les premiers jusqu'à une grande borne N avec une implémentation soignée ; nécessite le traitement correct des conditions de résidus quadratiques et n'est pas avantageux pour de petites plages ou en présence d'une mauvaise localité mémoire.

Tension sémantique

Concurrence les variantes optimisées d'Ératosthène et les tests de primalité probabilistes ou déterministes ; Atkin met l'accent sur des règles de congruence arithmétiques qui peuvent réduire le travail mais impliquent une complexité d'implémentation et des coûts constants.

Synthèse

Atkin affine le criblage en utilisant des conditions quadratiques modulaires pour présélectionner des candidats puis en éliminant les multiples de carrés, offrant un crible théoriquement plus rapide pour de grands N lorsqu'il est implémenté avec optimisation.