Décomposition en produit de facteurs premiers
vignette|Décomposition du nombre 864 en facteurs premiers En mathématiques et plus précisément en arithmétique, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers ou encore plus couramment la décomposition en facteurs premiers, consiste à chercher à écrire un entier naturel non nul sous forme d'un produit de nombres premiers. Par exemple, si le nombre donné est 45, la factorisation en nombres premiers est 3 × 5, soit 3 × 3 × 5. Par définition, un nombre premier ne peut pas être décomposé en produit de plusieurs nombres premiers. On peut aussi dire qu'il est sa propre décomposition. Quant au nombre 1, c'est le produit vide. La factorisation est toujours unique, en accord avec le théorème fondamental de l'arithmétique. L'écriture des nombres entiers en produits de facteurs premiers en facilite la manipulation dans des problèmes de divisibilité, de fraction ou de racine carrée. La recherche d'algorithmes de décomposition est d'une importance considérable en mathématiques, en cryptologie, en théorie de la complexité des algorithmes, et pour les calculateurs quantiques. En 2020, un nombre de 250 chiffres (RSA-250) a été décomposé en facteurs premiers en utilisant environ 2700 cœurs.ans de calcul. Le théorème fondamental de l'arithmétique permet d'affirmer que tout entier strictement positif possède une unique décomposition en facteurs premiers. C'est-à-dire qu'il peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance adéquate. Pour tout nombre entier naturel n supérieur ou égal à 1, il existe une suite finie unique (p, k) ... (p, k) telle que : les p sont des nombres premiers tels que, si i < j, alors p < p ; les k sont des entiers naturels non nuls ; n est le produit des nombres p. Une définition plus formelle de la décomposition en facteurs premiers fait appel à la notion de valuation p-adique. Pour tout nombre premier p et tout entier naturel n non nul, on détermine le plus grand entier naturel k tel que p divise n.
