Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente Dernière révision Les deux révisions suivantes | ||
decomposition_en_facteurs_premiers [2008/07/02 17:25] tyrtamos |
decomposition_en_facteurs_premiers [2009/01/09 12:45] tyrtamos |
||
---|---|---|---|
Ligne 9: | Ligne 9: | ||
Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier! | Bien entendu, un nombre premier ne trouve que lui-même comme facteur premier! | ||
- | Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l' | + | Le principe du calcul est assez trivial, et consiste à faire des divisions entières systématiques avec divmod(). Cette fonction renvoie une liste de 2 valeurs: le résultat de la division entière et son reste. Si le reste est nul, c'est que la division est exacte, et on a trouvé un facteur de plus. On l' |
On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs " | On utilise en plus une astuce pour gagner du temps: on commence par trouver tous les facteurs " | ||
- | Les tentatives de division s' | + | Les tentatives de division s' |
Voici le code: | Voici le code: | ||
Ligne 23: | Ligne 23: | ||
def facteurs(n): | def facteurs(n): | ||
""" | """ | ||
- | | + | |
if n==1: | if n==1: | ||
- | return | + | return |
# recherche de tous les facteurs 2 s'il y en a | # recherche de tous les facteurs 2 s'il y en a | ||
while n>=2: | while n>=2: | ||
- | x=divmod(n, | + | x,r = divmod(n, |
- | if x[1]==0: | + | if r!=0: |
- | f.append(2) | + | |
- | n=x[0] | + | |
- | else: | + | |
break | break | ||
+ | F.append(2) | ||
+ | n = x | ||
# recherche des facteurs 1er >2 | # recherche des facteurs 1er >2 | ||
i=3 | i=3 | ||
- | | + | |
- | if i*i>n: | + | while i<=n: |
- | | + | if i>rn: |
+ | | ||
break | break | ||
- | x=divmod(n, | + | x,r = divmod(n, |
- | if x[1]==0: | + | if r==0: |
- | | + | |
- | n=x[0] | + | n=x |
+ | rn = lsqrt(n)+1 | ||
else: | else: | ||
- | i+=2 | + | i += 2 |
- | return | + | return |
# exemple d' | # exemple d' | ||
Ligne 60: | Ligne 61: | ||
Bien que passant par un calcul systématique " | Bien que passant par un calcul systématique " | ||
- | facteurs(12345678901234567890) | + | <code python> |
+ | print facteurs(12345678901234567890) | ||
+ | [2, 3, 3, 5, 101, 3541, 3607, 3803, 27961] | ||
+ | </ | ||
+ | |||
+ | Résultat trouvé | ||
+ | |||
+ | La rapidité du calcul dépend de la quantité des facteurs et de leur taille. Le temps le plus long étant obtenu, pour une taille donnée, | ||
+ | |||
+ | <code python> | ||
+ | print facteurs(6082717798076598743) | ||
+ | [1536921011, | ||
+ | </ | ||
+ | |||
+ | Ce qui prend environ 15 mn de calcul. | ||
+ | |||
+ | Par contre, pour traiter des nombres de plusieurs centaines de chiffres comme on en trouve en cryptographie, | ||
\\ | \\ | ||
Ligne 85: | Ligne 102: | ||
\\ | \\ | ||
Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: [[http:// | Vous pouvez tester la fonction facteurs(n) avec la Calculext ici: [[http:// | ||
+ | |||
+ | \\ | ||
+ | Amusez-vous bien! | ||
+ | |||
< | < | ||
< | < |