Décomposition en produit de facteurs premiers

En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers, aussi connue comme la factorisation entière en nombres premiers, consiste à chercher à écrire un entier supérieur ou égal à 2 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 x 3 x 5.

Le facteur trivial « 1 » n'est pas mentionné.

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.

11 = 11

25 = 5 × 5 = 5²

125 = 5 × 5 × 5 = 5³

360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5

1 001 = 7 × 11 × 13

1 010 021 = 17 × 19 × 53 × 59

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.

Sommaire

1 Décomposition en produit de nombres premiers
2 Utilisations élémentaires
3 Algorithmes de factorisation
4 Notes et références
5 Liens externes

Décomposition en produit de nombres premiers

Le théorème fondamental de l'arithmétique permet d'affirmer que tout entier supérieur ou égal à 2 possède une 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 à 2, il existe une suite finie unique (p₁;α₁) ... (p_i;α_i) ... telle que :

les p_i sont des nombres premiers tels que, si i < j, alors p_i < p_j ;
les α_i sont des entiers naturels non nuls
n est le produit des nombres p_i^α_i.

Une définition plus formelle de la décomposition en facteurs premiers^[1] permet d'attribuer également à l'entier 1 une décomposition unique en facteurs premiers. Elle 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^k divise n. Cet entier se note $v p (n)$ et s'appelle valuation p-adique de l'entier n

Ainsi $v p (1) = 0$ pour tout nombre premier p, $v 3 (45) = 2$ et $v 5 (45) = 1$ .

Si on note alors $\mathcal P$ l'ensemble de tous les nombres premiers, tout entier naturel non nul n peut s'écrire sous la forme du produit

$n = \prod_{p\in\mathcal{P}} p^{v_p(n)}$ .

Les $v p (n)$ étant nuls sauf un nombre fini d'entre eux, ce produit infini est en fait un produit fini. Cette écriture est unique, c'est-à-dire que, s'il existe une famille $(\alpha_p)_{p \in \mathcal P}$ d'entiers naturels, tous nuls sauf un nombre fini d'entre eux, telle que

$n = \prod_{p\in\mathcal{P}} p^{\alpha_p}$ ,

alors pour tout p, $α p = v p (n)$ . On appelle alors cette écriture la décomposition en produits de facteurs premiers de n.

Utilisations élémentaires

L'écriture d'un entier sous forme d'un produit de facteurs premiers permet de simplifier le travail sur les produits, les multiples et les diviseurs. Elle permet aussi de trouver des formes réduites pour des quotients ou des racines

Multiples et diviseurs

On suppose par la suite que la décomposition de n en produit de facteurs premiers s'écrit $\prod_{i=1}^kp_i^{\alpha_i}$

L'entier m est un multiple de n si et seulement si la décomposition de m en produit de facteurs premiers contient au moins tous les $p i$ élevés à une puissance $β i$ supérieure ou égale à $α i$ .

L'entier d est un diviseur de n si et seulement s'il existe k entiers $δ i$ vérifiant $0 \le \delta_i\le \alpha_i$ tels que $d=\prod_{i=1}^kp_i^{\delta_i}$

Sous cette forme il est alors possible de faire l'inventaire de tous les diviseurs de n et d'en déterminer le nombre :

Ainsi les diviseurs de 45 sont : $3^0\times 5^0$ - $3^1\times 5^0$ - $3^2\times 5^0$ - $3^0\times 5^1$ - $3^1\times 5^1$ - $3^2\times 5^1$ . Soit 6 diviseurs.

Plus généralement, l'entier $n= \prod_{i=1}^kp_i^{\alpha_i}$ possède exactement $\prod_{i=1}^k(\alpha_i+1)$ diviseurs, car un diviseur est constitué en choisissant arbitrairement un exposant pour $p 1$ parmi $α 1 + 1$ valeurs (de 0 à $α 1$ ), un exposant pour $p 2$ parmi $α 2 + 1$ valeurs, etc.

La somme des diviseurs positifs de n est donnée par la formule

$\sigma(n)=\prod_{i=1}^k\frac{p_i^{\alpha_i + 1}-1}{p_i-1}$

PGCD et PPCM

Le PGCD de deux nombres entiers a et b supérieurs ou égaux à 2 a pour décomposition en facteurs premiers le produit des facteurs premiers apparaissant à la fois dans la décomposition de a et de b munis du plus petit des exposants trouvés dans la décomposition de a et de b.

