On ne sait pas calculer simplement les nombres premiers

Proposé par
Invité
le

De nos jours, il n'existe aucune technique de calcul pour déterminer simplement les nombres premiers. C'est pourquoi on utilise ce problème pour les cartes bleues : le système de cryptage d'une carte bancaire s'appuie sur le produit de deux nombres premiers.

Il existe des formules mais elles demandent une puissance de calcul très importante, inaccessible en l'état actuel des connaissances. C'est pourquoi les nombres premiers utilisés pour le cryptage des cartes ont beaucoup de chiffres afin de rendre une tentative de décryptage quasi impossible en raison du temps qu'elle nécessiterait, même à l'aide d'un supercalculateur.


Tous les commentaires (113)

a écrit : Un nombre premier : nombre qui ne peut être divisé que par lui même et par 1.
Exemple : 3 / 5 / 7....71 / 73....
1 n'en n'est pas un.
Sans oublier le 2 !

Posté le

android

(1)

Répondre

a écrit : D'ailleurs n'est-ce pas le sujet d'un des problèmes du millénaire qui dit que les nombres premiers seraient répartis d'une certaines manière ? Fait observé par un mathématicien qui s'ennuyait lors d'une conférence et qui écrivait à la suite les nombres premiers et il en dégageait des formes géométrique. Source : SCMB Il faut écrire tous les nombres en colimaçon sur un damier et colorier les cases des nombres premiers ; c'est comme ça qu'apparaissent des "lignes" régulières ... Pour lesquelles il n'y a pas non plus d'explication !

Une façon très simple d'obtenir un nombre premier est d'utiliser la formule n! - 1

3x2x1 -1 est premier, tout comme 8x7x6x5x4x3x2x1 - 1 (=40319)

De mémoire, l'auteur de cette formule est Gauss.

a écrit : Un nombre premier n'est divisible que par 1 et lui même.
Ça c'est facile à comprendre, mais, blonde que je suis, je voudrais qu'on m'explique pourquoi "1" n'est pas un nombre premier...
Un nombre premier est un entier naturel qui admet "exactement deux diviseurs DISTINCTS (ni plus ni moins)", soit 1 et lui même.
Mais le nombre 1 a UN SEUL diviseur ! Qui est 1...

a écrit : Un nombre premier n'est divisible que par 1 et lui même.
Ça c'est facile à comprendre, mais, blonde que je suis, je voudrais qu'on m'explique pourquoi "1" n'est pas un nombre premier...
Suis la même logique que la règle qui veut que x^0=1.
Parce que!!!

a écrit : Suis la même logique que la règle qui veut que x^0=1.
Parce que!!!
x^(a-b) = (x^a)/(x^b). Remplace b par 0 tu comprendras pourquoi x^0=1.

Posté le

blackberry

(7)

Répondre

J'ai jamais compris ce truc en fait, pour moi un nombre premier peut se diviser aussi bien par 1 et lui même que par 10, ou 42, ou Pi, ou 56,7890764...
Par exemple, 71: divisé par 1, ça donne 71. Divisé par 71, ça donne 1. Et divisé par 10, ça donne 7,1.
Donc un nombre premier peut se diviser par 10 :)

a écrit : alors en fait 1 est théoriquement premier ( puisque divisible par lui même et par 1) mais il a été convenu de ne pas l intégré aux nombres premier car c est un nombre dit neutre (toute multiplication ou division par 1 etant neutre). par contre le premier nombre premier est le 2 et c est d ailleurs le seul nombre premier pair (tout les autres étant disvisibles par 2) Afficher tout 1 est premier parce que les deux entiers qui divisent ce nombre tel que le demande la définition d'un nombre premier sont égaux. Il faut bien préciser que le couple unique de diviseurs d'un nombre premier est formé de deux entiers naturels différents.

Posté le

android

(0)

Répondre

a écrit : D'ailleurs n'est-ce pas le sujet d'un des problèmes du millénaire qui dit que les nombres premiers seraient répartis d'une certaines manière ? Fait observé par un mathématicien qui s'ennuyait lors d'une conférence et qui écrivait à la suite les nombres premiers et il en dégageait des formes géométrique. Source : SCMB Effectivement, lors d une conference, le mathematicien observa que en ecrivant les chiffres en spirale, allant dans le sens trigonometrique (antihoraire), les nombres premiers formaient des diagonales. Cette spirale est la spirale d'ulam. D'ailleurs l auteur de cette anecdote aurait dû donner le nom de ce cryptage, qui est le codage RSA, utilisé par les banques et les sites internets entre autre.

Posté le

android

(1)

Répondre

Une petite explication complémentaire que je n'ai pas encore vue dans les commentaires précédents pour ceux qui n'auraient pas compris cette histoire de multiplication : le principe de la sécurité des CB (et autres applications) nécessite de connaitre les diviseurs d'un nombre, or puisqu'il est très long et compliqué de vérifier si un nombre est premier (et donc de trouver ses diviseurs s'il n'est pas premier), si on connait deux nombres premiers très grands (des milliards chacun) qui ont donc déjà nécessité une puissance et une durée de calcul très grands pour vérifier qu'ils sont premiers, lorsqu'on les multiplie entre eux on multiplie la complexité pour retrouver les diviseurs par des milliards aussi, le résultat de la multiplication est tellement grand qu'avec les puissances de calcul actuelles il faudrait des millions d'années pour retrouver les deux opérandes de la multiplication sans les connaitre !

a écrit : J'ai jamais compris ce truc en fait, pour moi un nombre premier peut se diviser aussi bien par 1 et lui même que par 10, ou 42, ou Pi, ou 56,7890764...
Par exemple, 71: divisé par 1, ça donne 71. Divisé par 71, ça donne 1. Et divisé par 10, ça donne 7,1.
Donc un nombre premier peut se diviser par 10 :)
On parle bien entendu des entiers naturels ici. Pas de complexes, de relatifs etc.

