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é ?

[tyrtamos]

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

Et oui . Extrait de la note concernant xrange:

Note
xrange() is intended to be simple and fast. Implementations may impose restrictions to achieve this. The C implementation of Python restricts all arguments to native C longs (“short” Python integers), and also requires that the number of elements fit in a native C long. If a larger range is needed, an alternate version can be crafted using the itertools module: islice(count(start, step), (stop-start+step-1)//step).

Résumé: pour que ce soit rapide, c'est programmé en C qui ne connait pas les entiers long de Python.

Solutions alternatives:

- utiliser un while, mais ça complique un peu le code. Exemple:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
i = 0
imax = 10
ipas = 2
while i<imax:
    print i
    i += ipas
 
0
2
4
6
8

- utiliser une fonction avec yield. Exemple:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
def xplage(i, imax, ipas=1):
    while i<imax:
        yield i
        i += ipas
 
for i in xplage(0, 10, 2):
    print i
0
2
4
6
8

- utiliser une classe itérable. Exemple:

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
 
class xplage(object):
 
    def __init__(self, ideb, imax, ipas=1):
        self.i = ideb-ipas
        self.imax = imax
        self.ipas = ipas
 
    def __iter__(self):
        return self
 
    def next(self):
        self.i += self.ipas
        if self.i >= self.imax:
            raise StopIteration
        return self.i
 
for i in xplage(0, 10, 2):
    print i
0
2
4
6
8

- ou utiliser le module itertools comme recommandé dans la note du manuel. Je ne l'ai jamais utilisé. Cependant, il ne faudrait pas que cela oblige à construire une liste de valeur, car justement l'avantage de xrange(), c'est que les valeurs renvoyées ne viennent pas d'une liste comme range().

Toutes les solutions programmées en Python ont l'air d'être rapides, mais probablement moins que le xrange programmé en C.

Tyrtamos

[eyquem]

Avec le code suivant

Code :

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

1
2
3
4
5
6
7
8
9
from math import sqrt,log
 
k1 = 1
maxrange  = 400
for i in xrange(1,maxrange):
    k = 2**int(log(i)/log(2))-1
    if k!=k1:
        print 'i = '+str(i)+'  k = '+str(k)
        k1 = k

maxrange = 400
i = 1 k = 0
i = 2 k = 1
i = 4 k = 3
i = 8 k = 7
i = 16 k = 15
i = 32 k = 31
i = 64 k = 63
i = 128 k = 127
i = 256 k = 255

on voit que chaque fois que k devient différent de k1, la valeur de k est i-1.

Donc l’instruction xk=liste_x[k] exécutée quand k devient différent de k1 est équivalente à xk=liste_x[i-1].

Or liste_x a été initialisée à [1], puis par la suite remplie avec tous les x successifs:
donc le premier x correspondant à i=1 a eté mis en position 1, le second correspondant à i=2 a eté mis en position 2, et tout x calculé pour une valeur i de l’indice d’itération est à la position i dans liste_x.

Donc liste_x[i-1] est la valeur de x qui a été enregistrée dans liste_x au tour précédent, c’est à dire pour la valeur i-1 de l’indice d’itération.

L’instruction xk = liste_x[k] affecte donc à xk la valeur du x au tour précédent quand k devient != k1.



Pour se passer de liste_x , il suffit donc d’affecter à xk la valeur de x avant de calculer la nouvelle valeur de x correspondant à i, en déplaçant l’instruction xk = liste_x[k] entre
k = 2**int(log(i)/log(2))-1
et
x=(x**2+c)%n

Ce qui donne:

Code :

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

1
2
3
4
5
6
7
8
9
10
while a==1 and i < racine:
    i+=1
    k = 2**int(log(i)/log(2))-1
    if k-k1!=0:
        #xk=liste_x[k]  remplacee par:
        xk = x
        k1=k
    x=(x**2+c)%n
    # liste_x.append(x)  devenue inutile
    a=pgcd(n,abs(x-xk))

Ensuite, en revenant sur le premier code en haut, on voit bien sur un plus grand nombre de résultats que k change pour tous les i qui sont des multiples de 2:

maxrange = 3000000
i = 1 k = 0
i = 2 k = 1
i = 4 k = 3
i = 8 k = 7
i = 16 k = 15
i = 32 k = 31
i = 64 k = 63
i = 128 k = 127
i = 256 k = 255
i = 512 k = 511
i = 1024 k = 1023
i = 2048 k = 2047
i = 4096 k = 4095
i = 8192 k = 8191
i = 16384 k = 16383
i = 32768 k = 32767
i = 65536 k = 65535
i = 131072 k = 131071
i = 262144 k = 262143
i = 524288 k = 524287
i = 1048576 k = 1048575
i = 2097152 k = 2097151

On peut donc réécrire le code en tenant compte du fait que xk reste constante sur des plages de valeurs range(2,4), range(4,8), range(8,16), range(16,32) etc, en prenant des valeurs différentes sur les différentes plages.

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
# 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
 
n=10023859281455311421
racine=sqrt(n)
 
x,c,a,xk=2,1,1,2
k1=0
racine = sqrt(n)
 
dedeux = 2
te = clock()
while a==1:
    xk = x
    dedeux *= 2
    for i in xrange(dedeux,min(dedeux*2,racine)):
        x=(x**2+c)%n
        a=pgcd(n,abs(x-xk))
        if a!=1:
            break
tf = clock()
 
print "\nLe nombre",n,"se factorise ainsi :"
print a,"*",n/a
print "Temps de travail :", tf-te
print 'Nombre de tours de la boucle : ',i

Ce code est plus rapide: - 11 % par rapport à ton premier code. C’est une toute petite baisse. L’algorithme est vraiment médiocre.

Avec ton deuxième algo avec x et y, le temps est divisé par deux, même par rapport au premier code “optimisé“. Je ne vois en effet pas comment on peut battre cet algo dont les variables x et y sautent de valeur en valeur sans qu’il y ait d’itération i+=1.

[eyquem]

Par rapport au tout premier code,


- mon précédent code optimisé faisait - 11 % de temps d’exécution


- avec le code suivant

Code :

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

1
2
3
4
5
6
7
8
while a==1:
    xk = x
    dedeux = dedeux *2
    for i in xrange(dedeux,min(dedeux*2,racine)):
        x = (x*x + c)%n
        a=pgcd(n,abs(x-xk))
        if a!=1:
            break

j’ai obtenu -18 % pour le temps d’exécution le plus bas sur une série d’essais


- avec en plus, gcd() du module fraction à la place de la fonction pgcd()
j’ai obtenu - 35 % de temps









Reprenant alors ton code du message #7 ,
j’ai modifié en

Code :

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

1
2
3
4
5
while a==1:
    x = (x*x+c)%n           # x = f(x)              (mod n)
    y = y*y+c
    y = (y*y+1)%n    # y = (f o f)(y)  (mod n)
    a = f.gcd(n,abs(x-y))

et ça donne -19 % sur le temps d’exécution,
soit -65 % par rapport au premier code du message #1, et plus seulement -50 %.

[yoshik]

Salut,

Tiens, tiens...
Le code précédent tendrait à prouver qu'il est plus rapide de faire x*x que x**2 !
Là, je suis franchement surpris...
Par rapport à mon code message #7, remplacer les puissances de 2 de x et y par x*x et y*y et calculer le y en 2 fois comme tu le suggères, tyrtamos, me fait gagner 14% c'est énorme !
D'où cela peut-il venir ?

D'autre part, je me suis demandé pourquoi l'algo du code n°2 du message #1, dans lequel j'ai remplacé le def pgcd() par l'importation du gcd natif, et le x**2 par x*x était quand même si lent par rapport celui-ci modifié...
Bon, il y a le calcul du 2**int(log(i)/log(2)) et le test if... Mais ça ne pouvait pas tout expliquer.
Donc dans le code ultra-rapide que tu as retouché, j'ai introduit un compteur d'itérations : j'ai 4/100 s sur 0,28 s... Ce n'est pas suffisant.
Donc j'ai comparé le nombre d'itérations pour arriver au résultat : 14557 contre 30941... Et le 1er nombre affiché est bien le même...
Donc, je crois qu'on peut tirer le rideau, le 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
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from time import time
from fractions import gcd
 
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...
i=0
while a==1:
    x=(x**2+c)%n           # x = f(x)              (mod n)
    y=((y**2+c)**2+c)%n    # y = (f o f)(y)  (mod n)
    a=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"

est intrinsèquement le plus rapide de 54%.
Y a pas photo, ça vient de l'algorithme choisi, la variante mise au point par le mathématicien Richard Brent est mauvaise au point de vue temps quand même le commentaire de cette méthode est :

On choisit à chaque fois k=2^{plancher(\ln(i)/\ln(2))}-1, c'est lié à la méthode de détection de période de Brent.

J'ai beaucoup aimé le "plancher", d'ailleurs.

Bon, je classe en Résolu.

Merci encore

@+

[rambc]

Y a pas photo, ça vient de l'algorithme choisi, la variante mise au point par le mathématicien Richard Brent est mauvaise au point de vue temps...

Si cela peut te rassurer, il y a plain d'algorithmes de factorisation et heureusement que cette dernière est dure à faire, sans quoi le RSA serait menacé. Si le sujet t'intéresse, il va falloir mettre un peu le nez dans des livres de maths.
A l'heure actuelle, d'un point de vue théorique, seuls les ordinateurs quantiques pourraient permettre une factorisation rapide.

[tyrtamos]

A l'heure actuelle, d'un point de vue théorique, seuls les ordinateurs quantiques pourraient permettre une factorisation rapide.

Par curiosité, j'ai tenté d'utiliser sur un ordinateur "normal" (=non-quantique) la méthode de shor, dont on dit qu'elle serait une "rsa-killer": manifestement, il faut la technologie quantique, parce que là, c'est très lent. Cependant ça marche, et on devrait pouvoir l'améliorer au moins avec une fft ainsi qu'avec d'autres astuces de calcul (ce n'est pas très optimisé pour l'instant...):

http://python.jpvweb.com/mesrecettes...orisation_shor.

Tyrtamos

[yoshik]

Salut

Si le sujet t'intéresse, il va falloir mettre un peu le nez dans des livres de maths.

Même pas peur !
Je suis prof de maths retraité...

@+

[fred1599]

Mais on a oublié le meilleur : le module psyco

Il permet l'accélération de certaines séquences de 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
# usr/bin/env python
# -*- coding: utf-8 -*-
 
from time import time
from fractions import gcd
import psyco
psyco.full()
 
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...
i=0
while a==1:
    x=(x**2+c)%n           # x = f(x)              (mod n)
    y=((y**2+c)**2+c)%n    # y = (f o f)(y)  (mod n)
    a=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"

On passe de 0.690901994705 s à 0.520672082901 s soit encore un gain de 10% à 20%

[rambc]

Ce module psyco, c'est de la folie... Cela me tue...

Même pas peur !

Dans ce cas, il y un très bon livre sur le calcul formel en général : Modern Computer Algebra de Gathen et Gerhard. Il y a une partie sur la factorisation mais ce n'est pas le sujet principal du livre.

Il faut regarder du côté des algorithmes probabilistes pour les méthodes relativement efficaces et "simples". Il y a aussi l'utilisation des courbes elliptiques : http://www.bibmath.net/crypto/comple...lliptique.php3 .

[tyrtamos]

Bonjour,

Je suis impressionné par la compacité et l'efficacité du dernier algorithme donné (message de fred1599), mais... il ne trouve pas toutes les décompositions, avec ou sans psyco.

Par exemple:

n = 372469; renvoie (372469 et 1) alors que c'est 173*2153
n = 477667; renvoie (477667 et 1) alors que c'est 631*757
n = 166483; renvoie (166483 et 1) alors que c'est 229*727

Je voulais utiliser cela pour calculer l'ensemble des facteurs premier d'un nombre quelconque (calcul récursif), mais pour cela, il faut pouvoir tester si n est premier, ce qui serait facile si le résultat de la décomposition de n premier était (n,1) ou (1,n) et seulement dans ce cas.

Quelqu'un a-t-il une idée?

(je sais tester si le nb est premier avec Miller-Rabin, mais je cherche plus simple)

Tyrtamos

[rambc]

Je suis impressionné par la compacité et l'efficacité du dernier algorithme donné (message de fred1599), mais... il ne trouve pas toutes les décompositions, avec ou sans psyco.

Par exemple:

n = 372469; renvoie (372469 et 1) alors que c'est 173*2153
n = 477667; renvoie (477667 et 1) alors que c'est 631*757
n = 166483; renvoie (166483 et 1) alors que c'est 229*727

Bien vu pour ces contre-exemples qui montrent la non validité de l'algorithme d'un point de vue déterministe. Peut-être que l'algorithme proposé est probabiliste...

je sais tester si le nb est premier avec Miller-Rabin, mais je cherche plus simple

Factoriser pour un test de primalité c'est pas le plus efficace. Il est plus "facile" de tester la primalité directement. Il existe un algorithme récent efficace et déterministe : [ame="http://fr.wikipedia.org/wiki/Test_de_primalité_AKS"]Test de primalité AKS[/ame]. Pour la théorie, voir ce document. Une piste pour l'implémentation : [ame="http://en.wikipedia.org/wiki/AKS_primality_test"]les grandes étapes[/ame].

PS : si tu as besoin d'aide, je peux participer en fonction de mes disponibilités.

PS Bis : dans quel cadre vas-tu faire des tests de primalité ?

[yoshik]

RE,

J'aurais bien voulu essayer...
J'ai téléchargé psyco ici : http://sourceforge.net/projects/psyco/files/
J'ai pris le dernier, je l'ai installé sans problème et au lancement de mon scrip, paf :

Code :

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

1
2
3
4
5
6
Traceback (most recent call last):
  File "C:\Python26\rho_pollard1.py", line 6, in <module>
    import psyco
  File "C:\Python26\lib\site-packages\psyco\__init__.py", line 46, in <module>
    raise ImportError, str(e) + extramsg
ImportError: DLL load failed: Le module spécifié est introuvable. (check that the compiled extension 'C:\Python26\lib\site-packages\psyco\_psyco.pyd' is for the correct Python version; this is Python 2.6)

Après vérification, pyco n'est pas là :
"C:\Python26\lib\site-packages\psyco\

mais ici :
"C:\Python26\libs\site-packages\psyco\__init__.py"

Comment faire pour vérifier le chemin ? Je pense que ce s manquant peut être la cause de l'erreur ? Doit bien y avoir un python path ou qq ch comme ça dans Windows...

@+

PS

Je suis impressionné par la compacité et l'efficacité du dernier algorithme donné (message de fred1599), mais... il ne trouve pas toutes les décompositions, avec ou sans psyco.

Ca tient à la valeur de c... là on part avec c = 1, pour 222119, j'ai essayé c=1 et c=3 sans succès, mais ça fonctionne avec c=5... C'est spécifié dans les commentaires du code cf message #7

Pour certains f, l'algorithme ne trouvera pas de facteur. Si pgcd(|xa − xb|, n) = n, l'algorithme échouera, parce que xa = xb, ce qui veut dire que la suite était bouclée et cela continuera tant que le travail précédent se répètera. En changeant c ou f, on peut augmenter la chance de succès. Cette situation d'échec peut survenir pour tous les nombres premiers, elle peut survenir pour certains nombres composés aussi.

Ainsi on décompose 372469 avec c= 3 ou c =5 mais pas c=1
Algorithme non fiable à 100%...
A moins, peut-être, de prévoir une boucle d'essai pour c 3 5 7 si on arrive à pgcd = n pour c = 1.
Il est précisé ailleurs qu'il est inopérant dans le cas de clés RSA...
Le petit curieux qui a fait la demande d'un tel code, en C++ de préférence, voulait casser le "log discret" avec...

[rambc]

Essayes ceci :

Code :

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

1
2
import os, sys
sys.path.append(os.path.normpath("C:/Python26/libs/site-packages"))