Pour un entier « pas trop grand », il est assez facile d’obtenir sa décomposition en produit de facteurs premiers par divisions successives par des nombres premiers (que l’on a reconnus comme étant des diviseurs, ou sinon systématiquement par ordre croissant). Par exemple, 45 = 5 × 9 = 5 × 32, ou, de manière plus systématique,
4 851 = 3 ×1 617 = 3 × 3 ×539 = 32 × 7 ×77 = 32 × 72 × 11. Cette méthode atteint rapidement ses limites dans le cas d’un nombre composé ayant des facteurs premiers relativement « grands » : les critères de divisibilité des entiers n’aident plus et la méthode de division systématique par des nombres premiers croissants allonge considérablement la procédure. Aujourd’hui, grâce aux ordinateurs et à des méthodes plus raffinées, on peut factoriser des entiers constitués d’une centaine de chiffres ; pour autant, il n’existe toujours pas d’algorithmes de factorisation suffisamment performants pour faire beaucoup mieux en un temps raisonnable (le plus grand entier produit de deux nombres premiers factorisé à ce jour possède deux cent cinquante chiffres « seulement »).
À la racine du problème
Au XVIIe siècle, on trouve déjà trace, dans la correspondance entre Marin Mersenne et Pierre de Fermat, de problèmes de factorisation d’entiers ayant jusqu’à douze chiffres : à une époque où la calculette n’existe pas, c’est plutôt remarquable ! Ainsi, dans une lettre datant de 1643 que Fermat adresse à Mersenne, il est question de savoir si le nombre
2 027 651 281 est premier ou composé, et dans ce dernier cas comment il se décompose en facteurs premiers. Cette lettre nous donne au passage de précieux indices sur l’état de l’arithmétique de l’époque et son évolution vers une théorie des nombres moderne, dont on peut considérer que Fermat est le fondateur.
La méthode de factorisation exposée par Fermat s’appuie essentiellement sur la propriété suivante : le produit de deux nombres impairs peut toujours s’écrire comme la différence de deux carrés. En effet, si p et q (avec p > q) sont deux entiers impairs, alors leur somme et leur différence sont paires, ce qui permet d’écrire
Comme R2 – S2 = (R – S)(R + S), il s’ensuit que si un entier N impair est composé, il existe des entiers R et S tels que N = (R – S)(R + S). Cette propriété peut donc conduire à une méthode générale de décomposition : tous les nombres premiers (hormis 2) étant impairs, tout entier composé est de la forme 2k N (k un entier naturel) avec N impair, qui, s’il n’est pas premier, pourra s’écrire comme différence de deux carrés et donc être factorisé. Si les facteurs trouvés sont premiers, la décomposition est trouvée, sinon on procède de même avec les facteurs encore décomposables.
Mais, pour un entier N impair donné, comment déterminer R et S tels que N = R2 – S2 ? L’idée est de chercher R à partir de la partie entière de , que l’on notera c, par incrémentation successive : R = c + k, avec k = 1, 2, 3… (R est nécessairement plus grand que
puisque N = R2 – S2). Comme N = R2 – S2 = (c + k)2 – S2, (c + k)2 – N doit être un carré (égal à S2) : c’est la condition d’arrêt de la boucle d’incrémentation. L’entier k étant trouvé, R = (c + k) aussi, et il en est de même pour S (c’est la racine carrée de (c + k)2 – N) : le problème est résolu !
Quelques astuces calculatoires permettent à Fermat de rendre son algorithme moins laborieux qu’il n’y paraît : la quantité à tester, (c + k)2 – N, est calculée pour k = 1 en remarquant que, pour un entier r, (c + 1)2 – (c2 + r) = (c2 + 2c + 1) – (c2 + r) = 2c + 1 – r, expression bien plus facile à calculer « à la main » que l’expression initiale lorsque c est « grand ». Puis Fermat utilise le fait que : (c + k + 1)2 – N = (c + k)2 – N + (2c + 1 + 2k) pour passer d’une valeur de k à la suivante.
Voyons ce que cela donne sur le nombre entier en question dans la lettre :
N = 2 027 651 281. On commence par extraire la racine carrée de N en s’arrêtant à sa partie entière ; on trouve c = 45 029 et un reste r = 40 440 (autrement dit, 2 027 651 281 = 45 0292 + 40 440). On calcule alors 2c + 1 – r, qui est la quantité à tester à l’étape k = 1 ; on trouve 49 619. Ce nombre n’est pas un carré car, dit Fermat, « aucun carré ne finit par 19 » (voir encadré). On passe donc à k = 2, en ajoutant 2c + 1 + 2 = 90 061 à 49 619. On obtient 139 680, qui n’est toujours pas un carré. Pour k = 3 : 139 680 + 90 063 = 229 743 n’est pas un carré. Pour k = 4 : 229 743 + 90 065 = 319 808 n’est pas un carré… La lettre de Fermat nous apprend qu’il a dû poursuivre jusqu’à k = 12 (vérifiez-le !) afin de trouver 1 040 400, qui est le carré de 1 020. On obtient ainsi R = c + 12 = 45 041, S = 1 020, donc N = (R – S)(R + S) = 44 021 × 46 061. La décomposition s’arrête là puisque 44 021 et
46 061 sont des nombres premiers (ce qui peut se voir grâce au crible d’Ératosthène ; voir encadré « Fermat, Mersenne et les nombres premiers »).
Statue de Pierre de Fermat (vers 1601, 1665)
à Beaumont-de-Lomagne, dans le Tarn-et-Garonne.
Est-ce un carré ?
Comment savoir si un entier donné u > 0 est un carré ? De même qu’il existe des critères de divisibilité bien utiles en arithmétique, il est souvent possible de déterminer si l’on a affaire à un carré en examinant les derniers chiffres de u.
(1) Si u se termine par un nombre impair de zéros, ce n’est pas un carré (c’est facile à voir).
(2) Si u se termine par 2, 3, 7 ou 8, ce n’est pas un carré : il suffit d’étudier les dix cas possibles pour le dernier chiffre d’un nombre pour se convaincre que son carré se terminera nécessairement par 0, 1, 4, 5, 6 ou 9.
(3) Les seules terminaisons à deux chiffres possibles pour le carré d’un entier sont les suivantes : 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96 (assurez-vous-en !).
Fermat, Mersenne et les nombres premiers
L’une des premières traces de recherche systématique de nombres premiers est la méthode du savant grec Ératosthène de Cyrène (vers ‒273, ‒194), connue désormais sous le nom de crible d’Ératosthène. Elle consiste à écrire tous les entiers d’un intervalle donné et à éliminer successivement ceux qui sont des multiples de 2, puis ceux qui sont des multiples du nombre suivant non éliminé, soit 3, puis les multiples de 5, 7, 11, 13… Les nombres non éliminés sont tous les premiers contenus dans l’intervalle considéré. Dans une liste constituée de N entiers passée au crible d’Ératosthène, la procédure s’arrête après examen des multiples des nombres premiers inférieurs à (car si N est le produit de deux facteurs, ils ne peuvent être simultanément plus grands que
). Cette méthode est toujours utilisée (et enseignée) pour obtenir des listes de nombres premiers « pas trop grands ».
Il faut attendre le XVIIe siècle pour trouver des études approfondies sur les nombres premiers. Marin Mersenne, prêtre dans l’Ordre des minimes, ami de Descartes, défenseur de Galilée, en est un contributeur majeur. Dans son Cogitata physico-mathematica (1644), il affirme que les seuls nombres premiers p compris entre 2 et 257 tels que 2p – 1 soit aussi premier sont 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 et 257. Il peut paraître surprenant que la primalité d’un nombre aussi grand que 2257 – 1, qui comporte soixante-dix-sept chiffres, ait été établie par Mersenne ; de fait, on ne sait pas vraiment comment il se convainquit de ce résultat, d’autant que ce n’est qu’en 1750 que le « nombre de Mersenne » 231 – 1 fut prouvé premier (par Leonhard Euler). Ce ne sera qu’en 1876 que 2127 – 1 sera prouvé premier, et qu’au début du XXe siècle que la liste fournie par Mersenne sera complétée et corrigée (67 et 257 ne donnent pas des nombres de Mersenne premiers, ce qui est le cas en revanche de 61, 89 et 107) ! On connaît à ce jour cinquante et un nombres de Mersenne premiers, le plus grand étant 282 589 933 – 1 (un nombre à quelque vingt-cinq millions de chiffres…), qui est aussi le plus grand nombre premier connu. On ignore cependant toujours s’il y a une infinité de nombres de Mersenne premiers ou pas (et dans ce cas combien).
Marin Mersenne (1588–1648).
À la même époque, Pierre de Fermat, magistrat à Toulouse, cultive les mathématiques en amateur (très éclairé !) ; il entre en correspondance avec Mersenne dès 1636. L’un de ses résultats parmi les plus importants en théorie des nombres premiers figure dans une lettre envoyée en 1640 à son ami Bernard Frénicle de Bessy (1604‒1674) : il y affirme, sans démonstration, que si p est un nombre premier et a un entier quelconque, alors p divise ap – a. Ce résultat, démontré en 1736 par Euler, est désormais connu sous le nom de petit théorème de Fermat ; il est au cœur des algorithmes actuels testant la primalité des très grands nombres.
Une méthode vraiment efficace
La méthode de Fermat permet ainsi de factoriser efficacement le nombre N = 2 027 651 281 : la procédure algorithmique converge en relativement peu d’étapes (12). Si l’on avait cherché les facteurs premiers de N = 2 027 651 281 par la « voie ordinaire », c’est-à-dire par divisions successives par des nombres premiers croissants, il aurait fallu, écrit Fermat, « diviser par tous les nombres depuis 7 jusqu’à 44 021 ». Son algorithme fait bien mieux en effet ! Mais cela tient au fait que les deux facteurs premiers p et q qui composent N sont « assez proches » l’un de l’autre. La méthode proposée par Fermat part de , soit la partie entière de la moyenne géométrique des deux facteurs, pour progresser vers R = (p + q) / 2, leur moyenne arithmétique. La différence entre ces deux moyennes donne ainsi une idée de la longueur de l’algorithme de Fermat ; malheureusement, plus p et q s’éloignent l’un de l’autre, plus cette différence s’accroît…
Cette méthode de factorisation est néanmoins restée jusque dans les années 1970 la méthode la plus efficace pour factoriser des entiers bien choisis. Elle a été améliorée en 1981 par l’Américain Carl Pomerance (né en 1944), dans un algorithme appelé crible quadratique, où l’on cherche R et S tels que N divise R2 – S2 (alors que dans la méthode de Fermat, R et S sont tels que N = R2 – S2). Cet algorithme a permis, en 1994, grâce à plusieurs centaines d’ordinateurs et des mois d’efforts, de factoriser le nombre RSA-129, un nombre à cent vingt-neuf chiffres produit de deux grands nombres premiers.
Un défi entre savants
Dans une autre lettre datée de 1643, Fermat s’attaque à plus costaud, avec
N = 100 895 598 169, suite à la demande formulée par Mersenne d’« une méthode pour découvrir dans l’espace d’un jour s’il est premier ou composé » (les correspondances entre savants de l’époque tiennent souvent de la joute intellectuelle…). Fermat expliquait rarement comment il obtenait ses résultats, ce qui permit d’occuper de nombreux mathématiciens à les démontrer, et ce jusqu’au XXe siècle ! Fidèle à cette pratique, il répondit, sans autre explication, que le nombre proposé par son correspondant est composé de 898 423 et 112 303, qui, ajoute-t-il, sont premiers.
Fermat aurait-il dans ce cas aussi utilisé l’algorithme précédent ? Sûrement pas ! Un codage de cet algorithme sur ordinateur montre en effet qu’il lui aurait fallu pousser jusqu’à k = 187 723. On voit à quel point la condition sur la proximité des deux facteurs est forte : 898 423 et 112 303 sont bien trop « éloignés » l’un de l’autre pour pouvoir les trouver en un temps « raisonnable » avec cette méthode. Alors, quelle nouvelle méthode a bien pu employer Fermat pour relever le défi lancé par Mersenne ?
Il se trouve que Fermat s’est intéressé à des nombres particuliers, les nombres parfaits (égaux à la somme de leurs diviseurs stricts, comme 28, égal à 1 + 2 + 4 + 7 + 14) et les nombres multi-parfaits (entier dont un multiple est égal à la somme de ses diviseurs stricts, comme 120, dont la somme des diviseurs stricts vaut 360, soit 3 × 120). Tous ces nombres ont été étudiés par Euclide, puis par Descartes. Or, un autre passage de cette seconde lettre rend manifeste le fait que Mersenne s’intéresse à la factorisation d’un nombre N, supposé multi-parfait (ce nombre fut sans doute suggéré par Frénicle). La décomposition de N en facteurs premiers est établie… ou presque, car un certain facteur se révèle plus compliqué que les autres à analyser : il s’agit précisément de
100 895 598 169. Cet entier est-il premier ? Il n’y qu’à demander à Fermat !
Ce dernier s’empare du problème, qu’il traite, très certainement, à partir de considérations sur les propriétés des nombres multi-parfaits. Son raisonnement aurait pu être le suivant : si N est k-parfait, c’est-à-dire si la somme σ (N) de ses diviseurs stricts vaut kN, avec k « petit », alors les « grands » facteurs premiers de σ (N) et de N sont les mêmes ! Or, il se trouve que 616 318 177 apparaît dans la décomposition de N, le nombre σ (616 318 177) apparaît donc dans celle de σ (N), avec
σ (616 318 177) = 616 318 177 + 1. La décomposition de 616 318 178 donne
2 × 73 × 898 423, avec 898 423 premier ; ce dernier nombre est donc aussi un facteur premier de N. Comme il n’apparaît pas dans la décomposition initiale, c’est qu’il est un facteur de 100 895 598 169. Une dernière division peut conduire à la factorisation cherchée : 100 895 598 169 = 898 423 × 112 303. De manière moins laborieuse, on peut aussi réutiliser le raisonnement précédent pour la trouver :
σ (898 423) = 898 424 = 23 × 112 303 ; comme 112 303 n’apparaît pas non plus dans la décomposition initiale de N, c’est qu’il est aussi un facteur premier de 100 895 598 169. Et le tour est joué !
La factorisation reste difficile, tant mieux !
Au XVIIe siècle, savoir factoriser de très grands entiers n’avait sans doute aucun autre intérêt que de prouver à ses pairs son ingéniosité dans le calcul. De nos jours, cette question est devenue cruciale : un pan entier de la sécurité numérique repose sur la difficulté de traiter un tel problème de factorisation ! On sait aujourd’hui générer des nombres si difficiles à factoriser que même si l’on dédiait la puissance de tous nos ordinateurs à cette seule tâche, on n’en viendrait pas à bout en un temps raisonnable. Loin d’être fâcheuse, cette difficulté est au cœur même du système de cryptage le plus utilisé actuellement : le système RSA, inventé en 1977 par Ronald Linn Rivest (né en 1947), Adi Shamir (né en 1952) et Leonard Adleman (né en 1945), et généralisé comme clé de cryptage à la fin des années 1990, avec l’arrivée d’Internet. Il s’agit d’un code asymétrique, avec une clé connue de tous pour le codage des messages, dite clé publique, et une clé connue du seul destinataire pour le déchiffrement, dite clé privée. L’avantage de ce type de code asymétrique est que la clé privée n’emprunte aucun canal de communication.
Dans le système de cryptage RSA, la clé publique est un nombre N produit de deux facteurs premiers p et q « très grands » que l’on n’a pas besoin de connaître pour coder le message (voir encadré), tandis que le décodage nécessite non seulement la connaissance de N mais aussi celle des deux facteurs p et q. On comprend dès lors que si N est « suffisamment grand », et p et q bien choisis, compte tenu des limites actuelles sur la factorisation, un tel système de codage est en pratique inattaquable. On estime aujourd’hui que prendre un nombre N à quelque six cents chiffres (p et q comportant eux environ trois cents chiffres) nous met à l’abri de toute menace pour plusieurs dizaines d’années (on ne sait pas faire mieux actuellement que factoriser un nombre à deux cent cinquante chiffres).
La clé publique de RSA, en pratique ?
En 1983, le Groupement des cartes bancaires a décidé d’utiliser le système de cryptage RSA pour sécuriser les transactions par carte bancaire. La clé publique utilisée alors était un nombre de quatre-vingt-dix-sept chiffres, avant qu’elle soit remplacée par un nombre de deux cent trente-deux chiffres : 1 550 880 802 783 769 298 423 921 500 751 307 878 471 020 215 206 711 102 793 111 990 113 875 394 553 459 999 757 605 304 671 735 856 091 597 555 389 797 408 938 173 344 043 674 704 780 986 390 069 906 679 096 728 933 081 405 044 935 969 514 508 676 239 942 493 440 750 589 270 015 739 962 374 529 363 251 827. Cette clé est publique, mais en pratique il est épouvantablement difficile de la trouver explicitement, même sur Internet !
Ce texte est issu de la conférence donnée par Daniel Perrin le mercredi 14 mars 2018 à la Bibliothèque nationale de France dans le cadre du cycle « Un texte, un mathématicien ».