Ainsi si $a = 2^3\times 3^4\times 5^2\times 7$ et $b=2^2\times 3^5\times 7^3\times 11$ alors $\text{pgcd}(a,b) = 2^2\times 3^4\times 7$

Le PPCM de deux nombres entiers a et b supérieurs ou égaux à 2 a pour décomposition en facteurs premiers le produit des facteurs premiers apparaissant dans a ou dans b munis du plus grand des exposants trouvés dans la décomposition de a et de b.

Ainsi si $a = 2^3\times 3^4\times 5^2\times 7$ et $b=2^2\times 3^5\times 7^3\times 11$ alors $\text{ppcm}(a,b) = 2^3\times 3^5\times 5^2\times 7^3\times 11$

Décomposition et valuation

L'écriture de la décomposition sous forme d'un produit infini permet de résumer ces calculs en travaillant seulement sur les valuations.

Diviseur : d divise n si et seulement si, pour tout nombre premier p, $v_p(d) \le v_p(n)$
Produit : la décomposition en facteurs premiers de ab consiste à faire les somme de valuations : $ab = \prod_{p \in \mathcal P}p^{v_p(a)+v_p(b)}$
PGCD : $\text{pgcd}(a,b)= \prod_{p \in \mathcal P}p^{\inf(v_p(a),v_p(b))}$
PPCM : $\text{ppcm}(a,b)= \prod_{p \in \mathcal P}p^{\sup(v_p(a),v_p(b))}$

Formes réduites

La décomposition en produit de facteurs premiers peut se révéler utile pour réduire une fraction en fraction irréductible, pour la décomposer en éléments simples, pour réduire deux fractions au même dénominateur ou pour réduire des expressions contenant des racines carrées ou des racines nième.

Pour réduire une fraction sous forme irréductible, il faut simplifier le numérateur et le dénominateur de la fraction par le PGCD de ces deux nombres. Une écriture des nombres en produit de facteurs premiers rend plus évidente la simplification :

$\frac{1827}{1050}=\frac{3^2\times 7\times 29}{2\times 3\times 5^2\times 7} = \frac{3\times 29}{2\times 5^2}=\frac{87}{50}$

Pour réduire deux fractions au même dénominateur, on peut choisir comme dénominateur commun le PPCM des deux dénominateurs. Là aussi la décomposition en produits de facteurs premiers peut se révéler utile :

$\frac{5}{28}+\frac{3}{70}=\frac{5}{2^2\times 7}+ \frac{3}{2\times 5\times 7} = \frac{5\times \color{Red} 5}{2^2 \times 7\times \color{Red}{5}}+ \frac{3\times \color{Red}2}{2\times 5\times 7\times \color{Red}2} = \dfrac {31}{2^2\times 5\times 7}=\dfrac{31}{140}$

Toute fraction peut s'écrire comme somme ou différence de fractions dont le dénominateur est une puissance de nombre premier. Sous cette forme, appelée décomposition en éléments simples, il est facile de connaitre un développement décimal périodique de la fraction connaissant les périodes de chacune des fractions élémentaires. La décomposition en éléments simples utilise l'identité de Bézout et la décomposition du dénominateur en facteurs premiers.

$\frac{5}{28} = \frac{5}{2^2\times 7}$

On cherche alors deux entiers a et b tels que $5=a\times 2^2 + b \times 7$ . On peut prendre a=-4 et b=3

$\frac{5}{28} = \frac{3\times 7 - 4\times 4}{2^2\times 7} = \dfrac34 - \dfrac{4}{7} = 0,75 - 0,\underline{571428}=0,17\underline{857142}$

Tout entier supérieur ou égale à 2 est un carré si tous les exposants de sa décomposition en produit de facteurs premiers sont pairs. Tout entier supérieur ou égal à deux se décompose en produit d'un carré et d'un nombre dont la décomposition en produits de facteurs premiers ne contient que des exposants égaux à 1. Sous cette forme, il est possible d'écrire une racine carrée sous forme irréductible :

$\sqrt{1188}=\sqrt{2^4\times 3^3\times 11}=\sqrt{(2^2\times 3)^2\times 3\times 11}=12\sqrt{33}$

Cette propriété se généralise à des racines nièmes.

Algorithmes de factorisation

