Nombre premier

Un nombre premier est un nombre entier supérieur à 1 dont les seuls facteurs sont 1 et lui-même. Un facteur est un nombre entier qui peut être divisé de façon égale en un autre nombre. Les nombres premiers comprennent 2, 3, 5, 7, 11, 13, 17 et 19, 23, 23 et 29. Les nombres qui ont plus de deux facteurs sont appelés nombres composés. Le nombre 1 n'est ni premier ni composite. Il existe de nombreuses raisons pour lesquelles les nombres premiers peuvent être utilisés. Par exemple, certains types de cryptographie utilisent des nombres premiers. Il existe un nombre premier supérieur à p pour chaque nombre premier (par exemple "p"). La preuve mathématique qu'aucun nombre premier n'est le plus grand, démontrée par Euclide dans l'antiquité, confirme ce concept. Au fur et à mesure que l'ensemble des nombres naturels N = 1, 2, 3, ... progresse, les nombres premiers deviennent généralement moins fréquents et sont plus difficiles à trouver en un temps raisonnable. augmente, les nombres premiers deviennent donc plus rares et plus difficiles à trouver.} Quel est le meilleur moyen de savoir si un nombre est premier ? Un ordinateur peut être utilisé pour tester des nombres extrêmement grands pour voir s'ils sont premiers. Il n'y a pas de limite à la taille d'un nombre naturel, il y aura donc toujours un moment où tester de cette manière deviendra impossible, même avec des superordinateurs extrêmement puissants. À titre d'exemple, le plus grand nombre premier connu en décembre 2018 comptait 24 862 048 chiffres.

Qm = n/m q(m-1) = n / (m-1) q(m-2) = n / (m-2) q(m-3) = n / (m-3) . . . q3 = n / 3 q2 = n / 2

Si -- et seulement -- aucun des nombres q, tels que déduits ci-dessus, n'est un nombre entier, alors n est premier. Primes de Fermat et de Mersenne Un nombre premier de Mersenne est un nombre qui doit être réductible à la forme 2 n - 1, où n est un nombre premier. Les quelques premières valeurs connues de n qui produisent des nombres premiers de Mersenne sont les suivantes : n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61 et n = 89. Un nombre premier de Fermat est un nombre de Fermat qui est également premier. Un nombre de Fermat F n est de la forme 2 m + 1, où m signifie la puissance de 2 -- c'est-à-dire m = 2 n, et où n est un nombre entier. Cryptographie et nombres premiers Une règle essentielle du cryptage est que l'algorithme, ou la procédure réelle utilisée pour créer des clés, n'a pas à être gardé secret. En revanche, la clé doit l'être. Les nombres premiers peuvent être très utiles pour créer des clés. Par exemple, la force du cryptage à clé publique/privée réside dans le fait qu'il est facile de calculer le produit de deux nombres premiers choisis au hasard. Cependant, il peut être très difficile et long de déterminer quels sont les deux nombres premiers utilisés pour créer un produit extrêmement grand, lorsque seul le produit est connu. Dans le système RSA (Rivest-Shamir-Adleman), un exemple bien connu de cryptographie à clé publique, les nombres premiers sont toujours censés être uniques. Cependant, les nombres premiers utilisés dans le schéma de cryptographie Diffie-Hellman et l'échange de clés Digital Signature Standard(DSS) sont souvent normalisés et peuvent être utilisés par de nombreuses applications.

Divers algorithmes ont été formulés pour tenter de générer des nombres premiers toujours plus grands. Par exemple, supposons que "n" soit un nombre entier, et que l'on ne sache pas encore si n est premier ou composite. Tout d'abord, prenez la racine carrée - ou la puissance 1/2 - de n ; arrondissez ensuite ce nombre au nombre entier supérieur et appelez le résultat m. Trouvez ensuite tous les quotients suivants :