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. 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). 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 4x2 + y2 = n ; dans la deuxième classe, on compte le nombre de couples x > 0 et y > 0 solutions de 3x2 + y2 = n ; dans la troisième classe, on compte le nombre de couples x > 0 et y > 0, avec x > y, solutions de 3x2 – y2 = 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 p2. Enfin, on place les nombres restants dans la liste des nombres premiers. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (6)

Concepts associés (1)

Cours associés (2)

Séances de cours associées (15)

Testing diﬀerent (e)DNA metabarcoding approaches to assess aquatic oligochaete diversity and the biological quality of sediments

Régis Lionel Vivien

Aquatic oligochaetes are important bioindicators of sediment quality in watercourses and lakes, but their morphological identiﬁcation to the species level is challenging and sometimes impossible. The use of DNA barcoding and metabarcoding could greatly fac ...

2019

Recherche de fragments de plastique dans les sédiments profonds du Léman

Luiz Felippe De Alencastro, Florian Faure

A growing number of studies focusing on microplastics (plastic particles smaller than 5 mm) show this issue affects all environmental matrices and compartments, and suspicions grow as to their toxicity. In this context, the Commission Internationale pour l ...

2017

Quadratic Sieving

Thorsten Kleinjung

We propose an efficient variant for the initialisation step of quadratic sieving, the sieving step of the quadratic sieve and its variants, which is also used in sieving-based algorithms for computing class groups of quadratic fields. As an application we ...

American Mathematical Society2016

Crible d'Ératosthène

Le crible d'Ératosthène est un procédé qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. Le crible d'Atkin est plus rapide mais plus complexe. L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de 2 à N tous les multiples d'un entier (autres que lui-même). En supprimant tous ces multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier à part 1 et eux-mêmes, et qui sont donc les nombres premiers.

MATH-521: Advanced analytic number theory

We will present the work of James Maynard (MF 2022) on the existence of bounded gaps between primes

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

Factorisation entière: Sieve Quadratic MATH-489: Number theory II.c - Cryptography

Couvre la méthode Quadratic Sieve pour la factorisation entière, soulignant l'importance de choisir les bons paramètres pour la factorisation efficace.

Calcul avec des séquences infinies CS-210: Functional programming

Introduit des listes paresseuses pour calculer des séquences infinies comme les nombres premiers.

Granulation de la suspension céramique par atomisation

Explore la granulation de la suspension céramique par l'atomisation et les processus connexes tels que le moulage par glissement et les mesures de densité.