© DR

Comment les nombres premiers jouent actuellement un rôle crucial en sécurité informatique

Le Vif

Les nombres premiers, étudiés par pur plaisir dès l’Antiquité. D’Euclide aux cartes bancaires, leur rôle est crucial.

Un nombre premier est un entier positif ayant exactement deux diviseurs. Ainsi, 13 est premier car 1 et 13 sont ses seuls diviseurs, 15 ne l’est pas car il a quatre diviseurs (1, 3, 5 et 15), 1 ne l’est pas non plus car son seul diviseur est lui-même. Les plus petits nombres premiers sont 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… En voici deux plus grands, faciles à mémoriser : 23 456 789 et 345 676 543.

Les nombres premiers sont un peu les atomes de l’arithmétique : de la même façon que toute molécule se décompose en atomes, tout entier plus grand que 1 se décompose en produit de nombres premiers. Par exemple, 2016 = 2.2.2.2.2.3.3.7. De plus, cette décomposition est unique, à l’ordre près des facteurs.

Le plus grand nombre premier connu actuellement est (2 exposant 77 232 917) – 1, un nombre de 23 249 425 chiffres (les écrire tous remplirait environ 3 300 pages de ce magazine). Sa découverte, après six jours non-stop de calculs sur ordinateur et quatre vérifications indépendantes, a été annoncée le 3 janvier dernier. Existe-t-il des nombres premiers encore plus grands ? La réponse se trouve dans le livre 9 des Eléments d’Euclide (iiie siècle avant notre ère). Euclide prouve qu’il existe une infinité de nombres premiers. Son raisonnement, court et élégant, est souvent considéré comme une des plus belles démonstrations mathématiques. Le voici.

Supposons (pour rire) qu’il n’existe qu’un nombre fini de nombres premiers et appelons P le plus grand d’entre eux. Soit N = 2.3.5.7.11….P + 1 le nombre obtenu en faisant le produit de tous les nombres premiers jusqu’à P et en ajoutant 1 à ce produit. N admet un diviseur premier p, et p est nécessairement un des facteurs du produit 2.3.5.7.11….P (puisqu’on a supposé que tous les nombres premiers s’y trouvaient), donc p divise ce produit, qui vaut N – 1. En conclusion, p divise à la fois N et N – 1, ce qui est impossible puisque p est plus grand que 1. Notre supposition de départ était donc fausse, et il existe bien une infinité de nombres premiers.

Quel est l’impact de l’étude des nombres premiers sur notre vie quotidienne ? Savez-vous que, lorsque vous faites un virement ou un achat sur Internet avec votre carte de banque ou de crédit, de grands nombres premiers interviennent pour garantir la sécurité de votre transaction ? Dans les années 1970, la cryptologie, c’est-à-dire la science des échanges d’informations secrètes, a connu une véritable révolution. L’idée de base est que, autant il est facile de fabriquer rapidement deux nombres premiers p et q de quelques centaines de chiffres (en pratique environ 300 chiffres) et d’en faire le produit n = p.q, autant il est extrêmement difficile, connaissant n, de retrouver p et q : même avec les ordinateurs actuels les plus puissants, cela prendrait des dizaines d’années !

En 1978, Rivest, Shamir et Adleman ont mis au point l’algorithme RSA de chiffrement et déchiffrement d’informations secrètes, largement utilisé de nos jours. Si un espion, connaissant la  » clé publique  » n, réussissait à intercepter un message secret chiffré par RSA, la seule méthode connue pour le déchiffrer l’obligerait à retrouver les deux facteurs premiers de n. Bon courage !

Par Jean Doyen.

Vous avez repéré une erreur ou disposez de plus d’infos? Signalez-le ici

Contenu partenaire