constante de Atkin

Pour trouver les nombres premiers jusqu'à une limite, on peut d'abord repérer des entiers qui apparaissent un nombre impair de fois dans certains calculs de carrés. Le crible d'Atkin utilise précisément ce signal : les expressions 4x² + y², 3x² + y² et 3x² − y² produisent des candidats selon leur reste modulo 12. Les multiples d'un carré sont ensuite retirés. Ainsi, 13 apparaît avec 4 × 1² + 3², tandis que 25 peut être sélectionné avant d'être éliminé parce que 25 = 5². Le mot « constante » du titre hérité ne désigne donc pas une valeur à calculer.

Le crible d'Atkin-Bernstein est un algorithme qui génère les nombres premiers inférieurs ou égaux à une borne N. Il commence par une table booléenne : chaque entier candidat est marqué ou démarqué selon la parité du nombre de représentations obtenues avec certaines formes quadratiques binaires. La parité signifie ici que l'on conserve un candidat lorsqu'il est représenté un nombre impair de fois, et qu'une nouvelle représentation inverse son état. Les trois tests usuels portent sur 4x² + y² lorsque le reste modulo 12 vaut 1 ou 5, sur 3x² + y² lorsqu'il vaut 7, et sur 3x² − y² lorsque x est strictement supérieur à y et que le reste vaut 11. Les entiers 2 et 3 sont traités séparément, puis les multiples des carrés de nombres premiers sont supprimés. La table restante fournit les nombres premiers jusqu'à N. Cette méthode doit son nom à A. O. L. Atkin et Daniel J. Bernstein ; elle n'est pas une constante et ne possède donc pas de valeur numérique éponyme à restituer.

Prenons la borne N = 30 et examinons deux entiers produits par les formes quadratiques. Les données sont : x = 1 et y = 3 pour le candidat 13 ; x = 2 et y = 3 pour le candidat 25 ; le nombre premier 5 sert à l'étape d'élimination des carrés.

Pour 13, la première forme donne 4 × 1² + 3² = 4 + 9 = 13.
Le reste de 13 dans la division par 12 est 1, donc 13 satisfait le test correspondant.
Pour 25, la même forme donne 4 × 2² + 3² = 16 + 9 = 25.
Le crible retire ensuite 25, car 25 = 5² est un multiple du carré du nombre premier 5.
Après ces deux décisions, 13 reste candidat et 25 ne l'est plus.

Le contrôle est direct : 4 × 1² + 3² vaut exactement 13, tandis que 4 × 2² + 3² vaut exactement 25 et que 5² vaut exactement 25. L'exemple montre pourquoi une sélection par forme quadratique ne suffit pas à elle seule : l'élimination des multiples de carrés est indispensable.

Pour construire une table de nombres premiers jusqu'à N, on initialise une table des entiers concernés, on parcourt les couples d'entiers positifs dont les formes quadratiques restent inférieures ou égales à N, puis on applique les tests de reste modulo 12. Chaque représentation retenue inverse l'état du nombre correspondant.

Une seconde passe parcourt les nombres premiers déjà reconnus et élimine leurs multiples de carrés. Cette étape est visible dans l'exemple : 25 a été sélectionné par une forme quadratique, mais disparaît parce qu'il est égal à 5². Le résultat est la liste des premiers jusqu'à N.

Le crible d'Ératosthène reste une alternative pratique pour une table modeste : il barre directement les multiples successifs des nombres premiers. Le choix dépend de l'implémentation, de la mémoire disponible et de la taille de N ; le nom « constante de Atkin » ne fournit aucun critère algorithmique.

Le crible d'Atkin ne doit pas être confondu avec le crible d'Ératosthène. Le critère qui les sépare est leur première opération : Atkin sélectionne des candidats par la parité de représentations dans des formes quadratiques, alors qu'Ératosthène élimine directement les multiples d'un nombre premier connu. Pour une table jusqu'à 30, le nombre 13 peut être sélectionné par 4 × 1² + 3² dans le premier procédé ; dans le second, il est conservé après les barrages déclenchés par 2, 3 et 5.

Il ne faut pas non plus confondre « constante de Atkin » avec une constante mathématique attribuée à Atkin. Le critère est testable dans une source ou un calcul : le terme standard désigne un crible, sans valeur fixe à mémoriser. Face à une demande de nombre ou de décimales, il faut corriger l'appellation et parler du crible d'Atkin.

Le test par formes quadratiques ne constitue pas, à lui seul, un certificat de primalité. Le symptôme est un entier comme 25, sélectionné par 4 × 2² + 3² mais égal à 5² ; il faut appliquer la passe qui retire les multiples des carrés de nombres premiers.

Les entiers 2 et 3 demandent un traitement séparé dans la formulation usuelle, car les tests de reste modulo 12 et les règles de balayage concernent surtout les candidats plus grands. Si cette initialisation manque, une table jusqu'à 30 peut omettre des nombres premiers valides ; il faut les ajouter selon la convention de l'algorithme.

La borne N est une limite de génération, pas une propriété du nombre premier. Une table construite jusqu'à 30 ne permet pas de conclure sur 31 ou sur un entier plus grand ; il faut relancer le crible avec une borne adaptée. Enfin, la notation « constante de Atkin » est un abus de libellé, non un cas numérique caché.

Pour approfondir le sujet, l'article de référence Prime sieves using binary quadratic forms présente le crible d'Atkin-Bernstein à partir des formes quadratiques binaires et de la parité du nombre de représentations. Il permet de passer de l'intuition des candidats sélectionnés à la justification mathématique des règles modulo 12, sans transformer le libellé hérité en constante inexistante.