image1 image2 image3

Pourquoi les nombres premiers sont importants ?

Note utilisateur: 5 / 5

Etoiles activesEtoiles activesEtoiles activesEtoiles activesEtoiles actives
 

Prologue

En classe de 3ème (en France), nous introduisons la notion de nombres premiers. Mais force est de constater que si l'on demande à n'importe quelle personne dans la rue si elle sait à quoi servent ces nombres, les réponses sont très souvent négatives. Et pourtant, chaque personne utilise sans le savoir des technologies issues de la théorie des nombres premiers.

C'est quoi un nombre premier ?

La définition précise est la suivante : « Un nombre est premier si il est divisible uniquement par 1 et lui-même. »

Ainsi, en notant \( \mathbb{P} \) l'ensemble des nombres premiers, on a : \[ \mathbb{P} = \{2~;3~;5~;7~;11~;13~;\cdots \} \]

Et oui : "1" n'est pas un nombre premier car la définition nous impose que le nombre doit être divisible par 1 ET lui-même (le "ET" suppose donc que le nombre et "1" doivent être différents).

Les clés

Dans un RIB

Avez-vous déjà remarqué qu'à chaque Relevé d'Identité Banquaire ou Postal est attribué ce que l'on appelle une clé?

A quoi correspond-elle ? Comment est-elle calculée ?

Un RIB, RIP ou RICE est constitué de 21 chiffres (entre 0 et 9) suivi de deux chiffres correspondant à la clé. Cette clé correspond à la différence de 97 et du reste de la division euclidienne du nombre formé par les 21 premiers chiffres auxquels on a mis deux "0" par 97.

Par exemple, si le RIB commence par : 182080000301170928519, nous allons effectuer la division euclidienne de 18208000030117092851900 par 97 :

 

Le reste de cette division euclidienne est 84 ; la clé de ce RIB est donc 97 - 84=13.

Dans notre numéro de sécurité sociale

Le système est le même que précédemment : on prend les 13 premiers chiffres et on effectue la division euclidienne du nombre ainsi formé par 97. La clé est alors la différence de 97 et du reste.

Par exemple, le numéro de SS de Zoé commence par : 2990578646018. Elle a perdu sa clé donc il nous faut la retrouver.

Effectuons la divisions euclidienne de 2990578646018 par 97 :

97 - 88 = 09 donc son numéro de SS se termine par la clé : 09.

La famille des nombres premiers est infinie

C'est à Euclide (oui ! le même que pour la division ... euclidienne !) que l'on doit ce résultat. Et en plus, la démonstration est assez simple.

Notons \( p_1,\ p_2,\ \cdots,\ p_n \) les \( n\) premiers nombres premiers, \( n\geqslant2\).

Alors,  \( p_1 \times p_2 \times \cdots \times p_n+1\) n'est divisible par aucun des nombres  \( p_1,\ p_2,\ \cdots,\ p_n \). Il est donc premier, quel que soit l'entier \( n \geqslant 2 \), aussi grand que l'on veut, ce qui signifie que l'ensemble des nombres premiers est infini.

En termes mathématiques, si on note \( \mathbb{P} \) l'ensemble des nombres premiers, on pourrait dire qu'il existe une bijection de \( \mathbb{N}^*\setminus\{1\} \) dans \( \mathbb{P} \) qui à \( n \) associe \( n!+1 \).

Ainsi, comme \( \mathbb{N} \) est infini, \( \mathbb{P} \) l'est aussi.

La décomposition en produits de facteurs premiers

Il existe un théorème qui nous dit que n'importe quel nombre peut être écrit comme le produits de puissances de nombres premiers.

Autrement dit, quel que soit le nombre \( x \), on a : \[ x = p_1^{n_1} \times p_2^{n_2} \times \cdots \times p_k^{n_k}\qquad,\qquad p_i\in\mathbb{P},\ n_i\in\mathbb{N}. \]

 Par exemple, \[ 360=2^3 \times 3^2 \times 5.\]

La cryptographie

La cryptographie est la science qui permet de crypter un message. Elle est donc importante à l'ère du numérique. Quand vous utilisez votre carte bancaire, vous utilisez la cryptographie. Et cette science repose essentiellement sur des théorèmes de mathématiques concernant les nombres premiers.

Prenons l'exemple de la cryptographie RSA. Elle repose sur le théorème suivant :

Soient p et q sont deux nombres premiers distincts, n = pq et h = (p - 1)(q - 1). Soit alors k un entier compris strictement entre 1 et h premier avec h.

Alors, il existe un unique entier d compris strictement entre 1 et h tel que : \[ kd \equiv 1 \mod h.\]

Prenons p = 13 et q = 17. Alors, n = 221 et h = 192. Prenons alors k = 5.

Pour crypter un mot, on associe à chaque lettre de ce mot sa position dans l'alphabet (1 pour A, 2 pour B, etc.). Le mot "MATH" donne donc : (13,1,20,8).

Pour chaque élément de cette liste, on élève à l'exposant 5 et on prend le reste de la division euclidienne du résultat par 221.

  • \( 13 ^ 5 = 371293 \equiv 13 \mod 221 \)
  • \( 1 ^5 = 1 \equiv 1 \mod 221 \)
  • \( 20^5=3200000 \equiv 141 \mod 221 \)
  • \( 8^5 = 32768 \equiv 60 \mod 221\)

Le message "crypté" est donc : (13,1,141,60).

Pour décrypter le message à partir des valeurs de p et q, il faut calculer le nombre d compris strictement entre 1 et 192 tel que \( 5d \equiv 1 \mod 192 \). On trouve d = 77.

On a alors :

  • \( 13 ^ {77} \equiv (13^5)^{15}\times13^2 \equiv 13^{15} \times 13^2 \equiv (13^5)^3\times13^2 \equiv 13^3\times13^2 \equiv 13^5 \equiv 13 \mod 221 \)
  • etc.

On obtient alors (13,1,20,8) qui est le message original.

Commentaires   

0 #2 Stéphane Pasquet 26-02-2016 16:30
En effet, la démonstration était fausse. Je l'ai remplacé. Merci !
Citer
0 #1 Mpsi 2 08-02-2016 13:39
Bonjour, je suis tombé sur votre lien : "http://blog.mathweb.fr/index.php/13-curiosites-ma thematiques/12-pourquoi-les-nombres-premiers-sont- importants" , et vous dites que n!+1 est toujours premier (prenez n=4 ...) A mon avis vous vouliez dire autre chose...
Citer

Ajouter un Commentaire


Code de sécurité
Rafraîchir

joomla templatesjoomla template
2017  Le blog de Stéphane Pasquet