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.


Commentaires préférés (3)

De Polignac c'est amusé à caractériser les nombres premiers par couple :
-Nombres premiers jumeaux : ils me différent que de 2, cette distance de 2 est la plus petite distance entre deux nombre premiers (3,5,7,11 et 13)
-Nombres premiers cousins : ils correspond à un écart de 4
-Nombres premiers sexy : ils correspondent à un écart de 6 (leurs nom vient d'une proximité phonétique entre six et sex)

Posté le

android

(190)

Répondre

J'ai toujours été le dernier a comprendre cette histoire de calcul des nombres premiers .. Pour moi les premiers ça a toujours été : 1,2,3,4,5,6,7,8,9

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


Tous les commentaires (113)

De Polignac c'est amusé à caractériser les nombres premiers par couple :
-Nombres premiers jumeaux : ils me différent que de 2, cette distance de 2 est la plus petite distance entre deux nombre premiers (3,5,7,11 et 13)
-Nombres premiers cousins : ils correspond à un écart de 4
-Nombres premiers sexy : ils correspondent à un écart de 6 (leurs nom vient d'une proximité phonétique entre six et sex)

Posté le

android

(190)

Répondre

Et le jour où on va savoir faire ça, ça va être la révolte partout !

Il y a la loi de réciprocité quadratique (de Gauss) qui lie deux nombres premiers et qui dit que un nombre premier peut être exprimés par le carré à un multiple près d'un autré nombre premier

Posté le

android

(11)

Répondre

J'ai toujours été le dernier a comprendre cette histoire de calcul des nombres premiers .. Pour moi les premiers ça a toujours été : 1,2,3,4,5,6,7,8,9

Pour ceux qui souhaiterais en savoir plus sur ce type de cryptage, je vous invite a rechercher "chiffrement RSA" sur votre amis google ;)

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.

Posté le

android

(32)

Répondre

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

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...

Encore mieux, étant donné qu'on ne sait pas bien dire si on nombre est premier ou pas, il n'est pas utile de n'utiliser que des nombres premiers pour le cryptage. Utiliser des nombres pseudo-premiers (ça a un sens précis mais disons dans le sens où tout algorithme actuel prendra une plombe à vous dire s'il l'est ou pas) est très largement suffisant.

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.
Pourquoi 1 n'est pas un nombre premier? Il est divisible par lui-même et par... 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...
Ç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éresse, 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)

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...
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)

Posté le

android

(15)

Répondre

a écrit : Et le jour où on va savoir faire ça, ça va être la révolte partout ! Le jour où l'on saura faire ça c'est qu'on aura des ordinateurs quantiques (parce que sinon il suffit d'augmenter la taille des nombres qu'on utilise pour augmenter la difficulté). Et si on a des ordinateurs quantiques, alors on est capable d'utiliser la cryptographie quantique, qui, et là c'est magique, n'a ABSOLUMENT aucune faille (c'est mathématiquement prouvé).

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 Non, ce n'est pas un problème du millénaire. C'est la spirale de Ulam, qui est expliquée par la conjecture dite F formulée par Hardy et Littlewood (à l'origine du théorème des nombres premiers qui est le premier vrai pas fait dans l'étude de la répartition de ceux-ci à mon avis) à partir de la conjecture de Bateman et Horn (oui Bateman comme le psychopathe dans American Psycho).

Pour rappel une conjecture est une proposition qui n'a pas été prouvée.

Par contre il est vrai que si quelqu'un réussissait à prouver ladite conjecture, il serait regardé comme une énorme brute (et s'il avait moins de 40 ans, se verrait assez sûrement donner la médaille Fields).

J'aimerai que l'on vérifie cette partie de l'anecdote où l'auteur affirme qu'il existe une formule pour trouver les nombres premiers (bien qu'elle soit inconnue). Dans mes souvenir aucune preuve rigoureuse n'a été produite pour démontrer l'existence seulement de cette formule. Et donc rien ne prouverai qu'un jour on soit capable de comprendre la logique des nombre premier.

