Le processus de décomposer un entier composé en un produit d'entiers plus petits, typiquement en facteurs premiers ; pour n>1 il s'agit de produire un multiensemble {p_i} de nombres premiers tel que n=∏ p_i^{e_i}.

Principe

La factorisation d'entiers exploite la structure arithmétique (divisibilité, ordre d'éléments modulo n, factorisations algébriques) et des techniques algorithmiques (division d'essai, cribles, rho de Pollard, méthodes par courbes elliptiques, crible général de corps de nombres) pour retrouver des facteurs non triviaux ; sa difficulté est la base de nombreuses hypothèses cryptographiques.

Démonstration

Algorithmes concrets : la division d'essai trouve rapidement les petits facteurs premiers ; Pollard rho trouve des facteurs modérés via marches pseudo-aléatoires ; la méthode ECM est efficace pour des facteurs premiers de taille moyenne ; le crible général de corps de nombres (GNFS) est la méthode asymptotiquement la plus rapide connue pour les grands entiers généraux utilisés dans les records de factorisation.

Mauvaise application

Supposer qu'une heuristique unique ou un algorithme à petits paramètres factorisera efficacement tous les entiers (par exemple attendre que Pollard rho réussisse sur des semiprimes avec des facteurs premiers très grands), ou confondre la factorisation d'entiers avec la factorisation de polynômes ou avec le test de primalité.

Conséquence

La factorisation réussie fournit l'information arithmétique complète sur n (sa décomposition en premiers) et compromet les schémas cryptographiques fondés sur la difficulté présumée de la factorisation ; les progrès algorithmiques modifient le seuil de sécurité pratique et motivent des recommandations sur la taille des clés.

Inversion

L'inversion est le test de primalité : plutôt que produire des facteurs, on décide si n est premier ; une décision positive de primalité rend la factorisation inutile, tandis que la factorisation fournit une information strictement plus forte et généralement plus difficile à obtenir.

Limite

La tâche s'applique aux entiers fournis sous représentation standard ; exclut la factorisation d'idéaux dans des corps de nombres, la factorisation de polynômes sur des corps (algorithmes et complexité différents), et les problèmes où la forme spéciale d'un entier ou une structure auxiliaire peut être exploitée séparément.

Tension sémantique

Tension entre la complexité théorique dans le pire cas et la difficulté pratique 'typique' : certains entiers (formes spéciales) se factorisent facilement alors que les semiprimes aléatoires de grande taille résistent à tous les algorithmes connus ; on confond aussi parfois la factorisation d'un entier avec le calcul de structures multiplicatives dans d'autres objets algébriques.

Synthèse

La factorisation d'entiers est la tâche computationnelle de décomposer un entier en constituants premiers en utilisant un ensemble d'algorithmes qui exploitent la divisibilité et la structure algébrique ; sa difficulté pratique dépend de la taille et de la forme particulière des facteurs et a des conséquences centrales pour la théorie algorithmique des nombres et la cryptographie.