Grands nombres premiers Cryptographie RSA François DE MARÇAY Département de Mat

Grands nombres premiers Cryptographie RSA François DE MARÇAY Département de Mathématiques d’Orsay Université Paris-Sud, France 1. Limitations physiques Soit un nombre donné quelconque n ⩾1, représenté par exemple en base 10 comme suite finie de chiffres appartenant à {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Le Crible d’Eratosthène est la méthode la plus simple et la plus directe pour déterminer si un tel nombre entier n donné est un nombre premier, ou un nombre composé. L’algorithme procède par élimination : il s’agit de supprimer de la table complète de tous les entiers allant de 2 jusqu’à n tous les entiers qui sont multiples d’un entier inférieur à n. À la fin il ne restera donc que les entiers qui ne sont multiples d’aucun entier, c’est-à-dire, il ne restera plus que les nombres premiers. On commence tout simplement par rayer tous les multiples de 2, puis tous les multiples de 3, puis tous les multiples de 5, puis tous les multiples de 7, et ainsi de suite, jusqu’aux multiples du dernier entier premier k tel que k2 ⩽n. 1 2 François DE MARÇAY, Département de Mathématiques d’Orsay, Université Paris-Sud, 2014–2015 On peut en effet s’arrêter à k ≈√n, car tous les entiers non premiers ont déjà été rayés précédemment ! Cependant, ce procédé direct est limité dans la pratique à cause du très grand nombre d’opérations qu’il exige. In a very real sense, there are no large numbers : Any explicit integer can be said to be ‘small’. Indeed, no matter how many digits or towers of exponents you may write down, there are only finitely many natural numbers smaller than your candidate, and finitely many that are larger. Though condemned always to deal with small numbers, we can at least strive to handle numbers that are larger than those that could be handled before. Richard Crandall, Carl Pomerance Affirmation de philosophie des mathématiques. L’ensemble complet de tous les nombres premiers n’est pas connaissable comme totalité donnée de manière actuelle, c’est-à-dire de manière accessible, effective, concrète, visible, « vraiment présente ». □ La raison métaphysique simplette de cette limitation est claire : l’infini actuel n’existe pas. Afin de mieux comprendre en quoi il y a réellement limitation, spéculons quelque peu. Supposons par exemple que l’on rêve d’imprimer la liste complète de tous les nombres entiers premiers qui sont inférieurs à un certain entier nombre assez grand, disons pour se satisfaire de possèder un petit « trésor mathématique ». Va-t-on y parvenir ? Définition 1.1. Pour x ⩾1 entier, on note classiquement π(x) le nombre d’entiers premiers inférieurs à x : π(x) := Card  p ∈P premiers avec p ⩽x . On connaît la valeur exacte de π(x) pour des x contenant une vingtaine de chiffres en base 10. 1. Limitations physiques 3 Prenons par exemple x = 1020. Il se trouve qu’à notre époque, on connaît la valeur exacte : π 1020 = 2 220 819 602 560 918 840 ≈2 · 1018. De tels nombres n’ont « qu’une vingtaine de chiffres », ils peuvent donc sembler « petits » — mais attention aux illusions ! Question 1.2. Si on connaît la valeur exacte de π(1020), cela semble vouloir dire que l’on connaît effectivement tous les nombres premiers p ⩽1020, mais cela est-il bien vrai ? En fait, non ! Même si chacun de ces ≈2 · 1018 nombres pouvait être représenté par un seul caractère d’imprimerie ou un seul bit informatique, nous affirmons qu’il serait néan- moins totalement impossible de les voir tous, ou de les stocker tous dans des ordinateurs. En effet, considérons par analogie le nombre record de décimales du nombre d’Archi- mède : π = 3, 141592653589793238462643383279502884279169399375· · ·, qui, depuis octobre 2011, va jusqu’à 10 000 milliards, ce qui nous fait donc : 1013 décimales, c’est-à-dire 1013 caractères d’imprimerie, ou bits sur un ordinateur, un nombre vraiment inférieur à 2 · 1018. Mais même ce nombre se situe à la limite du visible. Question 1.3. Combien de livres de 500 pages comportant 40 lignes chacune avec 80 ca- ractères seraient nécessaires pour montrer à l’humanité éclairée les 1013 décimales connues du nombre π ? Dans un seul livre, on peut imprimer : 500 × 80 × 40 = 1 600 000 décimales, et donc il faudrait environ : 10 000 000 000 000 1 600 000 = 6 250 000, 4 François DE MARÇAY, Département de Mathématiques d’Orsay, Université Paris-Sud, 2014–2015 livres, environ la moitié des quatorze millions de livres que possède et conserve la Biblio- thèque Nationale de France. Pour faire voir les ≈2 · 1018 nombres premiers inférieurs à 1020, il faudrait alors au moins : 1018−13 = 100 000 bibliothèques de cette taille de par le monde. En poussant jusqu’à 5 chiffres de plus : Conclusion 1.4. Pour des raisons purement physiques, on ne pourra jamais « voir » tous les nombres premiers ayant un nombre de chiffres ⩽25 en base 10. □ Rien n’est logique et rien ne semble absurde comme l’océan. Cette dispersion de soi-même est inhérente à sa souveraineté et est un des éléments de son ampleur. Victor Hugo Ainsi dans cette immensité, se noie ma pensée : et le naufrage m’est doux dans cette mer. Leopardi Le paradoxe contre-paradoxal 1, c’est que les théoriciens des nombres réussissent quand même à capturer et à manipuler quelques gros poissons nombres premiers ayant jusqu’à 100, 200, 300 chiffres ! Les mathématiques évoluent alors comme dans une mer immense de nombres gigantesques, en connaissant très peu de nombres premiers parmi ceux qui comportent jusqu’à des dizaines de millions de chiffres en base 10. Question 1.5. Comment engendrer des nombres premiers qui possèdent un très grand nombre de chiffres ? 2. Grands nombres premiers : pêche à la ligne Fermat avait proposé, nous l’avons vu, une formule simple qui lui semblait produire des nombres premiers de plus en plus grands. Le hic, avec ces nombres de Fermat : Fn := 22n + 1, c’est qu’ils ne sont presque jamais premiers, en tout cas, pour ce qui est de ceux que nous connaissons actuellement. En 1732, Euler a découvert la factorisation : F5 = 4294967297 = 641 · 6700417. En 1882, Landry a montré que le nombre de Fermat suivant est aussi composé : F6 = 226 + 1 = 18446744073709551617 = 274177 · 67280421310721. No prime Fn has ever been found beyond F4, so Fermat’s conjecture has not proved a very happy one. G.H. Hardy, E.M. Wright Aux alentours de l’année 2005, l’état des connaissances concernant les nombres de Fer- mat jusqu’à F24 est résumé au moyen du tableau suivant. 1. Ce n’est parce qu’on ne peut pas tout connaître qu’il est impossible de connaître un tout petit peu d’un trop grand tout. 2. Grands nombres premiers : pêche à la ligne 5 Dans ce tableau, tous les nombres explicitement écrits sont des nombres premiers, et la lettre « P » désigne un grand facteur entier dont on a démontré qu’il est premier, tandis que la lettre « C » désigne un très grand facteur composé, dont on ne connaît pas nécessairement les facteurs premiers. Néanmoins, comme les mathématiques savent produire un très grand nombre de for- mules très compliquées, on peut toujours espérer qu’une modification de la formule de Fermat pourrait engendrer une collection infinie de nombres premiers. Question 2.1. Existe-t-il une formule générale simple F(k) dépendant d’un entier k ⩾1 dont toutes les valeurs : F(1) = 2, F(2) = 3, F(3) = 5, F(4) = 7, F(5) = 11, . . . . . . , décrivent exactement la suite des nombres premiers ? Aucune telle formule magique n’est connue sur Terre, et il est très probable qu’il n’en existe pas non plus sur les autres planètes habitées de l’Univers. On peut alors abaisser les ambitions d’un cran. Question 2.2. Existe-t-il une formule générale simple G (k) dépendant d’un entier k ⩾1 dont les valeurs contiennent au moins une infinité de nombres premiers ? (Sans demander, toutefois, que toutes les valeurs G (1), G (2), G (3), ..., soient des nombres premiers.) Par exemple, la formule : G (k) := k2 −k + 41 ne produit que des valeurs entières premières pour : 0 ⩽k ⩽40, 6 François DE MARÇAY, Département de Mathématiques d’Orsay, Université Paris-Sud, 2014–2015 à savoir les valeurs : 41, 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347, 383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097, 1163, 1231, 1301, 1373, 1447, 1523, 1601, mais à partir de k = 41, ces nombres cessent d’être toujours premiers : 41·41, 41·43, 1847, 1933, 43·47, 2111, 2203, 2297, 2393, 47·53, quoiqu’il y en ait toujours pas mal qui soient premiers. Problème mathématique ouvert. Existe-t-il une infinité de nombre premiers dans la suite : k2 + 1 ∞ k=1 ? ou encore dans la suite : k2 −k + 41 ∞ k=1 ? De même, on constate à la main ou uploads/Geographie/ grands-nombres-premiers-cryptographie-rsa-de-arcay-departement-de-mathematiques-d-x27-orsay-universite-paris-sud-france.pdf

Tags
Administrationnombres nombre premiers bernard chiffres
Documents similaires
  • 32
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager