Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Catégories
Techniques
Sciences
Encore plus...
Techno-Science.net
Partenaires
Organismes
 CEA
 ESA
Sites Web
Photo Mystérieuse

Que représente
cette image ?
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Algorithme de décomposition en produit de facteurs premiers

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 (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers...) fondamental de l'arithmétique (L'arithmétique est une branche des mathématiques qui comprend la partie de la théorie des nombres qui utilise des méthodes de la géométrie algébrique et de la théorie des groupes. On l'appelle plus généralement la « science des...) assure que cette décomposition (En biologie, la décomposition est le processus par lequel des corps organisés, qu'ils soient d'origine animale ou végétale dès l'instant qu'ils sont privés de vie, dégénèrent sous l'action de facteurs...) est unique.

Un simple algorithme de factorisation

Description

Nous pouvons décrire un algorithme récursif pour accomplir de telles factorisations : soit un nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 (Les besoins se situent au niveau de l'interaction entre l'individu et l'environnement. Il est souvent fait un classement des besoins humains en trois...) 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

Voici l'exemple en python :

 
 import math,sys 
 def factorize(n): 
 def isPrime(n): 
 return not [x for x in xrange(2,int(math.sqrt(n))) 
 if n%x == 0] 
 primes = (lien) 
 candidates = xrange(2,n+1) 
 candidate = 2 
 while not primes and candidate in candidates: 
 if n%candidate == 0 and isPrime(candidate): 
 primes.append(candidate) 
 primes = primes + factorize(n/candidate) 
 candidate += 1 
 return primes 
 print factorize(int(sys.argv(lien))) 
 

Sortie :

 
 python factorize.py 9438 
 [2, 3, 11, 11, 13] 
 

Complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri...)

L'algorithme décrit ci-dessus marche (La marche (le pléonasme marche à pied est également souvent utilisé) est un mode de locomotion naturel. Il consiste en un déplacement en appui alternatif sur les jambes, en position debout...) 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 (ou 60 chiffres bits), tous les nombres premiers inférieurs à 1 000 000 000 doivent être testés, ce qui devient long, même pour un ordinateur (Un ordinateur est une machine dotée d'une unité de traitement lui permettant d'exécuter des programmes enregistrés. C'est un ensemble de circuits électroniques permettant de manipuler des données...). En ajoutant deux chiffres décimaux au nombre original, on multiplie le calcul par 10.

La difficulté de la factorisation (complexité en temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) large) en fait une base idéale pour la cryptologie moderne.

Voir aussi : Théorème d'Euler, Décomposition en produit de facteurs premiers, Essais de divisions

Source: Wikipédia publiée sous licence CC-BY-SA 3.0.

Vous pouvez soumettre une modification à cette définition sur cette page. La liste des auteurs de cet article est disponible ici.