Les nombres premiers

Publié le 15 avril 2019 par Serdj

Les nombres premiers sont sans doute les plus fascinants de tous les nombres entiers. Rappelons qu'un nombre premier est un nombre dont les seuls diviseurs sont 1 et lui même. (Donc 1 n'est pas premier, mais 2 l'est).
L'intérêt des nombres premiers provient avant tout du théorème de la factorisation : tout nombre entier > 1 se décompose en manière unique en un produit de nombres premiers, dits "facteurs".
Il existe tout un courant de recherches sur les nombres premiers et sur la factorisation. De grandes conjectures existent sur ces nombres, dont la conjecture de Goldbach et la conjecture de Riemann. Le problème de la factorisation consiste à trouver un algorithme rapide pour factoriser un nombre. Or actuellement on ne sait pas si ce problème est de classe P non NP. Le meilleur algorithme connu à ce jour, GNFS , factorise un nombre en un temps maxi de l'ordre de exp((64n/9)^(1/3)*(log n)^(2/3)), où n est le nombre de bits du nombre à factoriser.
Comme ce problème est très important pour la cryptographie, il se peut que quelqu'un ait déjà trouvé un algorithme polynomial (P), mais garde ce résultat secret. Ça ne facilite pas la recherche... J'ai cherché moi-même plusieurs algorithmes de factorisation. Voir mes pages informatique.
Voir ici un article sur les méthodes de factorisation modernes (en PDF)
Un petit truc amusant que j'ai découvert par hasard : la spirale des nombres premiers .


> La suite : La spirale des nombres premiers

Sciences


Tous mes livres : Cliquez sur le titre qui vous intéresse


Home Mes livres Mes tableaux Plan du site

NOUVEAU ! Vous aimez ce site ? Aidez-moi !
Partagez / votez pour cette page :