Factorisation des nombres : optimisation du temps de calcul

Version imprimable

Voir 40 message(s) de cette discussion en une page

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,

@+

24/10/2009, 13h30
fred1599
Le PGCD n'a pas besoin d'être recréé. Pour cela utilise le module fractions.
Code:

1 2 3 import fractions as f f.gcd(12785, 15) # Calcul le pgcd de 12785 et 15 5
24/10/2009, 13h51
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é !

@+

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

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:

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:

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

donne

Citation:

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

24/10/2009, 17h43
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

J'ai essayé le petit changement suivant dans le tout 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 # 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...

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:

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:

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

Citation:

Envoyé par yoshik

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

Et oui ;). Extrait de la note concernant xrange:

Citation:

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:

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:

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:

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

Avec le code suivant
Code:

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

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:

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:

Citation:

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:

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.

25/10/2009, 19h17
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:

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:

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

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:

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 :

Citation:

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

@+

26/10/2009, 11h25
rambc

Citation:

Envoyé par yoshik

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.
26/10/2009, 11h39
tyrtamos

Citation:

Envoyé par rambc

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
26/10/2009, 11h41
yoshik

Salut

Citation:

Envoyé par rambc

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

@+

Mais on a oublié le meilleur :D : le module psyco

Il permet l'accélération de certaines séquences de 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
# 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%

26/10/2009, 12h09
rambc

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

Citation:

Envoyé par yoshik

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 .
26/10/2009, 12h53
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
26/10/2009, 13h33
rambc

Citation:

Envoyé par tyrtamos

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

Citation:

Envoyé par tyrtamos

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

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:

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

Citation:

Envoyé par tyrtamos

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

Citation:

Envoyé par wikipedia

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

Essayes ceci :

Code:

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

Voir 40 message(s) de cette discussion en une page