Savez-vous factoriser à la mode de Fermat ?

La question de savoir factoriser un nombre entier est cruciale de nos jours: de nombreux systèmes cryptographiques (dont le fameux RSA) reposent dessus. Mais, au 17ème siècle, du temps du mathématicien Pierre de Fermat, savoir factoriser un entier n’avait absolument aucune application pratique; le seul intérêt de trouver une factorisation était éventuellement ludique (on s’amusait comme on pouvait à l’époque).

Disons-le tout de suite, savoir factoriser un entier est un problème difficile. Par exemple, si je vous donne le nombre 15, vous me direz immédiatement que c’est 3 fois 5 mais si je vous donne 2 473 859, peu d’entre vous me répondront qu’il s’agit du produit de 1039 par 2381. L’exemple que je viens de vous donner reste relativement simple (!), mais dans une lettre envoyée à Fermat en 1643, le père Mersenne (il était prêtre), lui demanda de factoriser le nombre 100 895 598 169. Rien que ça ! Quel farceur ce Mersenne… Cependant, sa blague tomba à l’eau car il reçut aussitôt une lettre de Fermat (datée du 7 Avril 1643) dans laquelle on pouvait lire ceci:

Vous me demandez si le nombre 100 895 598 169 est premier ou non, et une méthode pour découvrir, dans l’espace d’un jour, s’il est premier ou composé. À cette question, je réponds que ce nombre est composé et se fait du produit de ces deux : 898 423 et 112 303, qui sont premiers.

Impressionnant. Sans calculatrice et en moins d’un jour, Fermat a réussi à factoriser un nombre à 12 chiffres ! Mais comment Fermat a-t-il fait pour factoriser ce nombre ? Car malheureusement Fermat n’a pas donné sa méthode dans cette lettre… (certaines mauvaises langues diront qu’il était coutumier du fait, et que sa marge était aussi courte que le Pape est une femme).

Ce que l’on sait en revanche, c’est que Fermat avait développé une méthode de factorisation, dite méthode de factorisation de Fermat (original comme nom) que je vais tenter de vous expliquer ici.

Une idée simple mais brillante

Soit $N$ un entier naturel qu’on veut factoriser. La méthode de Fermat découle de l’idée toute simple suivante: si on peut écrire $N$ comme une différence de deux carrés $N=a^2 -b^2$ alors $N=(a+b)(a-b)$ . Le problème de la factorisation se ramène donc à un problème de soustraction. Par exemple, $15=4^2 - 1^2$ donc $15 = (4+1) (4-1) = 5 \times 3$ .

Remarque: si $N$ est un nombre impair, une telle factorisation existe toujours. En effet, si $N=2n+1$ alors vous pouvez vérifier que $N= (n+1)^2 - n^2$ . Il faut faire tout de même attention car dans ce cas nous avons $a=n+1$ et $b=n$ , ce qui donne $a-b=1$ et $a+b=2n+1=N$ : la factorisation obtenue est donc triviale (savoir que $N=N \times 1$ n’a aucun intérêt, vous en conviendrez).

Deux conditions nécessaires

Dans toute la suite, on supposera que $N$ n’est pas un carré (car sinon, la factorisation de $N$ est facile à trouver: c’est $N = \sqrt{N} \times \sqrt{N}$ ). Si on est capable de trouver une décomposition comme une différence de deux carrés, autrement dit si $N = a^2 - b^2$ alors,

1) $a^2 -N$ est un carré
2) $a \geqslant E( \sqrt{N}) +1$ où $E( \sqrt{N})$ est la partie entière de $\sqrt{N}$ .

Explication: Le 1) est évident. Pour le 2), il faut remarquer que $a^2 = N + b^2 > N$ (strict car $N$ n’est pas un carré) et donc $a > \sqrt{N}$ , ce qui implique $a \geqslant E( \sqrt{N}) +1$ .

Ces deux conditions vont nous permettre, comme vous allez le voir, de donner un algorithme de factorisation.

