Décomposition en produit de facteurs premiers

En mathématiques et plus exactement en arithmétique modulaire, la décomposition en produit de facteurs premiers est le problème suivant : soit un entier strictement positif, comment l'écrire sous forme d'un produit de nombres premiers.



Catégories :

Divisibilité et factorisation - Arithmétique élémentaire - Mathématiques élémentaires - Algorithme de factorisation des entiers

Recherche sur Google Images :


Source image : neamar.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Algorithme de factorisation en nombre premier, Algorithme de décomposition en produit de facteurs premiers Un algorithme de décomposition en produit de ... (source : encyclopedie-enligne)
  • Ici, les nombres non premiers sont écrits en rouge. Les nombres premiers.... Si N est un entier dont la décomposition en produit de facteurs premiers est :.... on aboutit à : «n divise le dernier reste non nul de l'algorithme... (source : reymarlioz.free)
  • La preuve de l'algorithme d'Euclide ne me paraît pas raisonnable en collège... de b (NB : la décomposition en produit de facteurs premiers est au... fait que le pgcd de deux nombres est le meilleur "simplificateur" des ... (source : mathsdiscut.sesamath)

En mathématiques et plus exactement 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, comment l'écrire sous forme d'un produit de nombres premiers. A titre d'exemple, si le nombre donné est 45, la factorisation en nombres premiers est 32·5.

Par définition, un nombre premier ne peut pas être décomposé. On peut aussi dire qu'il est sa propre décomposition.

11 = 11
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 essentiel de l'arithmétique. Ce problème est d'une importance énorme en mathématiques, en cryptologie, en théorie de la complexité, et pour les calculateurs quantiques.

Décomposition en nombres premiers

Tout nombre naturel n non nul peut s'écrire de manière unique comme le produit fini de nombres premiers à une puissance correcte.

\forall n\in\mathbb{N}ˆ*, \exists! (\alpha_p)_{p\in\mathcal{P}}\in\mathbb{N}ˆ{(\mathcal{P})}: n = \prod_{p\in\mathcal{P}} pˆ{\alpha_p}.

La liste complète des facteurs peut être déduite de la factorisation en nombres premiers en incrémentant les exposants de zéro jusqu'au nombre cherché. A titre d'exemple, comme 45 = 32·5, 45 est divisible par 30·50, 30·51, 31·50, 31·51, 32·50, et 32·51, ou 1, 5, 3, 15, 9, et 45. Par contraste, la factorisation en nombres premiers inclut uniquement les facteurs premiers. Voir l'algorithme de décomposition en produit de facteurs premiers.

Applications pratiques

Soient deux grands nombres premiers donnés, il est facile d'en obtenir le produit. Par contre, il est bien plus complexe de trouver les facteurs premiers de ce dernier. C'est ce qu'on nomme une fonction trappe. Ceci s'applique pour les dispositifs 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 dispositifs 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 dispositifs, il peut exister d'autres manières de les casser qui n'impliquent pas la factorisation. Ainsi, il est envisageable que le problème de la factorisation entière soit vraiment complexe, ces dispositifs 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 précisément aussi complexe 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 inversement.

État actuel de l'art

Si un grand nombre à n-bit est le produit de deux nombres premiers qui sont certainement de la même taille, alors aucun algorithme n'est aujourd'hui réputé 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-polynômiaux. Surtout, 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 réputé pour les grands n. Pour un calculateur quantique, par contre, 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 uniquement O (n3) de temps et O (n) d'espace. Les formes de l'algorithme sont connues pour utiliser uniquement 2n qubits. En 2001, le premier calculateur quantique 7-qubit devint le premier à exécuter l'algorithme de Shor. Il factorisa le nombre 15 (!).

Article détaillé : calculateur quantique.

Difficulté et complexité

On ne connaît pas précisément 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 réputé 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 particulièrement étonnant, donc la factorisation entière est beaucoup suspectée d'être en dehors de ces classes. Énormément de personnes ont essayé de trouver des algorithmes en temps polynomial pour cela et ont échoué; donc, elle est beaucoup 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 exactement, 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. Qui plus est , il existe un nombre d'algorithmes probabilistes qui peuvent tester la primalité d'un nombre particulièrement 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 principale de l'algorithme RSA, comme il est indispensable de trouver de grands nombres premiers pour démarrer avec lui.

Algorithmes de factorisation

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 fluctue entre les algorithmes.

But général

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

Liens externes

Recherche sur Amazone (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/D%C3%A9composition_en_produit_de_facteurs_premiers.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 10/03/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu