|
||||||||||||||||||||||||||||||||||||||||||||||||||
|
CRIBLE d'ATKIN Critère
de primalité, alternative au crible
d'Ératosthène. Méthode
qui fait appel à des propriétés avancées de la théorie des nombres.
Application d'une forme du second
degré selon le reste de la division par 12. Utilisation de formes quadratiques en arithmétique
modulaire à base 12. Créé
par A.O.L. Atkin et Danile J. Bernstein autour de l'an 2000. |
|
|
||
|
Le crible
d'Ératosthène élimine rapidement tous les nombres pairs, puis les multiples
de 3, etc. Le crible
d'Atkin est plus puissant en allant chercher des propriétés des nombres au
plus profond de la théorie des nombres. |
Principe Selon le reste de la division par k, examen d'une
forme quadratique en x²
et y². La quantité de telles formes égalant n est un
signe de la primalité de n. Le crible se décline en l'application de trois
théorèmes. |
|
|
|
||
|
THÉORÈME 1 Si n est un entier positif sans facteur carré et
tel que le reste de la division par 4 est 1,
alors n est premier si et seulement si la
quantité de formes quadratiques 4x² + y² = n est impaire avec x et y
positifs. |
|
|
Explications
|
Formulation du théorème par Atkin et Bernstein
Squarefree integer: nombres sans
facteur carré, qui ne contient aucun facteur premier répété (cad. avec un
exposant 2 ou plus). 1 + 4Z indique tous
les nombres du type 4k + 1, nombres qui divisés par 4 ont un reste de 1. Ssi si et seulement si (iff :if and only if). # est le symbole indiquant la
quantité des éléments (ou cardinal). On considère les couples x et y, nombres
positifs, tels que la somme
quadratique 4x² + y² est égal à n. Si la quantité de telles sommes est
impaire, alors le nombre n est premier. La réciproque est vraie aussi: un
nombre premier sans facteur carré de la forme 4k + 1 induit une quantité
impaire de formes quadratique 4x² + y² = 1. Exemples
Démonstration La démonstration est du niveau expert en théorie des nombres. Elle figure
dans le papier original d'Atkin et Berntsein. |
|
THÉORÈME 2 Si n est un entier positif sans facteur carré et
tel que le reste de la division par 6 est 1,
alors n est premier si et seulement si la quantité
de formes quadratiques 3x² + y² = n est impaire avec x et y
positifs. |
|
|
|
Exemples |
103 ≡ 1 mod 6 et 103 = 3×1² + 10²; Forme
unique; 103 est premier. 109 ≡ 1 mod 6 et 109 = 3×6² + 1² ; Forme unique; 109 est premier. |
|
|
THÉORÈME 3 Si n est un entier positif sans facteur carré et
tel que le reste de la division par 12 est 11,
alors n est premier si et seulement si la quantité
de formes quadratiques 3x² – y² = n est impaire avec x et y positifs
et x supérieur à y. |
|
|
|
Exemple |
107 ≡ 11 mod 12 et cinq formes quadratiques; 107 est premier. 107 = 3 × 6² – 1²
= 108 – 1 107 = 3 × 11² – 16² = 363 – 256 107 = 3 × 13² – 20² = 507 – 400 107 = 3 × 38² – 65² = 4332 – 4225 107 = 3 × 46² – 79² = 6348 – 6241 |
|
|
|
||
|
Les
théorèmes impliquent des calculs mod 4, 6, 12 et 60.
Tous les
nombres proposés par ces trois théorèmes sont des nombres premiers jusqu'à
60, sauf un intrus: 49 = 7². Ce qui montre qu'il faudra traiter le cas des nombres
avec des facteurs carrés. Le cycle
60 est justifié par le fait que tous les nombres jusqu'à 60 sont:
|
|
|
|
|
||
|
def CA(nmax): if nmax > 2: print(2, end=" ") if nmax > 3: print(3, end=" ") crible = [False] * nmax for i in range(0,
nmax): crible[i]
= False x = 1 while x * x < nmax: y = 1 while y * y < nmax: n =
(4 * x * x) + (y * y) if (n <= nmax and
(n % 12 == 1 or n % 12 ==
5)):
crible[n] ^= True n = (3
* x * x) + (y * y) if n <= nmax and
n % 12 == 7:
crible[n] ^= True n =
(3 * x * x) - (y * y) if (x > y and
n <= nmax and
n % 12 == 11):
crible[n] ^= True y += 1 x += 1 r = 5 while r * r < nmax: for i in range (r * r, nmax, r * r):
crible[i] = False r += 1 for a in range(5, nmax): if crible[a]: print(a, end=" ") # Principal nmax = 130 CA(nmax) |
But Éditer la liste des nombres premiers jusqu'à nmax en utilisant le crible d'Atkin. Commentaires Fonction CA
comme Cible Atkin. Si nmax est
supérieur à 3 imprimer 2 et 3 chacun suivi d'un espace (end). Crible est une liste binaire
que l'on initialise avec des valeurs "fausses", autant que nmax. Balayage en x et
en y pour identifier les formes
quadratiques dans chacun des cas de résidu. La valeur de la forme est n. Si n est dans la zone des nombres à explorer et si son
modulo (%) 12 vaut (==) 1 ou 5, alors l'emplacement numéro n dans
crible est modifié. S'agissant de valeurs binaires, la modification
consiste à faire un OU
exclusif (^=) entre la valeur dans
crible et la valeur vraie (True)*. Si la
valeur est fausse, elle devient vraie et si elle est vraie, elle devient
fausse. Soit une inversion (flip en
anglais). * Voir Opérateurs d'augmentation
en Python Idem pour les deux autres formes. Le module suivant (r
= 5, …) identifie les nombres avec
carrés et les élimine (aussi bine 5² que 5² × 7, etc.). On
commence à 5 et on termine avant racine de nmax. Jusqu'à présent on dispose d'une liste de nmax
valeurs binaires témoignant du fait que le nombre est premier ou composé (True or False). Le module suivant va identifier les valeurs
vraies, les convertir en nombres et les imprimer. Notez que la condition est
vérifiée avec la valeur vraie implicite (pas besoin de la spécifier). Résultat 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61
67 71 73 79 83 89 97 101 103 107 109 113 127 Programme inspiré de celui produit par Geeksforgeeks |
|
Voir Crible d'Ératosthène avec
Python / Crible de la roue avec Python
|
|
|||
|
|
But Éditer la liste des nombres premiers jusqu'à nx en utilisant le crible d'Atkin. Commentaires Initialisation. Requête pour les 1000 plus petits
nombres premiers en nx. Déclaration d'un vecteur de tailla 1000, rempli
avec la valeur "false". On utilise un vecteur plutôt qu'une liste
du fait de la taille. Balayage en x et
en y pour identifier les formes
quadratiques dans chacun des cas de résidu. La valeur de la forme est n. Si n est dans la zone des nombres à explorer et si son
modulo (mod) 12 vaut (=) 1 ou 5, alors l'emplacement numéro n dans
crible est modifié. S'agissant de valeurs binaires, la modification
consiste à faire un OU
exclusif (xor) entre la valeur dans
crible et la valeur vraie (true). Si la
valeur est fausse, elle devient vraie et si elle est vraie, elle devient
fausse. Soit une inversion (flip en
anglais). Idem pour les deux autres formes. Le module suivant (r
= 5, …) identifie les nombres avec
carrés et les élimine. On commence à 5 et on termine avant racine
de nmax. Jusqu'à présent on dispose d'une liste de nx
valeurs binaires témoignant du fait que le nombre est premier ou composé (true or false). Le module suivant va identifier les valeurs
vraies, les convertir en nombres et les imprimer. |
||
|
Résultat 168 nombres
premiers jusqu'à 1000 |
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907,
911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997}
168 |
||
|
Listing pour
copier coller dans Maple |
restart; nx := 100: S := array(1 .. nx, [false$nx]): x := 1: while x^2
< nx do y := 1: while y^2 < nx do n := 4*x^2+y^2; if n < nx and
(`mod`(n, 12) = 1 or `mod`(n, 12) = 5) then S[n] := `xor`(S[n], true) end if;
n := 3*x^2+y^2; if n < nx and `mod`(n, 12) = 7 then S[n] := `xor`(S[n],
true) end if; n := 3*x^2-y^2; if x > y and n < nx and `mod`(n, 12) = 11
then S[n] := `xor`(S[n], true) end if; y := y+1 end do: x := x+1 end do: r :=
5: while r^2 < nx do for i from r^2 by r^2 to nx do S[i] := false end do;
r := r+1 end do: SS := {2, 3}: for j to nx do if S[j] = true then SS := {j,
op(SS)} end if end do: SS; nops(SS); |
||
Voir Crible
d'Ératosthène avec Maple / Crible de la roue
avec Maple
Voir Programmation – Index
|
Voir |
|
|
Aussi |
|
|
|
|
|
Cette page |
