Factorisation des nombres : optimisation du temps de calcul
Bonjour à tous,
Les spécialistes de l'optimisation vont avoir de quoi faire tourner leurs neurones.
A partir de la page suivante, méthode de rho Pollard, variante Richard Brent :
http://www-lipn.univ-paris13.fr/~ban...cto/facto.html
J'ai créé ce premier code :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| # usr/bin/env python
# -*- coding: utf-8 -*-
from math import sqrt,log
from time import time
def pgcd(a,b):
while b>0:
a,b=b,a%b
return a
tp_d=time()
n=10023859281455311421
racine= sqrt(n)
x,c,a,xk=1,1,1,1
k1=1
liste_x=[1]
i=0
while a==1 and i < racine:
i+=1
k = 2**int(log(i)/log(2))-1
x=(x**2+c)%n
liste_x.append(x)
if k-k1!=0:
xk=liste_x[k]
k1=k
a=pgcd(n,abs(x-xk))
print "Le nombre",n,"se factorise ainsi :"
print a,"*",n/a
print
print "Temps de travail :", time()-tp_d |
Temps : 0.733999967575 s
En fait j'ai déjà écrit un premier code sur cette base http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm qui était deux fois plus rapide... :cry:
Je me suis donc dit : c'est normal, tu stockes tous les nombres dans une liste, et tu accèdes de très nombreuses fois à ladite liste, il faut trouver un moyen de se passer de la liste !
Donc, j'ai cogité et pondu ça :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| # usr/bin/env python
# -*- coding: utf-8 -*-
from math import sqrt,log
from time import time
def pgcd(a,b):
while b>0:
a,b=b,a%b
return a
tp_d=time()
x,a,xk,c=2,1,1,3
n=10023859281455311421
racine=sqrt(n)
i=1
while a==1 and i<racine:
i+=1
k=2**int(log(i)/log(2))
x=(x**2+c)%n
a=pgcd(abs(x-xk),n)
if k==i:
xk=x
print "Le nombre",n,"se factorise ainsi :"
print a,"*",n/a
print
print "Temps de travail :", time()-tp_d |
Et bien : 1.54699993134 s... Encore deux fois plus lent ! 8O
Là, je perds mon latin...
Il y a les mêmes calculs, pas de liste dans le 2nd code, un test pratiquement identique. D'où vient cette perte de temps ?
Merci d'avance,
@+
