Discussion :

[yoshik]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Sélectionner tout - Visualiser dans une fenêtre à part

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 !
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,

@+

[fred1599]

Le PGCD n'a pas besoin d'être recréé. Pour cela utilise le module fractions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
import fractions as f
f.gcd(12785, 15) # Calcul le pgcd de 12785 et 15
5

[yoshik]

Salut,

Merci, je ne savais pas que le pgcd était implanté...
Je l'ai essayé :
j'abaisse mon temps de 1.54699993134 s à 1.32899999619 s dans le 2e code, c'est significatif et de 0.733999967575 s à 0,625 s dans le 1er code.
Significatif aussi...

Cela dit, 0,625 x 2 = 1,33, je suis toujours 2 fois plus lent...

Qu'est-ce qui fait que le 2e code est si lent par rapport au 1er ?

Encore, merci, belle réactivité !

@+

[eyquem]

Il suffit d'ajouter un print i après la boucle while pour constater que
ta première methode tourne avec 30940 tours de boucle,
tandis que la seconde tourne avec 66916 tours.

De plus le premier code donne le résultat 7660450463 * 1308520867
tandis que le second donne le résultat 1308520867 * 7660450463







Voici les codes que j'ai utilisés pour comprendre un peu la façon dont évoluent les variables,
avec choix au lancement d'occulter l'affichage ou non.
Si ça peut servir.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
45
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from math import sqrt,log
from time import clock
 
def pgcd(a,b):
    while b>0:
        a,b=b,a%b      
    return a
 
print 'methode 111111111111111111111'
arr = raw_input('Entrer   rien pour afficher   quch pour ne pas afficher   ')
 
te = clock()
n=10023859281455311421
racine=sqrt(n)
x,c,a,xk=1,1,1,1
k1=1
liste_x=[1]
i=0
if not arr:
    print '\nx de depart =',x
    somt = ''
 
while a==1 and i<racine:
    i+=1
    if i%25==0 and not arr:
        print somt
        somt = ''
        raw_input('stop')
    k = 2**int(log(i)/log(2))-1
    x=(x**2+c)%n
    if not arr:
        somt += '\n\nxk ='+str(xk)+'   i = '+str(i)+'   k ='+str(k)+'\nx  ='+str(x)
    liste_x.append(x)
    if k-k1!=0:
        xk=liste_x[k]
        k1=k
    a=pgcd(n,abs(x-xk))
 
print "\nLe nombre",n,"se factorise ainsi :"
print a,"*",n/a
print "\nTemps de travail :", clock()-te
print '\nNombre de tours de la boucle : ',i

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
34
35
36
37
38
39
40
41
42
43
44
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from math import sqrt,log
from time import clock
 
def pgcd(a,b):
    while b>0:
        a,b=b,a%b      
    return a
 
print 'methode 2222222222222222222222222222222222222222222'
arr = raw_input('Entrer   rien pour afficher   quch pour ne pas afficher   ')
 
te = clock()
n=10023859281455311421
racine=sqrt(n)
x,a,xk,c=2,1,1,3
 
 
i=1
if not arr:
    print '\nx de depart =',x
    somt = ''
 
while a==1 and i<racine:
    i+=1
    if i%25==0 and not arr:
        print somt
        somt = ''
        raw_input('stop')
    k = 2**int(log(i)/log(2))
    x=(x**2+c)%n
    if not arr:
        somt += '\n\nxk ='+str(xk)+'   i = '+str(i)+'   k ='+str(k)+'\nx  ='+str(x)
    a=pgcd(abs(x-xk),n)
    if k==i:
        xk=x
 
 
print "\nLe nombre",n,"se factorise ainsi :"
print a,"*",n/a
print "\nTemps de travail :", clock()-te
print '\nNombre de tours de la boucle : ',i

x,c,a,xk=1,1,1,1
peut s'écrire
x = c = a = xk = 1
il n'y a pas de phénomène d'aliasing parce que ce sont des variables non mutables.

Mais attention, ne pas faire ça avec des variables mutables.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
a = b = c = d = [12,34]
 
a.append(199)
c.append(2000)
 
