Pour trouver la décomposition en produit de facteurs premiers d’un nombre $ N $ il n’existe pas de formule mathématique. Pour y parvenir, il existe des algorithmes dont le plus basique tente de diviser le nombre $ N $ par l’ensemble des facteurs premiers $ p $ qui sont inférieurs à $ N $. Si $ p $ est un diviseur de $ N $ alors recommencer en prenant un nouveau $ N = N/p $ tant qu’il reste des diviseurs premiers envisageables.
Exemple : Soit le nombre $ N = 147 $, les nombres premiers inférieurs à $ N = 147 $ sont $ 2, 3, 5, 7, 11, 13, … $. L’algorithme de décomposition en produit de facteurs premiers de $ 147 $, commencer par tenter la division par $ 2 $, or $ 147 $ n’est pas divisible par $ 2 $. continuer avec la division par $ 3 $, or, $ 147/3 = 49 $ donc $ 147 $ est divisible par $ 3 $ et $ 3 $ est un facteur premier de $ 147 $. Dans la suite, ne plus considérer $ 147 $ mais $ 147/3 = 49 $. Les nombres premiers inférieurs à $ 49 $ sont $ 2, 3, 5, 7, 11, 13, … $ Essayer de diviser $ 49 $ par $ 2 $, etc.
Exemple : Au final, les facteurs $ 3, 7, 7 $ sont obtenus et $ 3 * 7 * 7 = 147 $, qui s’écrit aussi $ 147 = 3 * 7 ^ 2 $.
Cette décomposition est possible quel que soit le nombre de départ, c’est un théorème fondamental de l’arithmétique.
Exemple : $ 123 = 3 * 41 $, $ 1234 = 2 * 617 $, $ 12345 = 3 * 5 * 823 $ ou encore $ 123456 = 2 ^ 6 * 3 * 643 $
-
1
Mémoriser les nombres premiers inférieurs à 30
Fiche de Synthèse
Reconnaître un nombre premier
Un nombre premier est un nombre qui possède 2 diviseurs différents: 1 et lui-même.
Voici les nombres premiers inférieurs à 30 classés par ordre croissant: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Prends le temps de mémoriser cette liste, tu en as besoin pour décomposer un nombre entier.
Mémorise les nombres premiers inférieurs à 30. -
2
Trouver le 1er facteur premier
Trace une droite verticale pour obtenir 2 colonnes:
- Dans la colonne de gauche, note le nombre entier à décomposer.
- Dans la colonne de droite, note le plus petit nombre premier qui peut diviser le nombre entier.
Ce plus petit nombre premier est le 1er facteur premier de la décomposition.
« 2 » est le plus petit nombre premier qui peut diviser « 132 ».
Le 1er facteur premier est « 2 ».
Aide-toi des critères de divisibilité pour trouver facilement les diviseurs d’un nombre entier.
Fiche de Synthèse
Utiliser les critères de divisibilité
-
3
Trouver le 2ème facteur premier
Dans la colonne de gauche, note le quotient (le résultat) de la division précédente.
Dans la colonne de droite, note le plus petit nombre premier qui peut diviser le quotient.
Ce plus petit nombre premier est le 2ème facteur premier de la décomposition.
132 : 2 = 66.
« 2 » est le plus petit nombre premier qui peut diviser « 66 ».
Le 2ème facteur premier est « 2 ».
-
4
Trouver tous les autres facteurs premiers
Dans la colonne de gauche, note le quotient de la division précédente.
Dans la colonne de droite, note le plus petit nombre premier qui peut diviser le nouveau quotient.
Pour décomposer un nombre, il suffit de répéter plusieurs fois cette procédure.
Le calcul de la décomposition est terminé lorsque tu obtiens un quotient égal à 1.
66 : 2 = 33.
« 3 » est le plus petit nombre premier qui peut diviser « 33 ».
33 : 3 = 11.
« 11 » est le plus petit nombre premier qui peut diviser « 11 ».
11 : 11 = 1.
Le calcul de la décomposition est terminé car le quotient est 1.
-
5
Écrire la décomposition en produit de facteurs premiers
Tous les nombres dans la colonne de droite sont les facteurs premiers de la décomposition.
Le nombre entier de départ est égal au produit (multiplication) de ces facteurs premiers.
« 132 » est égal au produit de tous les facteurs premiers de la colonne de droite. Tu peux vérifier que la décomposition est correcte en effectuant la multiplication.
Apprenez en vidéo comment décomposer un nombre en produit de facteurs premiers.
Un nombre entier peut être décomposé en un produit de facteurs premiers.
La décomposition en facteurs premiers consiste à écrire un nombre sous la forme d’une multiplication de nombres premiers.
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 32 × 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[1].
5 = 5
25 = 5 × 5 = 52
125 = 5 × 5 × 5 = 53
360 = 2 × 2 × 2 × 3 × 3 × 5 = 23 × 32 × 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. 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[2].
Décomposition en produit de nombres premiers
[
modifier
|
modifier le code
]
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[3], il existe une suite finie unique (p1, k1) … (pr, kr) telle que :
- les
pi
sont des nombres premiers tels que, si
i < j
, alors
pi < pj
;
- les
ki
sont des entiers naturels non nuls ;
-
n
est le produit des nombres
p
ki
i.
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 pk divise n. Cet entier se note vp(n) et s’appelle valuation p-adique de l’entier n.
Ainsi vp(1) = 0 pour tout nombre premier p, v3(45) = 2 et v5(45) = 1.
Si l’on note alors P {displaystyle {mathcal {P}}} 
n = ∏ p ∈ P p v p ( n ) . {displaystyle n=prod _{pin {mathcal {P}}}p^{v_{p}(n)}.}
Les vp(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 ( α p ) p ∈ P {displaystyle (alpha _{p})_{pin {mathcal {P}}}} 
n = ∏ p ∈ P p α p , {displaystyle n=prod _{pin {mathcal {P}}}p^{alpha _{p}},}
alors pour tout p, αp = vp(n). On appelle alors cette écriture la décomposition de n en produit de facteurs premiers.
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
[
modifier
|
modifier le code
]
On suppose par la suite que la décomposition de n en produit de facteurs premiers s’écrit
n = ∏ i = 1 r p i k i . {displaystyle n=prod _{i=1}^{r}p_{i}^{k_{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 pi élevés à une puissance k’i supérieure ou égale à ki.
L’entier d est un diviseur de n si et seulement s’il existe r entiers ki’ vérifiant 0 ≤ k’i ≤ ki tels que d = ∏ i = 1 r p i k i ′ . {displaystyle d=prod _{i=1}^{r}p_{i}^{k’_{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 5 0 , 3 1 5 0 , 3 2 5 0 , 3 0 5 1 , 3 1 5 1 , 3 2 5 1 , {displaystyle 3^{0}5^{0},~3^{1}5^{0},~3^{2}5^{0},~3^{0}5^{1},~3^{1}5^{1},~3^{2}5^{1},} 
Plus généralement, le nombre de diviseurs de l’entier n = ∏ i = 1 r p i k i {displaystyle n=prod _{i=1}^{r}p_{i}^{k_{i}}} 
La somme des diviseurs positifs de n est donnée par la formule σ ( n ) = ∏ i = 1 r p i k i + 1 − 1 p i − 1 . {displaystyle sigma (n)=prod _{i=1}^{r}{frac {p_{i}^{k_{i}+1}-1}{p_{i}-1}}.}
PGCD et PPCM
[
modifier
|
modifier le code
]
Le PGCD (plus grand commun diviseur) 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. Autrement dit, pour tout nombre premier p, vp(pgcd(a,b)) = min(vp(a),vp(b)), où vp est la valuation p-adique. Ainsi, s i a = 2 3 × 3 4 × 5 2 × 7 e t b = 2 2 × 3 5 × 7 3 × 11 a l o r s p g c d ( a , b ) = 2 2 × 3 4 × 7. {displaystyle {rm {si}}quad a=2^{3}times 3^{4}times 5^{2}times 7quad {rm {et}}quad b=2^{2}times 3^{5}times 7^{3}times 11quad {rm {alors}}quad {rm {pgcd}}(a,b)=2^{2}times 3^{4}times 7.}
Le PPCM (plus petit commun multiple) 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. Autrement dit, pour tout nombre premier p, vp(pgcd(a,b)) = max(vp(a),vp(b)), où vp est la valuation p-adique. Ainsi, s i a = 2 3 × 3 4 × 5 2 × 7 e t b = 2 2 × 3 5 × 7 3 × 11 a l o r s p p c m ( a , b ) = 2 3 × 3 5 × 5 2 × 7 3 × 11. {displaystyle {rm {si}}quad a=2^{3}times 3^{4}times 5^{2}times 7quad {rm {et}}quad b=2^{2}times 3^{5}times 7^{3}times 11quad {rm {alors}}quad {rm {ppcm}}(a,b)=2^{3}times 3^{5}times 5^{2}times 7^{3}times 11.}
Décomposition et valuation
[
modifier
|
modifier le code
]
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
,
vp(d) ≤ vp(n)
.
- Produit : la décomposition en facteurs premiers de
ab
consiste à faire les somme de valuations :
a b = ∏ p ∈ P p v p ( a ) + v p ( b ) . {displaystyle ab=prod _{pin {mathcal {P}}}p^{v_{p}(a)+v_{p}(b)}.}
- PGCD :
pgcd ( a , b ) = ∏ p ∈ P p min ( v p ( a ) , v p ( b ) ) . {displaystyle {text{pgcd}}(a,b)=prod _{pin {mathcal {P}}}p^{min(v_{p}(a),v_{p}(b))}.}
- PPCM :
ppcm ( a , b ) = ∏ p ∈ P p max ( v p ( a ) , v p ( b ) ) . {displaystyle {text{ppcm}}(a,b)=prod _{pin {mathcal {P}}}p^{max(v_{p}(a),v_{p}(b))}.}
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 n-ièmes.
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 : 1827 1050 = 3 2 × 7 × 29 2 × 3 × 5 2 × 7 = 3 × 29 2 × 5 2 = 87 50 {displaystyle {frac {1827}{1050}}={frac {3^{2}times 7times 29}{2times 3times 5^{2}times 7}}{=}{frac {3times 29}{2times 5^{2}}}={frac {87}{50}}}
Fractions réduites au même dénominateur
[
modifier
|
modifier le code
]
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 : 5 28 + 3 70 = 5 2 2 × 7 + 3 2 × 5 × 7 = 5 × 5 2 2 × 7 × 5 + 3 × 2 2 × 5 × 7 × 2 = 31 2 2 × 5 × 7 = 31 140 {displaystyle {frac {5}{28}}+{frac {3}{70}}={frac {5}{2^{2}times 7}}+{frac {3}{2times 5times 7}}{=}{frac {5times color {Red}5}{2^{2}times 7times color {Red}{5}}}+{frac {3times color {Red}2}{2times 5times 7times color {Red}2}}{=}{dfrac {31}{2^{2}times 5times 7}}={dfrac {31}{140}}}
Fractions décomposées en élément simples
[
modifier
|
modifier le code
]
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. 5 28 = 5 2 2 × 7 {displaystyle {frac {5}{28}}{=}{frac {5}{2^{2}times 7}}} 
Réduction de racines
[
modifier
|
modifier le code
]
Tout entier supérieur ou égal à 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 : 4752 = 2 4 × 3 3 × 11 = ( 2 2 × 3 ) 2 × 3 × 11 = 12 33 . {displaystyle {sqrt {4752}}={sqrt {2^{4}times 3^{3}times 11}}={sqrt {(2^{2}times 3)^{2}times 3times 11}}=12{sqrt {33}}.}
Cette propriété se généralise à des racines n-ièmes.
Algorithmes de factorisation
[
modifier
|
modifier le code
]
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.
La première idée consiste à 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
208822 divise 2088 le quotient est 1044104422 divise 1044, le quotient est 52252222 divise 522, le quotient est 26126132 ne divise pas 261, mais 3 divise 261 et le quotient est 878733 divise 87 et le quotient est 2929ni 3, ni 5 ne divisent 29 et 72 est plus grand que 29 (fin)
On obtient la décomposition attendue : 2088=23 × 32 × 29.
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 que ces systèmes puissent 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 : savoir casser le générateur en temps polynomial suffit pour savoir factoriser les entiers en temps polynomial, et vice versa.
État actuel de l’art
[
modifier
|
modifier le code
]
Si un grand nombre à n bits 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(nk) quelle que soit la constante k. Il existe des algorithmes, néanmoins, qui sont aussi rapides que Θ(en). En d’autres termes, les meilleurs algorithmes connus sont sous-exponentiels, mais super-polynomiaux. En particulier, le meilleur algorithme connu 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(n3) 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[4].
Difficulté et complexité
[
modifier
|
modifier le code
]
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 admet-il un facteur premier inférieur à M ? » est connu pour être à la fois NP et co-NP. Ceci parce que les réponses OUI et NON peuvent être données en temps polynomial si les facteurs premiers sont donnés : on peut vérifier leur primalité grâce au test de primalité AKS, puis vérifier que leur produit vaut N, et enfin vérifier si l’un des facteurs est inférieur à M.
Le problème de la décomposition est connu comme étant dans BQP à cause de l’algorithme de Shor. Il est suspecté, comme le problème de l’isomorphisme de graphes, d’être strictement entre les classes P et NP-complet (ou co-NP-complet). S’il peut être démontré qu’il est 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, ce problème est largement suspecté d’être également en dehors de P.[réf. nécessaire]
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)[5]. 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 à utiliser avec lui.
Le 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.
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
[
modifier
|
modifier le code
]
Partition d’un entier qui correspond à la décomposition d’un entier additivement, qui, elle, n’est pas unique et dont le nombre de possibilités est objet d’étude.
Outil de décomposition en produit de facteurs premiers en ligne.
Soyez le premier a laisser un commentaire