Décomposition en facteurs premiers

Qu’est-ce que la décomposition en facteurs premiers ?

Tout entier supérieur à un est soit premier — divisible seulement par lui-même et par un — soit un produit de nombres premiers, et ce produit est unique à l’ordre près. C’est le théorème fondamental de l’arithmétique, et décomposer consiste à le trouver : 360 vaut 2 × 2 × 2 × 3 × 3 × 5, que l’on écrit 2³ × 3² × 5, et aucune autre combinaison de premiers ne donne 360.

C’est l’opération qui se cache sous une bonne partie de l’arithmétique ordinaire. Réduire une fraction, c’est simplifier des facteurs premiers communs. Un plus petit dénominateur commun se construit à partir des premiers de chaque dénominateur, en gardant la plus grande puissance de chacun. Et le nombre de diviseurs se lit directement dans la décomposition : multipliez chaque exposant augmenté de un, si bien que 360 = 2³ × 3² × 5¹ possède 4 × 3 × 2 = 24 diviseurs, que l’outil énumère.

Ce calculateur travaille en arithmétique entière exacte et non en virgule flottante : il n’existe donc aucune taille à partir de laquelle les réponses deviendraient discrètement approximatives. Collez un nombre de quarante chiffres et chaque facteur renvoyé sera exactement juste.

Comment s’en servir

1. Tapez ou collez un nombre entier. Virgules, espaces et tirets bas sont ignorés : un nombre copié depuis un tableur fonctionne tel quel. Décimales, signe moins et notation exponentielle sont refusés plutôt que réinterprétés en silence.
2. Lisez la décomposition et les diviseurs. Les nombres composés apparaissent en forme exponentielle avec tous leurs facteurs premiers, plus le nombre de diviseurs et, quand la liste reste raisonnable, tous les diviseurs. Un nombre premier est simplement signalé comme premier.
3. S’il dit qu’il n’a pas fini, croyez-le. Les nombres difficiles atteignent une limite de travail et l’outil vous le dit, en montrant ce qu’il a trouvé et ce qui reste. Le bouton propose une recherche plus longue ; si elle échoue aussi, le nombre est réellement hors de portée d’un navigateur en un temps raisonnable.

Pourquoi certains nombres l’arrêtent, et pourquoi c’est là tout l’intérêt

Décomposer est infiniment plus facile pour certains nombres que pour d’autres, et l’écart ne tient pas à la taille. Retirer les petits facteurs premiers règle la plupart des cas instantanément, parce que la plupart des nombres ont un petit facteur : sur quarante nombres aléatoires de quarante chiffres, celui du milieu se décompose en un sixième de seconde environ. Ce qui est dur, c’est un nombre sans aucun petit facteur : un semi-premier, produit de deux grands nombres premiers et de rien d’autre.

La méthode naïve le rend saisissant. La division d’essai teste tous les candidats jusqu’à la racine carrée, si bien que son coût double environ tous les deux chiffres : sur la machine où cette page a été construite, un semi-premier fait de deux premiers à dix chiffres a demandé trois secondes, et un fait de deux premiers à onze chiffres trois minutes et demie. Cet outil emploie plutôt le rho de Pollard, qui a fait passer ce même cas à onze chiffres de 212 secondes à 68 millisecondes — trois ordres de grandeur, pour un algorithme qui tient en vingt lignes.

Mais le rho ne fait que déplacer le mur, il ne le supprime pas. Un semi-premier fait de deux premiers à treize chiffres reste hors de portée d’un onglet de navigateur, et ce n’est pas une faiblesse dont il faudrait s’excuser. C’est le fondement même de la cryptographie à clé publique : les clés RSA sont des semi-premiers choisis précisément parce que multiplier deux grands premiers est trivial et que le défaire ne l’est pas. Les nombres qui protègent votre banque ont la même forme que celui sur lequel cette page renonce, en beaucoup plus grand.

Voilà pourquoi la limite est ici un budget de travail et non un plafond de chiffres. Un plafond de chiffres se tromperait dans les deux sens : il refuserait le nombre de quarante chiffres qui se décompose en une milliseconde et accepterait celui de vingt-cinq qui prend plusieurs secondes. Compter l’effort permet à l’outil de s’arrêter quand le travail devient déraisonnable, quelle que soit l’allure du nombre, et de le dire honnêtement plutôt que de figer l’onglet.

Limites assumées

Quand la recherche s’arrête tôt, tout ce qui s’affiche reste vrai. Les facteurs trouvés sont bien des facteurs premiers de votre nombre ; ce qui reste n’a simplement pas été décomposé. Multipliez les facteurs affichés par le reste et vous retombez exactement sur votre nombre — cette propriété tient à tous les budgets, et c’est elle que les tests vérifient le plus âprement, car une réponse partielle qui se donne pour complète est bien pire qu’une qui avoue s’être arrêtée.

La primalité est tranchée par le test de Miller-Rabin avec un jeu fixe de douze témoins. Cette combinaison est prouvée correcte pour tout nombre inférieur à environ 3,3 × 10²⁴, ce qui couvre tout ce que cet outil recevra en pratique ; au-delà, il devient un test probabiliste et non une preuve, et le risque d’erreur est infime sans être nul. Presque aucun calculateur ne précise de quel côté de cette ligne il se trouve.

Zéro et un reçoivent leurs propres réponses plutôt qu’un résultat vide. Zéro n’a pas de décomposition, puisque tous les nombres le divisent. Un n’est ni premier ni composé — il n’a aucun facteur premier —, ce qui relève de la définition et non d’un oubli, et explique que le théorème fondamental commence à deux.

La liste des diviseurs est plafonnée à l’affichage, car un nombre très composé peut en avoir des milliers et les montrer tous n’aide personne. Le compte affiché au-dessus est toujours le total réel, calculé à partir des exposants et non en comptant ce qui est visible.

Pourquoi est-ce gratuit ?

Parce que cela ne coûte rien à faire tourner. Tout le calcul a lieu dans votre navigateur grâce à sa prise en charge native des grands entiers : rien n’est envoyé, aucun serveur ne voit vos nombres, et il n’y a ni compte ni limite au nombre de vérifications.

Le moteur est confronté à un décomposeur écrit indépendamment dans un autre langage, et à quelque chose de plus fort que n’importe quelle implémentation de référence : une décomposition se vérifie en la remultipliant, et les tests le font à tous les budgets de travail jusqu’à zéro. Deux des bogues attrapés ainsi étaient exactement du genre dangereux — une réponse partielle présentée comme complète, et un reste déclaré premier.