Brun sieveIn the field of number theory, the Brun sieve (also called Brun's pure sieve) is a technique for estimating the size of "sifted sets" of positive integers which satisfy a set of conditions which are expressed by congruences. It was developed by Viggo Brun in 1915 and later generalized to the fundamental lemma of sieve theory by others. In terms of sieve theory the Brun sieve is of combinatorial type; that is, it derives from a careful use of the inclusion–exclusion principle. Let be a finite set of positive integers.
Principe d'inclusion-exclusionthumb|Exemple d'inclusion-exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion-exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d'une réunion finie d'ensembles finis en fonction du nombre d'éléments de ces ensembles et de leurs intersections. Il se généralise en termes de probabilités. Il est attribué au mathématicien Abraham de Moivre, et connu également (lui ou sa version probabiliste) sous le nom de formule du crible de Poincaré, formule de Poincaré, ou formule du crible.
Viggo BrunViggo Brun est un mathématicien norvégien né le à Lier et mort le à Drøbak. Il est essentiellement connu comme étant le créateur d'une méthode de crible (le ), inspirée de celle d'Ératosthène, mais plus puissante. Un des résultats célèbres de cette méthode est que la somme des inverses des nombres premiers jumeaux est convergente. En son honneur, on a défini la somme de cette série comme étant la constante de Brun. Théorème de Brun Viggo Brun, Le crible d'Eratosthène et le théorème de Goldbach, Kristiania,
Crible d'ÉratosthèneLe 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.
Nombres premiers jumeauxEn mathématiques, deux nombres premiers jumeaux sont deux nombres premiers qui ne diffèrent que de 2. Hormis pour le couple (2, 3), cet écart entre nombres premiers de 2 est le plus petit possible. Les plus petits nombres premiers jumeaux sont 3 et 5, 5 et 7, 11 et 13. En , les plus grands nombres premiers jumeaux connus, découverts en 2016 dans le cadre du projet de calcul distribué PrimeGrid, sont × 2 ± 1 ; ils possèdent chiffres en écriture décimale.
Théorème de ChenEn mathématiques, le théorème de Chen, démontré par Chen Jingrun, énonce que : « Tout entier pair suffisamment grand est la somme d'un nombre premier et d'un nombre premier ou semi-premier ( produit de deux nombres premiers). » Ce théorème entre dans le cadre général des résultats profonds motivés par la célèbre conjecture de Goldbach (tout entier pair supérieur à 3 est somme de deux nombres premiers). Les démonstrations actuelles reposent essentiellement sur des méthodes de crible. Le résultat ci-dessus date de 1966.
Théorème de Brunvignette|ce schéma représente la théorie Le théorème de Brun énonce la convergence de la série des inverses des nombres premiers jumeaux. Sa somme est appelée constante de Brun. Autrement dit la somme (où désigne l'ensemble des nombres premiers) est finie. Le mathématicien norvégien Viggo Brun restera dans les mémoires comme étant l'inventeur des méthodes modernes de cribles combinatoires. Entre 1917 et 1924, il inventera et perfectionnera cette théorie, dont le principe repose sur le crible d'Ératosthène.
Crible algébriqueEn théorie des nombres, l'algorithme du crible du corps de nombres généralisé (GNFS) obtient la décomposition d'un entier en produit de facteurs premiers. C'est à l'heure actuelle (2018) l'algorithme le plus efficace connu pour obtenir cette décomposition, lorsque le nombre considéré est assez grand, c'est-à-dire au-delà d'environ 10100, et ne possède pas de structure remarquable. Cette efficacité est due pour partie à l'utilisation d'une méthode de crible et pour partie à l'utilisation d'algorithmes efficaces pour certaines opérations (comme la manipulation de matrices creuses).
Crible quadratiqueL'algorithme du crible quadratique est un algorithme de factorisation fondé sur l'arithmétique modulaire. C'est en pratique le plus rapide après le crible général des corps de nombres, lequel est cependant bien plus compliqué, et n'est plus performant que pour factoriser un nombre entier d'au moins cent chiffres. Le crible quadratique est un algorithme de factorisation non spécialisé, c'est-à-dire que son temps d'exécution dépend uniquement de la taille de l'entier à factoriser, et non de propriétés particulières de celui-ci.
Crible de Selbergvignette| Atle Selberg En mathématiques, et plus précisément en théorie des nombres, le crible de Selberg est une technique permettant d'estimer la taille des "ensembles criblés" d'entiers positifs qui satisfont à un ensemble de conditions qui sont exprimées par des congruences. Il a été développé par Atle Selberg dans les années 1940. En termes de théorie des cribles, le crible de Selberg est de type combinatoire : c'est-à-dire qu'il découle d'une utilisation subtile du principe d'inclusion-exclusion .