La méthode de factorisation de Fermat

On note toujours $N$ le nombre à factoriser et on pose $q= E(\sqrt{N})$ . Puisque l’idée est de trouver $a$ et $b$ tels que $N=a^2 -b^2$ et puisqu’on a vu que si $a$ existe alors $a \geqslant q+1$ , alors on va choisir successivement $a=q+1$ , $a=q+2$ , $a=q+3$ , … jusqu’à ce qu’il y ait un $a$ tel que $a^2 - N$ soit un carré. Facile, non ?

Je donne un exemple simple: supposons qu’on souhaite factoriser $N= 799$ . On a $\sqrt{799} \simeq 28,26...$ donc $q=28$ .

On essaye avec $a=q+1 = 29$ . On a $a^2 - N = 29^2 - 799 = 43$ . Ce n’est pas un carré.
On essaye avec $a=q+2 = 30$ . On a $a^2 - N = 30^2 - 799 = 101$ . Ce n’est pas un carré.
On essaye avec $a=q+3 = 31$ . On a $a^2 - N = 31^2 - 799 = 162$ . Ce n’est pas un carré.
On essaye avec $a=q+4 = 32$ . On a $a^2 - N = 32^2 - 799 = 225$ qui est un carré !

Comme $225 = 15^2$ , on pose $b=15$ , et on a donc la relation $a^2 - N = b^2$ . Ainsi, $N = a^2 - b^2 = 32^2 - 15^2$ . On en déduit que $N=(32+15) (32-15)$ c’est-à-dire $N = 47 \times 17$ .

Raffinement

Dans le cas où le nombre $N$ est très grand, le nombre d’étapes et de calculs est potentiellement très élevé. Pour que cette méthode soit utilisable d’un point de vue pratique, il va falloir minimiser le nombre de calculs, et pour cela, on va essayer de voir comment réutiliser les calculs déjà effectués au fur et à mesure. En particulier il va être possible de calculer les $a^2 - N$ facilement.

Puisqu’on pose successivement $a=q+1$ , $a=q+2$ , etc. nous allons donc utiliser la notation $a_k = q + k$ . Essayons de trouver une relation de récurrence:

$a_{k+1} - N^2 = ((q+k)+1)^2 - N = (q+k)^2 + 2 (q+k) + 1 - N$

En réarrangeant les termes, on a donc:

$a_{k+1} - N^2 = (q+1)^2 - N + 2(q+k) + 1$

Nous voyons donc que:

$\boxed{ a_{k+1}^2 - N = a_k ^2 - N + 2 a_k + 1}$

Il reste maintenant à voir sur un exemple pratique comment utiliser cette relation de récurrence pour exécuter la méthode de Fermat.

Un exemple donné par Fermat lui-même

Fermat avait expliqué cette méthode dans une lettre datant de 1643 et dans laquelle il expliquait comment factoriser le nombre 2 027 651 281:

(Cette image est extraite de: Œuvres de Fermat, publiées par les soins de MM. Paul Tannery et Charles Henry sous les auspices du Ministère de l’instruction publique. On peut trouver ce livre en ligne ici !)

Voici ce que l’exemple de Fermat donne sous forme de tableau (avec des notations modernes):

Vous voyez que ce tableau est très facile à remplir car:

$a$ augmente de 1 à chaque fois
$2a+1$ augmente de 2 à chaque fois
$a^2-N$ s’obtient en faisant la somme des deux cases situées au-dessus (à la manière du triangle de Pascal) et cela vient de la relation de récurrence que nous avons exhibée plus haut. Il n’y a donc aucune multiplication à faire, ni aucun carré à calculer ! (à part pour la première ligne bien sûr).

Dans l’exemple ci-dessus, on s’est arrêté dès qu’on est tombé sur un carré dans la dernière colonne: en effet, on a 1040400 = 1020² et donc, comme énoncé par Fermat dans son texte, on a

$N = 45 041^2 -1020^2 = (45 041+1020)(45 041-1020) = 46 061 \times 44 021$

