« La percée mathématique évidente serait le développement d'un moyen simple de factoriser les grands nombres en facteurs premiers. » [Bill Gates]

Non, je ne donnerai pas la clé du code de mon dernier article, vous n'avez qu'à trouver seuls la factorisation de 284191[...]27. Peut-être pas aujourd'hui, parce que nos ordinateurs en sont parfaitement incapables, mais peut-être que dans quelques années, si la puissance de nos ordinateurs évoluent et que les mathématiciens font bien leur boulot, la factorisation d'un nombre énorme sera quelque chose de faisable...

Mais au fait, pourquoi sommes nous aujourd'hui incapables de factoriser le n de mon précédent article ? Si tout va bien, je devrais y répondre au cours de cette note...

Digressons un peu : petite FAQ sur les nombres premiers ?

Qu'est ce qu'un nombre premier ?
Officiellement, c'est un nombre qui a exactement deux diviseurs : 1 et lui-même. Le genre de nombre impossible à diviser sous peine de se retrouver avec un nombre à virgule.
Qui donc a inventé ces nombres ?
Il s'agit apparemment de Grümf, le même qui a inventé la roue, il y a 23 000 ans...
Laurence Boccolini m'a dit que 1 était le premier nombre premier. C'est vrai ou pas ?
C'est faux, arrête de regarder TF1, ça ne te réussis pas. 1 n'est pas premier, il suffit de relire la définition : c'est un nombre qui a exactement deux diviseurs. Le nombre 1 ne possède qu'un seul diviseur, je vous laisse deviner lequel.
Et pourquoi on met le nombre 1 à l'écart comme ça ?
Parce que c'est bien plus pratique comme ça. Un théorème (appelé aussi théorème fondamental de l'arithmétique, ça serait dommage de l'infirmer) nous dit que tous les entiers naturels possèdent une décomposition unique en un produit de facteurs premier (aux permutations près). Par exemple, on a 12=2×2×3. Si 1 était un nombre premier, on aurait également 12=1×1×2×2×3, et la décomposition ne serait plus unique. Ca lui apprendra à être l'élément neutre de la multiplication !
Y'en a combien, des nombres premiers ?
Il y en a autant qu'on veut. Une infinité, quoi... Vous imaginez ce qu'il se passerait s'il y en avait un nombre fini ? Il suffirait de multiplier ensemble tous ces nombre premiers et d'y ajouter 1 pour se retrouver avec un nouveau nombre premier, ce qui serait embêtant...
C'est lequel le plus grand ?
Je viens de dire qu'il y en avait une infinité... Cependant, le plus grand que l'on ait calculé est un nombre de Mersenne, c'est à dire, de la forme 2n+1, avec n=32 582 657. Ca donne un nombre composé de 9 808 358 chiffres.


Maintenant cette petite mise au point faite, interressons-nous à cette histoire de factorisation. La force de l'algorithme RSA, c'est qu'il s'appuie sur la difficulté de décomposer un nombre composé en produit de nombre premiers, d'autant plus que les facteurs premiers sont de taille conséquentes.

Pour décomposer un nombre, la technique la plus simple est de tester un à un tous les nombres premiers pour voir s'ils divisent notre nombre.
Prenons 140.
2 est un diviseur de 140. On le garde de côté, il reste 70.
2 est encore un diviseur de 70. On le garde de côté, il nous reste 35.
2 n'est pas diviseur de 35, on passe donc au nombre premier suivant, c'est à dire 3.
En procédant ainsi, on trouvera facilement que 140=2×2×5×7.

Maintenant, si on s'amuse à chercher de la même façon pour décomposer 6887, on passera beaucoup plus de temps, puisqu'il faudra tester tous les nombres premiers uns à uns jusqu'à 71 avant de trouver que 6887=71×97.

Quand notre nombre à factoriser possède 309 chiffres, comme dans une clé de cryptage RSA classique, on ne peut pas décemment envisager le fait de tester tous les nombres premiers (ne serait-ce parce qu'il y en a au moins 10305).

Evidement, les algorithmes que l'on utilise en réalité sont plus efficaces que celui-ci, mais aucun d'eux n'arrive à donner des décompositions de gros nombres dans des temps raisonnables. En effet, les temps de calculs ne sont pas proportionnels à la longueur des nombres, mais à leur exponentielle. Ces algorithmes peuvent être rapides quand les nombres sont le produit de nombreux petits nombres premiers, mais dans le cas où l'on cherche à factoriser de grands nombres semi-premiers (un nombre produit de deux nombres premiers), l'attente serait vraiment trop longue.

L'idéal serait de trouver un algorithme rapide permettant de décomposer un nombre. Peut-être pas avec un temps de calcul proportionnel à la taille du nombre, mais au moins proportionnel à son carré, son cube ou autre... Un algorithme polynomial, en fait. Peut-être il existe, mais repose sur une propriété que l'on ne connait pas encore... Peut-être il n'existe pas, mais il faudrait le démontrer... Le mathématicien ou l'informaticien qui réussirait à répondre à cette question pourra finir ses jours heureux, vu l'argent en jeu...

En effet, le laboratoire RSA a lancé son propre concours : décomposez-moi ce nombre, et gagnez une somme conséquente en dollars. 200 000 $ sont prévus pour celui qui pourra donner les diviseurs premiers d'un nombre à 617 chiffres. Pour ceux qui visent moins haut, 30 000 $ sont prévus pour la factorisation d'un nombre à 211 chiffres. Ce challenge est plutôt réservé aux laboratoires qui prennent le temps de faire tourner leur ordinateur plusieurs mois durant, mais si vous vous ennuyez, vous pouvez toujours tester de multiplier des nombres au hasard. Mais c'est surtout un bon indicateur de la puissance des ordinateurs et des mathématiques.

Bref, tout ça pour dire qu'il faut faire attention à cette histoire de challenge RSA. Le jour où les 200 000 $ auront été gagnés, il faudra arrêter de se servir de sa carte bleue... Enfin, surtout pour Bill Gates, qui nargue tout le monde avec son argent protégé par des nombres à factoriser...


Sources :
Ben... Wikipedia !
Le challenge RSA