print a,b,c,d

donne

[12, 34, 199, 2000] [12, 34, 199, 2000] [12, 34, 199, 2000] [12, 34, 199, 2000]

[tyrtamos]

Bonjour,

Je me suis fait grillé par eyquem (bonjour eyquem!) pour la réponse, mais j'ai les mêmes résultats.

=> Avec le n donné, le rapport du nombre de boucle des 2 algorithmes est très proche du rapport des temps de calcul (env. 2.15).

Donc, les différences de temps sont plus dûs aux choix des algorithmes qu'aux choix de programmation.

Cela veut dire aussi que la tentative de ne pas utiliser de liste ne fait rien gagner si, pour cela, on doit utiliser un algorithme moins efficace.

(et c'était un problème intéressant, merci!)

Tyrtamos

[rambc]

J'ai essayé le petit changement suivant dans le tout premier code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from math import sqrt,log
from time import time
from fractions import gcd
 
tp_d=time()
n=10023859281455311421
racine= sqrt(n)
x,c,a,xk,yk=1,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
    if k-k1 <> 0:
        xk=yk
        k1=k
    else:
        yk = x
    a=gcd(n,abs(x-xk))
 
print "Le nombre",n,"se factorise ainsi :"
print a,"*",n/a
print
print "Temps de travail :", time()-tp_d

En faisant tourner le tout premier prog., ou en le lisant, on voit que l'emploi des listes est inutile car il y a un empilement de valeurs identiques. Comme k va en croissant, il suffit de passer par une autre variable intermédiaire, j'ai choisi par flemme yk.

PS : pour quelle raison fais-tu ce code ? Juste pour essayer...

[yoshik]

Salut,

Merci à tous, c'est un vrai plaisir de questionner ici, comme d'hab...
Oui, cet empilement, j'avais vu, ma liste contenait plus de 37000 nombres qui revenaient périodiquement... C'est pour ça que je m'étais dit que le coup de la liste, c'était vraiment pas subtil. D'où ma surprise !
Allez voilà le tout premier code bête et méchant niveau calcul pourtant très rapide :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from time import time
import fractions as f
 
tp_d=time()
n=10023859281455311421
x,y,a,c=1,1,1,1
 
# Si la factorisation me marche pas
# Et si vous avez la certitude que votre nombre n'est pas premier
# Changez la valeur de c : essayez avec 3,5,7...
 
while a==1:
    x=(x**2+c)%n           # x = f(x)              (mod n)
    y=((y**2+c)**2+1)%n    # y = (f o f)(y)  (mod n)
    a=f.gcd(n,abs(x-y))
 
temps = time()-tp_d
print "Le nombre",n,"se factorise ainsi :"
print "          ",a,"*",n/a
print 
print "Temps de travail :", temps,"s"

0,375 s avec le def pgcd(a,b) et 0,344 s avec le pgcd natif de Python...

Quant au pourquoi c'est simple, j'ai vu que quelqu'un cherchait à obtenir un script de l'algorithme de rho pollard pour factoriser les nombres, mais en C++ de préférence...
Moi C++, je ne connais pas, alors je me suis dit :
1. C'est quoi ce truc ? Jamais entendu parler ! J'ai cherché à savoir pour comprendre et j'ai trouvé
2. Programmons en Python, c'est un beau défi...
Et voilà !
La cryptographie est décidément est un domaine plein de surprise et qui est devenu hautement mathématisé...

Merci encore.
Je vais expérimenter tout ça demain. Mais je pense que mieux que 0,34 s avec cet algo particulier, ça va être "Mission Impossible"...

@+

PS Tiens au fait, ces recherches ont eu un effet collatéral : j'ai découvert qu'il était impossible de contrôler une boucle for avec un entier long...
Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
>>> from math import sqrt
>>> racine =int(sqrt(10023859281455311421))+1
>>> for i in xrange(racine):
	pass
 
 
Traceback (most recent call last):
  File "<pyshell#4>", line 1, in <module>
    for i in xrange(racine):
OverflowError: long int too large to convert to int
>>>

J'ai donc cherché dans la doc : rien vu ! Mal regardé ?