Remarque: Comme vous l’avez sans doute constaté dans la lettre, Fermat savait directement reconnaître si un nombre n’est pas un carré, s’épargnant ainsi un calcul de racine carrée. Il utilisait la condition nécessaire suivante: si un nombre est un carré alors ses deux derniers chiffres sont 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, ou 96 (mais attention, ce n’est pas une condition suffisante). Dans l’exemple ci-dessus, vous voyez tout de suite dans la dernière colonne que les seuls nombres qui peuvent potentiellement être des carrés sont 499 944 et 1 040 400.

Retour sur la blague de Mersenne

J’ai implémenté la méthode de Fermat en Python et pour $N=100 895 598 169$ (donc $q=E(\sqrt{100 895 598 169}) = 317640$ ), on trouve qu’il faudrait $k=187723$ étapes avant que l’algorithme se termine ! Et on a alors

$a^2-N=(q+k)^2 - N = (317640+187723)^2 - 100 895 598 169 = 154496163600$

qui est le carré de $b=393060$ . Ainsi, on a

$N=(a+b)(a-b) = (q+k +b) (q+k -b)$

donc

$N= (317640+187723+393060) \times (317640 + 187723 - 392060)$

c’est-à-dire

$N= 898423 \times 112303$

On retrouve bien la réponse donnée par Fermat à Mersenne. Cependant, il est très peu probable que Fermat se soit tapé à la main le calcul des 187 723 étapes (sauf s’il aimait se faire mal…) et il n’a donc probablement pas utilisé cette méthode pour répondre au problème de Mersenne (mais au moins ça nous a donné une occasion de parler de cette méthode…). Mais alors, comment ce filou a-t-il donc fait, nom d’une pipe en acajou ?

Des explications possibles

Voici ci-dessous trois hypothèses possibles (la plus probable et la plus vraisemblable étant la première je pense):

Hypothèse n°1: les nombres parfaits multiples

Si on retranscrit fidèlement la correspondance de Fermat, le problème de la factorisation du nombre 100 895 598169 intervient à l’intérieur d’un problème sur les nombres parfaits multiples. Voici un extrait plus long de la lettre de Fermat à Mersenne:

Traduction : Ce que demandait plus globalement Mersenne à Fermat, c’est de dire si oui ou non la somme des diviseurs propres (« parties aliquotes ») du nombre:

$N = 214 748 364 800 000 \times 11 \times 19 \times 43 \times 61 \times 83 \times 169 \times 223 \times 331\times 379\times 601 \\ \times 757 \times 961 \times 1201 \times 7 019 \times 823 543 \times 616 318177 \times 6 561 \times 100 895 598 169$

est égale à un multiple de $N$ (les diviseurs propres sont les diviseurs de N différents de N). Une explication probable du raisonnement que Fermat aurait suivi pour factoriser 100 895 598 169 est donnée par la note de l’éditeur des Oeuvres de Fermat (de l’édition que j’ai cité plus haut dans l’article). Mais, telle qu’elle est écrite, on n’y comprend rien, donc la voici rédigée dans le fichier PDF ci-dessous :

Comment Fermat a-t-il factorisé 100 895 598 169 ?

Il s’agit de l’explication la plus probable car elle permet de répondre en même temps aux deux questions que Mersenne posait.

Hypothèse n°2: l’astuce de calcul ad hoc

Fermat se serait rendu compte que sa méthode n’aboutirait pas rapidement et donc, plutôt que de factoriser $N$ , il se serait dit « pourquoi ne pas factoriser un multiple de $N$ , quitte à rediviser par ce multiple ensuite ? » Et voici ce que ce qu’il aurait peut-être fait: il aurait multiplié $N$ par 32, ce qui donne $32 N = 3228659141408$ et il se serait rendu compte que ce nombre est presque un carré. Plus précisément, $32 N +1 =3228659141409 = (1796847)^2$ (rappelons que Fermat savait reconnaître rapidement si un nombre n’est pas un carré et qu’il savait extraire une racine carré sans trop de difficulté). Ainsi,