Posté le

android

(5)

Répondre

a écrit : De Polignac c'est amusé à caractériser les nombres premiers par couple :
-Nombres premiers jumeaux : ils me différent que de 2, cette distance de 2 est la plus petite distance entre deux nombre premiers (3,5,7,11 et 13)
-Nombres premiers cousins : ils correspond à un écart de 4
-Nombres premiers
sexy : ils correspondent à un écart de 6 (leurs nom vient d'une proximité phonétique entre six et sex) Afficher tout
Étant donné que 2 et 3 sont des nombres premiers, 1 est la plus petite distance entre deux nombres premiers.

Comme d'habitude, dès que l'on parle de nombre premier je suis toujours aussi larguée.

Posté le

android

(7)

Répondre

a écrit : J'aimerai que l'on vérifie cette partie de l'anecdote où l'auteur affirme qu'il existe une formule pour trouver les nombres premiers (bien qu'elle soit inconnue). Dans mes souvenir aucune preuve rigoureuse n'a été produite pour démontrer l'existence seulement de cette formule. Et donc rien ne prouverai qu'un jour on soit capable de comprendre la logique des nombre premier. Afficher tout Il en existe, mais elles sont bien trop peu efficaces pour le calcul.

fr.wikipedia.org/wiki/Formules_pour_les_nombres_premiers#Formules_exactes_sans_int.C3.A9r.C3.AAt_pratique

Mais je suppose que par "formule" il entendait "algorithme". Auquel cas l'algorithme non probabiliste (qui vous dit à coup sûr si un nombre est premier ou pas) le plus rapide est l'algorithme dit AKS. Il reprend grosso modo le principe du crible de Fermat mais en en utilisant une généralisation.

Chiffres, formules, calculs, maths. Après plusieurs relectures de l'anecdote et consultations des sources, je suis toujours perdu. Pas de doutes, avec les nombres, premiers ou non, je serais toujours dans les derniers.

Quelques précisions :

Il faut savoir tout d'abord que tout nombre entier s'exprime comme un produit de nombres premiers. Par exemple 21 est le produit de 7 et 3, 21=7*3. Ou encore 75=3*5*5. Ce produit est unique, c'est à dire que par exemple pour 21, il n'existe pas d'autres nombres premiers que 3 et 7 dont il est produit.

Cette action de chercher pour un nombre les nombres premiers dont il est produit s'appelle "la décomposition en produit de facteurs premiers".
Seulement voilà : autant il est très facile de décomposer un nombre comme 21, autant quand le nombre est très grand ça devient une autre paire de manche !
Et c'est sur ce fait là que repose le système RSA.

Un peu d'explication :

Alice veut recevoir un message de Bob.
Elle prend alors un nombre qui est produit de DEUX nombres premiers. Par exemple 21=3*7.

21 sera ce qu'on appelle "la clé publique" qui sera accessible à tout le monde.
Le couple (3,7) sera "la clé privée" que seule Alice connait.

Bob se servira de la clé publique pour crypter son message. Il l'envoie à Alice, laquelle le décrypte grâce à la clé privée.
Le message ne peut se décrypter qu'avec la clé privée (on appelle ça un cryptage asymétrique, c'est à dire que la clé qui permet de crypter n'est pas la même que celle qui permet de décrypter) ! Donc même si le message est intercepté par quelqu'un, il ne lui servira à rien tant qu'il n'a pas la clé privée. Par contre s'il réussi à décomposer 21 (clé publique accessible à tout le monde) en 3 et 7, il aura donc trouvé la clé privée et pourra décrypter...

Voilà pour le principe.

Évidemment dans la réalité on prend des nombres beaucoup plus grand que 21...

Ps : Le nom "RSA" vient des initiales des noms de ses inventeurs : Ronald Rivest, Adi Shamir et Leonard Adleman.