S'il existe un algorithme simple à mettre en place pour décomposer un nombre de taille raisonnable, cet algorithme se révèle rapidement inefficace, en termes de temps, pour des très grands nombres. La recherche d'algorithmes performants est donc un objectif de la théorie des nombres

Algorithme naïf

Article détaillé : Algorithme de décomposition en produit de facteurs premiers.

Il s'agit tout simplement de balayer la liste des nombres premiers en testant si le nombre premier p divise n. Si oui, on recommence l'algorithme pour n/p, en ne testant que les diviseurs premiers encore envisageables. On s'arrête quand le nombre premier à tester devient supérieur à la racine carrée du nombre qu'il est censé diviser.

Ainsi pour décomposer 2088 en produit de facteurs premiers

2088	2	$\,$	2 divise 2088 le quotient est 1044
1044	2		2 divise 1044, le quotient est 522
522	2		2 divise 522, le quotient est 261
261	3		2 ne divise pas 261, mais 3 divise 261 et le quotient est 87
87	3		3 divise 87 et le quotient est 29
29			ni 3, ni 5 ne divisent 29 et 7² est plus grand que 29 (fin)

$2088=2^3\times 3^2\times 29$

Applications pratiques

Soient deux grands nombres premiers donnés, il est facile d'en obtenir le produit. Par contre, il est beaucoup plus difficile de trouver les facteurs premiers de celui-ci. C'est ce que l'on appelle une fonction trappe. Ceci s'applique pour les systèmes modernes en cryptologie. Si une méthode rapide était trouvée pour résoudre le problème de la factorisation des nombres entiers, alors plusieurs systèmes cryptologiques importants seraient cassés, incluant l'algorithme à clé publique RSA et le générateur de nombres pseudo-aléatoires Blum Blum Shub. La mise au point d'un ordinateur quantique est une de ces méthodes.

Bien que la factorisation soit une manière de casser ces systèmes, il peut exister d'autres manières de les casser qui n'impliquent pas la factorisation. Ainsi, il est possible que le problème de la factorisation entière soit vraiment difficile, mais ces systèmes peuvent quand même être cassés rapidement. Une exception rare est le générateur Blum Blum Shub. Il a été prouvé qu'il est exactement aussi difficile que la décomposition en produit de facteurs premiers : si vous pouvez casser le générateur en temps polynomial alors, vous pouvez factoriser les entiers en temps polynomial, et vice versa.

État actuel de l'art

Si un grand nombre à n-bit est le produit de deux nombres premiers qui sont probablement de la même taille, alors aucun algorithme n'est actuellement connu pour pouvoir le factoriser en temps polynomial. Ce qui veut dire qu'il n'existe pas d'algorithme connu pouvant le factoriser en temps O(n^k) quelle que soit la constante k. Il existe des algorithmes, néanmoins, qui sont aussi rapides que Θ(eⁿ). En d'autres termes, les meilleurs algorithmes connus sont sous-exponentiels, mais super-polynômiaux. En particulier, le meilleur algorithme connu s'exécutant en temps asymptotique est le crible général de corps de nombres (GNFS).

Pour un ordinateur ordinaire, GNFS est le meilleur algorithme connu pour les grands n. Pour un calculateur quantique, en revanche, Peter Shor a découvert un algorithme en 1994 qui le résout en temps polynomial. Ceci aura des implications significatives pour la cryptologie si un grand calculateur quantique est construit un jour. L'algorithme de Shor prend seulement O(n³) de temps et O(n) d'espace. Les formes de l'algorithme sont connues pour utiliser seulement 2n qubits. En 2001, le premier calculateur quantique 7-qubit devint le premier à exécuter l'algorithme de Shor. Il factorisa le nombre 15 en 5 x 3.

Article détaillé : Algorithme de Shor.

Difficulté et complexité

On ne connaît pas exactement quelles classes de complexité contiennent le problème de la décomposition en produit de facteurs premiers. Le problème de décision de forme ("N a-t-il moins de facteurs que M ?") est connu pour être à la fois NP et co-NP. Ceci parce que les réponses OUI et NON peuvent être cochées si les facteurs premiers sont donnés avec leurs preuves de primalité. Il est connu comme étant dans BQP à cause de l'algorithme de Shor. Il est suspecté d'être en dehors des trois classes de complexité P, NP-complet, et co-NP-complet. S’il peut être démontré qu'il est soit NP-Complet ou co-NP-Complet, cela impliquerait NP = co-NP. Ce serait un résultat très surprenant, par conséquent la factorisation entière est largement suspectée d'être en dehors de ces classes. Beaucoup de personnes ont essayé de trouver des algorithmes en temps polynomial pour cela et ont échoué; par conséquent, elle est largement suspectée d'être en dehors de P.

