Pourquoi est-il si difficile de décomposer un grand nombre en nombres premiers ?

Décomposer un grand nombre en nombres premiers est difficile parce que personne ne connaît de raccourci. Multiplier est facile, mais revenir en arrière, retrouver quels nombres premiers ont été multipliés, semble exiger une recherche. Pour les petits nombres, il suffit d'essayer de diviser par 2, 3, 5 et ainsi de suite jusqu'à la racine carrée. Pour les nombres énormes, cette recherche explose : plus le nombre a de chiffres, plus le travail exigé de n'importe quel ordinateur classique augmente de façon vertigineuse. On ne connaît aucune méthode efficace, même si personne n'a prouvé qu'il n'en existe pas.

Les cas les plus durs sont les nombres obtenus en multipliant deux grands nombres premiers de taille voisine. Ce n'est pas un hasard : ce sont les clés du chiffrement RSA. Si quelqu'un trouvait une façon rapide de factoriser, RSA ne serait plus sûr.

La plus belle histoire est une énigme de magazine. En août 1977, la rubrique de Martin Gardner dans Scientific American cache un message derrière un nombre de 129 chiffres. Il résiste jusqu'en avril 1994, quand environ 600 bénévoles prêtent quelque 1 600 ordinateurs reliés par Internet pour le casser. Le message secret disait : The Magic Words are Squeamish Ossifrage. En 2015, le même travail prenait environ une journée et 30 dollars de calcul dans le cloud.

La vraie menace pourrait être quantique. En 1994, Peter Shor a trouvé un algorithme qui factoriserait rapidement sur un ordinateur quantique, mais il pourrait falloir des machines à des millions de qubits.