Test de primalitévignette|Le 39e nombre premier de Mersenne découvert à ce jour pour un article sur la primalité Un test de primalité est un algorithme permettant de savoir si un nombre entier est premier. Le test le plus simple est celui des divisions successives : pour tester N, on vérifie s’il est divisible par l’un des entiers compris au sens large entre 2 et N-1. Si la réponse est négative, alors N est premier, sinon il est composé.
Nombre premiervignette|Nombres naturels de zéro à cent. Les nombres premiers sont marqués en rouge. vignette|Le nombre 7 est premier car il admet exactement deux diviseurs positifs distincts. Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs. Ces deux diviseurs sont 1 et le nombre considéré, puisque tout nombre a pour diviseurs 1 et lui-même (comme le montre l’égalité n = 1 × n), les nombres premiers étant ceux qui ne possèdent pas d'autre diviseur.
Test de primalité de Fermatvignette|Si le test de Fermat échoue, alors le nombre est composé. Si le test réussit, il y a de fortes chances que le nombre soit premier (illustration inspirée de , p. 30). En algorithmique, le test de primalité de Fermat est un test de primalité probabiliste basé sur le petit théorème de Fermat. Il est de type Monte-Carlo : s'il détecte qu'un nombre est composé alors il a raison ; en revanche, il peut se tromper s'il prétend que le nombre est premier.
Cryptographiethumb|La machine de Lorenz utilisée par les nazis durant la Seconde Guerre mondiale pour chiffrer les communications militaires de haut niveau entre Berlin et les quartiers-généraux des différentes armées. La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés. Elle se distingue de la stéganographie qui fait passer inaperçu un message dans un autre message alors que la cryptographie rend un message supposément inintelligible à autre que qui de droit.
Test de primalité AKSLe test de primalité AKS (aussi connu comme le test de primalité Agrawal-Kayal-Saxena et le test cyclotomique AKS) est un algorithme de preuve de primalité déterministe et généraliste (fonctionne pour tous les nombres) publié le par trois scientifiques indiens nommés Manindra Agrawal, Neeraj Kayal et Nitin Saxena (A.K.S). Ce test est le premier en mesure de déterminer la primalité d'un nombre dans un temps polynomial. Ce test a été publié dans un article scientifique intitulé « PRIMES is in P ».
RSA SecurityRSA Security est une entreprise inscrite au NASDAQ appartenant à EMC depuis le . Son siège social est à Bedford, au Massachusetts, et la société a des bureaux en Irlande, au Royaume-Uni, à Singapour et au Japon. RSA Security organise la conférence annuelle RSA Conference. Ses produits les mieux connus sont les bibliothèques cryptographiques B-SAFE et le ticket d'authentification SecurID. RSA est un sigle formé à partir des noms de ses fondateurs : Ronald Rivest, Adi Shamir et Leonard Adleman.
Nombre de Mersenne premiervignette|droite|Le moine français Marin Mersenne (1588-1648) En mathématiques et plus précisément en arithmétique, un nombre de Mersenne est un nombre de la forme 2 − 1 (souvent noté ), où est un entier naturel non nul ; un nombre de Mersenne premier (ou nombre premier de Mersenne) est donc un nombre premier de cette forme. Ces nombres doivent leur nom au religieux érudit et mathématicien français du Marin Mersenne ; mais, près de auparavant, Euclide les utilisait déjà pour étudier les nombres parfaits.
Cryptographie sur les courbes elliptiquesLa cryptographie sur les courbes elliptiques (en anglais, elliptic curve cryptography ou ECC) regroupe un ensemble de techniques cryptographiques qui utilisent une ou plusieurs propriétés des courbes elliptiques, ou plus généralement d'une variété abélienne. L'usage des courbes elliptiques en cryptographie a été suggéré, de manière indépendante, par Neal Koblitz et Victor S. Miller en 1985.
Formules pour les nombres premiersEn mathématiques, la recherche de formules exactes donnant tous les nombres premiers, certaines familles de nombres premiers ou le nombre premier s'est généralement avérée vaine, ce qui a amené à se contenter de formules approchées. Cette page recense les principaux résultats obtenus. L'espoir d'obtenir une formule exacte et simple donnant le n-ième nombre premier p, ou le nombre π(n) de nombres premiers inférieurs ou égaux à n, s'est très tôt heurté à l'extrême irrégularité de leur répartition, ce qui a amené à se contenter d'objectifs moins ambitieux.
Compétition de factorisation RSALa compétition de factorisation RSA fut une compétition mise en avant par la société RSA Security jusqu'en mai 2007. Mise en place le , son but était d'encourager la recherche dans la théorie calculatoire des nombres et dans la difficulté pratique de la mise en facteurs de grands entiers. Ils publièrent une liste de nombres semi-premiers connus comme les nombres RSA dotés d'une récompense financière pour les factorisations réussies pour certains d'entre eux.
Quadruplet premierEn théorie des nombres, un quadruplet premier est une suite de quatre nombres premiers consécutifs de la forme (p, p+2, p+6, p+8). C'est la seule forme possible pour quatre nombres premiers consécutifs d'écarts entre eux minimaux, en dehors des quadruplets (2,3,5,7) et (3,5,7,11). Par exemple (5, 7, 11, 13) et (11, 13, 17, 19) sont des quadruplets premiers. Un quadruplet de nombres premiers impairs consécutifs a un écart entre le plus petit et le plus grand de ces nombres d'au moins 6, il ne peut être de 6 car le seul triplet de nombres premiers consécutifs de la forme (p, p+2, p+4) est (3, 5, 7) (voir triplet premier).
Théorème des nombres premiersvignette|Une illustration du théorème des nombres premiers : en rouge, le nombre de nombres premiers inférieurs ou égaux à x ; en vert, une approximation utilisant ; en bleu, une approximation utilisant l'intégrale logarithmique . En mathématiques, et plus précisément en théorie analytique des nombres, le théorème des nombres premiers, démontré indépendamment par Hadamard et La Vallée Poussin en 1896, est un résultat concernant la distribution asymptotique des nombres premiers.
Indicatrice de Carmichaelvignette|upright=2|Fonction λ de Carmichael : λ(n) pour 1 ≤ n ≤ 1000 (avec les valeurs de la fonction φ d'Euler en comparaison) La fonction indicatrice de Carmichael, ou indicateur de Carmichael ou encore fonction de Carmichael, notée λ, est définie sur les entiers naturels strictement positifs ; elle associe à un entier n le plus petit entier m vérifiant, pour tout entier a premier avec n, am ≡ 1 mod n. Elle est introduite par Robert Daniel Carmichael dans un article de 1910.
Symbole de Jacobivignette|Charles Jacobi, mathématicien à l'origine du symbole de Jacobi Le symbole de Jacobi est utilisé en mathématiques dans le domaine de la théorie des nombres. Il est nommé ainsi en l'honneur du mathématicien prussien Charles Gustave Jacob Jacobi. C'est une généralisation du symbole de Legendre. Le symbole de Jacobi est défini pour tout entier relatif et tout entier naturel impair comme produit de symboles de Legendre, en faisant intervenir la décomposition en facteurs premiers de : pour tout et tous nombres premiers impairs (non nécessairement distincts), Soient positifs impairs et entiers quelconques.
Symbole de LegendreEn théorie des nombres, le symbole de Legendre est une fonction de deux variables entières à valeurs dans {–1, 0, 1}, qui caractérise les résidus quadratiques. Il a été introduit par Adrien-Marie Legendre, au cours de ses efforts pour démontrer la loi de réciprocité quadratique. Il ne dépend donc que de la classe de a modulo p. Le cas particulier p = 2 est inclus dans cette définition mais sans intérêt : vaut 0 si a est pair et 1 sinon.
Elliptic curve primalityIn mathematics, elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and de, in 1993. The concept of using elliptic curves in factorization had been developed by H. W.
Primality certificateIn mathematics and computer science, a primality certificate or primality proof is a succinct, formal proof that a number is prime. Primality certificates allow the primality of a number to be rapidly checked without having to run an expensive or unreliable primality test. "Succinct" usually means that the proof should be at most polynomially larger than the number of digits in the number itself (for example, if the number has b bits, the proof might contain roughly b2 bits).
Nombre de Carmichaelvignette|Robert Daniel Carmichael En théorie des nombres, un nombre de Carmichael (portant le nom du mathématicien américain Robert Daniel Carmichael), ou nombre absolument pseudo-premier, est un nombre composé n qui vérifie la propriété suivante, satisfaite par tous les nombres premiers d'après le petit théorème de Fermat : pour tout entier a premier avec n, n est un diviseur de a – 1. C'est donc un nombre pseudo-premier de Fermat en toute base première avec lui (on peut d'ailleurs se restreindre aux entiers a de 2 à n – 1 dans cette définition).
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.
Nombres premiers sexyEn mathématiques, un couple de nombres premiers sexy (ou nombres premiers sexys) est un couple de nombres premiers dont la différence est 6 (autrement dit, un couple de la forme (p, p + 6) où p et p + 6 sont des nombres premiers). C'est le cas, par exemple, des nombres 5 et 11. Certains de ces nombres premiers sont consécutifs, par exemple 23 et 29 sont premiers et il n'y a pas de nombre premier entre eux deux. Le terme « sexy » est un jeu de mots fondé sur le mot latin pour « six » : sex.
