Algorithme de décomposition 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 entier est « décomposé » en un produit de facteurs qui sont des nombres premiers. Le théorème fondamental de l'arithmétique assure que cette décomposition est unique.

Sommaire

Description

Nous pouvons décrire un algorithme récursif pour accomplir de telles factorisations : soit un nombre donné n

  • si n est premier, alors la factorisation s'arrête ici.
  • si n est composé, diviser n par le premier nombre premier p1. S'il est divisé sans reste, reprendre avec la valeur n/p1. Ajouter p1 à la liste des facteurs obtenus pour n/p1 pour avoir une factorisation pour n. S'il est divisé avec reste, diviser n par le nombre premier suivant p2, et ainsi de suite.

Notez que nous avons besoin de tester seulement les nombres premiers pi tels que pi ≤ √n.

Exemple

Supposons que nous désirons factoriser 9 438.

9 438/2 = 4 719, sans reste donc 2 est un facteur.

Nous répétons l'algorithme avec 4 719.

4 719/2 = 2 359.5, donc 2 n'est pas un facteur. 4 719/3 = 1 573, donc 3 est un facteur.

Le premier nombre premier par lequel 1 573 est divisible est 11.

1 573/11 = 143. De manière similaire, le nombre premier suivant qui divise 143 est 11. 143/11 = 13. 13 est lui-même premier.

Donc, en récapitulant, nous avons 9 438 = 2×3×11×11×13 = 2×3×112×13

Complexité

L'algorithme décrit ci-dessus marche bien pour les petits n, mais devient impraticable dès que n devient plus grand. Par exemple, pour un nombre de 18 chiffres décimaux, tous les nombres premiers inférieurs à 1 000 000 000 doivent être testés, ce qui prend du temps, même pour un ordinateur. À chaque fois que l'on ajoute deux chiffres au nombre à factoriser, on multiplie le temps de calcul par 10.

La difficulté de la factorisation (grande complexité en temps) en fait une base idéale pour la cryptologie moderne.

Voir aussi

Articles connexes

Lien externe



Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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

  • 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

  • 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

  • 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

  • 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

  • Algorithme de factorisation de nombre premier — 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

  • Algorithme de factorisation en nombre premier — 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

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”