Facteurs premiers

ÔĽŅ
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 suivant : soit un entier strictement positif, comment l'√©crire sous forme d'un produit de nombres premiers. Par 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 fondamental de l'arithmétique. Ce problème est d'une importance considérable en mathématiques, en cryptologie, en théorie de la complexité, et pour les calculateurs quantiques.

Sommaire

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 adéquate.

\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é. Par 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 seulement 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 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, 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(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. 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, 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 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 (!).

Article d√©taill√© : calculateur quantique.

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 monde 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.

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 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.

Liens externes

  • Portail des math√©matiques Portail des math√©matiques
Ce document provient de ¬ę D%C3%A9composition en produit de facteurs premiers ¬Ľ.

Wikimedia Foundation. 2010.

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

Regardez d'autres dictionnaires:

  • 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… ‚Ķ   Wikip√©dia en Fran√ßais

  • 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 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

  • 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 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√©composer un entier en facteurs premiers ‚ÄĒ ‚óŹ D√©composer un entier en facteurs premiers l √©crire sous forme de produit o√Ļ tous les facteurs sont des nombres premiers. (Cette d√©composition est unique √† l ordre pr√®s des facteurs.) ‚Ķ   Encyclop√©die Universelle

  • Facteurs D'√©mergence De La Grippe Aviaire ‚ÄĒ Cet article est un des sous chapitres de Grippe aviaire. Il traite des facteurs favorisant ou conditionnant l √©mergence d une situation pand√©mique, √† partir d un virus dit animal de la grippe aviaire. On distingue ici 7 facteurs principaux  ‚Ķ   Wikip√©dia en Fran√ßais

  • Premiers ministres des provinces et territoires du canada ‚ÄĒ Canada Cet article fait partie de la s√©rie sur la politique du Canada, sous s√©rie sur la politique. Po ‚Ķ   Wikip√©dia en Fran√ßais


Share the article and excerpts

Direct link
… Do a right-click on the link above
and select ‚ÄúCopy Link‚ÄĚ

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.