(Quoi que concrètement on peut avec les entiers relatifs, mais c'est uniquement avec les nombres entiers)

Posté le

android

(5)

Répondre

a écrit : Ça vient de l'algèbre en fait. La définition de premier dans le cadre des nombres entiers est une conséquence d'une définition plus générale sur les structures algébriques. Définition qui si je la cite va m'attirer une bonne dose de "hein j'ai rien compris".
Pour ceux que ça intéress
e, regardez "idéal premier" sur wikipedia.

Une meilleure définition, qui permet d'exclure ce problème de "est-ce que 1 est un nombre premier" que pose ton "divisible par 1 et lui-même" est :
Un nombre premier est un nombre qui a exactement deux diviseurs.

(et ça ça implique que ce sont 1 et lui-même)

NB : il est bien plus simple en fait de travailler dans les entiers relatifs, où l'on dira alors qu'un nombre est premier si il a exactement quatre diviseurs (lui-même, 1 et leurs opposés)
Afficher tout
Tu dis que chaque nombre premier a exactement 4 diviseur: lui même, 1 et son opposé; mais ça ne fait que 3... Quel est le 4ème?

a écrit : D'ailleurs n'est-ce pas le sujet d'un des problèmes du millénaire qui dit que les nombres premiers seraient répartis d'une certaines manière ? Fait observé par un mathématicien qui s'ennuyait lors d'une conférence et qui écrivait à la suite les nombres premiers et il en dégageait des formes géométrique. Source : SCMB Je me permet de compléter une autre réponse : le problème du millénaire (et sans doute bien plus) qui concerne les nombres premiers, c'est la démonstration (ou l'invalidation. Ou la preuve de l'indecidabilité :-P) de la conjecture de Riemann.
C'est difficile à vulgariser, mais grosso-modo, il s'agit de prouver que les points d'annulation d'une fonction complexe, appelée fonction zeta de Riemann, vérifient une certaine propriété (entiers strictement négatifs, OU avoir une partie réelle égale à 1/2 ). Cette fonction, définie par une série puis prolongée à C\{1}, étant intimement liée à la répartition des nombres premiers, car on sait l'écrire sous la forme d'un développement faisant intervenir tous les premiers.
David Hilbert, qui avait posé une liste de problèmes pour le XXe siècle, se plaisait à dire que s'il était cryogenisé et se réveillait dans 1000 ans, sa première question serait de savoir si la conjecture de Riemann a été prouvée.
Et dans Futurama, à un moment, Farnsworth donne une conférence pendant laquelle il utilise cette assertion, promue en l'an 3000 au rang de théorème !

Posté le

android

(1)

Répondre

a écrit : Tu dis que chaque nombre premier a exactement 4 diviseur: lui même, 1 et son opposé; mais ça ne fait que 3... Quel est le 4ème? Lui meme, son inverse, 1 et son inverse, donc -1.

Posté le

android

(4)

Répondre

a écrit : Une façon très simple d'obtenir un nombre premier est d'utiliser la formule n! - 1

3x2x1 -1 est premier, tout comme 8x7x6x5x4x3x2x1 - 1 (=40319)

De mémoire, l'auteur de cette formule est Gauss.
Pour tout n>0, faut-il préciser.

a écrit : Lui meme, son inverse, 1 et son inverse, donc -1. Opposé, pas inverse ! L'opposé de 2 c'est -2, l'inverse c'est 1/2. Ne pas confondre !

a écrit : Opposé, pas inverse ! L'opposé de 2 c'est -2, l'inverse c'est 1/2. Ne pas confondre ! Certes, mais ici le but de mon message était de faire comprendre pourquoi 4 diviseurs.
Mais effectivement, au temps pour moi, c'est l'opposé.

Ca n'enlève en rien à la véracité de mon explication ^^.

Posté le

android

(0)

Répondre

a écrit : Un nombre premier n'est divisible que par 1 et lui même.
Ça c'est facile à comprendre, mais, blonde que je suis, je voudrais qu'on m'explique pourquoi "1" n'est pas un nombre premier...
Un nombre premier à strictement exactement 2 diviseurs, 1 et lui même, or, 1 n'est divisible que par 1 donc il n'est pas premier

a écrit : Ce que tu dis est sûrement faux car le problème de la décomposition n'est très probablement pas NP-complet (on le soupçonne d'être strictement compris entre la classe P et la classe NP-complet, mais personne ne pense qu'il est NP-complet, même si personne n'a réussi à le prouver).

Par c
onséquent, trouver un algorithme de décomposition en facteurs premiers "rapide" (c'est à dire appartenant à la classe P) ne prouvera pas que P=NP.

Un exemple de problème NP-complet est celui du voyageur du commerce. Si quelqu'un trouve un algorithme rapide pour ce problème, il aura prouvé P=NP.
Mais y'a très peu de chance, à ma connaissance aucun mathématicien ne pense que P=NP. En fait ils sont divisés en deux camps : ceux qui pensent que P est différent de NP, et ceux qui pensent que c'est un problème indécidable...

Rappel : la classe des problèmes NP-complet est une sous classe des problèmes NP. C'est en fait l'ensemble des problèmes NP qui sont au moins aussi difficile que tous les autres problèmes NP. Donc si on prouve qu'un problème NP-complet est en fait facile (donc appartenant à P), on aura prouvé que tous les autres problèmes NP sont également faciles. Donc que P=NP.
Afficher tout
Comment déterminer si un problème appartient a la classe NP ?