De manière intéressante, le problème de décision « N est-il un nombre composé ? » (ou de façon équivalente : « N est-il un nombre premier ? ») apparaît comme étant plus facile que le problème consistant à trouver les facteurs de N. Plus précisément, la question ci-dessus peut être résolue en temps polynomial (en nombre n des chiffres de N), en accord avec l'article récent donné dans les références ci-dessous. De plus, il existe un nombre d'algorithmes probabilistes qui peuvent tester la primalité d'un nombre très rapidement si l'un d'eux est susceptible d'accepter une petite possibilité d'erreur. La facilité de test d'un nombre premier est une partie cruciale de l'algorithme RSA, comme il est nécessaire de trouver de grands nombres premiers pour démarrer avec lui.

But spécial

Les temps d'exécution des algorithmes de factorisation à but spécial dépend des propriétés de ses facteurs inconnus : taille, forme spéciale, etc. De manière exacte, le temps d'exécution dépend de ce qui varie entre les algorithmes.

But général

Le temps d'exécution des algorithmes de factorisation à but général dépend seulement de la taille de l'entier à factoriser. Ceci est le type d'algorithme utilisé pour factoriser les nombres RSA. La plupart des algorithmes de factorisation à but général sont basés sur la méthode des congruence de carrés.

Notes et références

↑ Louis Comtet, Analyse combinatoire élémentaire, chap 1.4 p.68

Liens externes

(en) Article « PRIMES is in P »L'article de Manindra Agrawal, Nitin Saxena, Neeraj Kayal qui montre que déterminer si un nombre est premier est un problème de complexité polynomial (PDF)
(fr) Applet Java basé sur le travail de Alejandro Alpern
(en) http://www.alpertron.com.ar/ECM.HTM est une applet Java de factorisation entière qui utilise la méthode des courbes elliptiques et le crible quadratique d'auto-initialisation (Self Initializing Quadratic Sieve) (en anglais).
programme de factorisation entière du domaine public pour Windows Il peut prendre en charge des nombres de 80 chiffres. Voir aussi le site web pour MIRACL

Portail des mathématiques

Catégories :

Divisibilité et factorisation
Algorithme de factorisation des entiers

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Décomposition en produit de facteurs premiers de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

Decomposition en produit de facteurs premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français
Décomposition En Produit De Facteurs Premiers — En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème suivant : soit un entier strictement positif,… … Wikipédia en Français
Algorithme De Décomposition En Produit De Facteurs Premiers — En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un entier est « décomposé » en un produit de facteurs… … Wikipédia en Français
Algorithme de decomposition en produit de facteurs premiers — Algorithme de décomposition en produit de facteurs premiers En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un… … Wikipédia en Français
Algorithme de décomposition en produit de facteurs premiers — En mathématiques, dans la branche de l arithmétique modulaire, un algorithme de décomposition en produit de facteurs premiers est un algorithme (un processus pas à pas) par lequel un entier est « décomposé » en un produit de facteurs… … Wikipédia en Français
Table des décompositions en produit de facteurs premiers de nombres U1 — Factorisation des nombres uniformes Cette table contient les décompositions en produit de facteurs premiers des nombres uniformes de la classe U1 (répunit) de U1 jusqu à U50. Nombre uniforme de la classe U1 Décomposition en produit de facteurs… … Wikipédia en Français
Décomposition en facteurs premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français
Facteurs premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français
Table des facteurs premiers — Cette table contient la décomposition en produit de facteurs premiers des nombres de 1 à 1000. Lecture du tableau la fonction additive a0(n) a pour valeur la somme des facteurs premiers de n lorsque n est premier, le facteur est en gras par… … Wikipédia en Français
Décomposition en nombres premiers — Décomposition en produit de facteurs premiers En mathématiques et plus précisément en arithmétique modulaire, la décomposition en produit de facteurs premiers (aussi connue comme la factorisation entière en nombres premiers) est le problème… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Décomposition en produit de facteurs premiers

Sommaire

Décomposition en produit de nombres premiers