$32N = (1796847)^2 - 1 = (1796847+1) (1796847 -1) = 1796848 \times 1796846$

Puis, il suffit de diviser par 32, en remarquant que le premier facteur est divisible par 16 et le deuxième est divisible par 2:

$N = \dfrac{1796848 }{16} \times \dfrac{1796846}{2}$

et donc on trouve bien:

$N = 112 303 \times 898 423$

L’idée de trouver une décomposition en différence de deux carrés d’un multiple de $N$ est l’idée de base d’un crible moderne appelé crible quadratique, où le principe est de chercher deux nombres $a$ et $b$ tels que $a^2 \equiv b^2 \mod[N]$ . On peut imaginer que Fermat avait eu l’intuition de cette méthode déjà à l’époque.

Hypothèse n°3: la méthode de Daniel Perrin

Daniel Perrin a donné une autre explication possible, mais je ne vais pas rentrer dans les détails de celle-ci (car cet article commence à devenir un peu long !). Vous pouvez lire cette explication très intéressante (qui est un raffinement de la méthode de Fermat) en annexe de ce document qu’il a posté sur sa page.

Quelques notes en guise de conclusion:

■ En pratique, la méthode de factorisation de Fermat est plutôt longue, et le nombre d’étapes nécessaires est en moyenne souvent très élevé. Elle n’est donc quasiment pas utilisée de nos jours, mais elle a donné naissance à d’autres algorithmes comme la méthode de Dixon et la très efficace méthode du crible quadratique.

■ Dans sa réponse, Fermat affirmait que 898 423 et 112 303 sont des nombres premiers. Pour le vérifier, Fermat a sans doute utilisé la méthode du crible d’Ératosthène. Par exemple, comme la racine carrée de 898 423 est environ 947, il suffit de montrer que 898 423 n’est divisible par aucun des nombres premiers inférieurs ou égaux à 947 (en faisant une bête division euclidienne). Sachant qu’il n’y a que 161 tels nombres premiers, cela pouvait se faire à la main en l’espace d’une journée. Dans le cas de 112 303, il n’y a que 67 nombres premiers à tester.

■ Ce problème de la factorisation de N=100 895 598 169 est cité dans l’article Wikipédia sur le petit théorème de Fermat:Contrairement à ce qui est suggéré, le petit théorème de Fermat n’a pas du tout été utilisé et ne permet certainement pas de donner les facteurs de la décomposition d’un nombre qui n’est pas premier ! Tout au plus il permet de montrer que N n’est pas premier mais utiliser ce théorème pour cela serait une douce folie car il faudrait montrer que:

$\exists a : a^{100895598168} \not\equiv 1 \mod [100895598169]$

ce qui du point de vue du calcul, serait plutôt long…. surtout si, comme Fermat, vous n’avez pas de calculatrice ! (Heureusement, de nos jours on possède de rapides ordinateurs et on peut voir en une fraction de seconde que si a=2 alors le reste n’est pas 1).

Références:

✓ Voici un article détaillant la note de l’éditeur qui donnait la méthode probable utilisée par Fermat. (c’est de cet article que je me suis inspiré pour rédiger l’hypothèse n°1 et, pour ça, j’ai dû me mettre à l’italien… Faut être polyglotte pour faire des maths, je vous jure…):
Giuseppe Palamà – Su di una regola di Fermat per la fattorizzazione dei numeri e su di una sua questione relativa alle parti aliquote.

✓ Pour l’aspect historique de l’étude des nombres multiples parfaits (y compris le résumé des correspondances entre Fermat, Descartes, Mersenne et d’autres), vous pouvez consulter le chapitre I de:
L.E. Dickson – History of the Theory of Numbers, Volume I: Divisibility and Primality

Merci à @blogdemath pour cet article.
Source : https://blogdemaths.wordpress.com/2014/05/18/savez-vous-factoriser-a-la-mode-de-fermat/

Laisser un commentaire X