Forum de mathématiques - Bibm@th.net

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

[Python] Factorisation d'un nombre (méthode de rho-Pollard)

Bonjour,

Malgré tous mes efforts je ne peux pas réduire la durée de fonctionnement pour les deux variantes de Richard Brent.
Méthode 1
Adaptée de http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

# usr/bin/env python
# -*- coding: utf-8 -*-

from time import time

def pgcd(a,b):
    while b>0:
        a,b=b,a%b      
    return a

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)
    y=((y**2+c)**2+1)%n    # y = (f o f)(y)
    a=pgcd(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"

Résultat :

Le nombre 10023859281455311421 se factorise ainsi :
           7660450463 * 1308520867

Temps de travail : 0.375 s

Avec cette variante qui recherche une valeur de x antérieure stockée dans une liste, le temps de calcul est doublé (Voir http://www-lipn.univ-paris13.fr/~bander … facto.html) :

# 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,75 s, le double !!!

Alors, j'ai rusé ! J'ai réussi à stocker le "bon" xk sans avoir à le recalculer ni à le stocker dans une liste...
Je suis encore 2 fois plus lent ! Je cherche toujours pourquoi et je me renseigne auprès de plus compétent que moi...

@+

---

Arx Tarpeia Capitoli proxima...

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Bon me revoilà,

Après consultation de personnes avisées, j'ai réussi à tout optimiser, on ne peut pas faire mieux...
Et je signale, à partir de la version 2.6 de Python, l'existence d'un module fractions, au sein duquel a été implémenté le calcul du pgcd de 2 nombres

>>> from fractions import gcd
>>> gcd(132,165)
33
>>>

Le 1er code ainsi modifié est le plus rapide sans contestation possible :

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

while a==1:
    x=(x*x+c)%n           # x = f(x)              (mod n)
    y=(y*y+c)%n    
    y=(y*y+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"

Résultat
Temps de travail : 0.28200006485 s (pour 14557 itérations)

2e code optimisé :

# usr/bin/env python
# -*- coding: utf-8 -*-

from math import log
from time import time
from fractions import gcd

tp_d=time()
x,a,xk,c=2,1,1,1
n=10023859281455311421
i=1
while a==1:
    i+=1
    k=2**int(log(i)/log(2))
    x=(x*x+c)%n
    a=gcd(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

Résultat
Temps de travail : 0.625 s (pour 34091 itérations)
Le 1er est 60% plus rapide que le 2nd et c'est l'algorithme qui est en cause : 14557 itérations pour obtenir le résultat contre 34091 pour l'autre...

@+

---

Arx Tarpeia Capitoli proxima...

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Salut,

Alors, j'ai rusé ! J'ai réussi à stocker le "bon" xk sans avoir à le recalculer ni à le stocker dans une liste...
Je suis encore 2 fois plus lent ! Je cherche toujours pourquoi et je me renseigne auprès de plus compétent que moi...

Comment fais-tu pour stocker directement le bon xk ?

Quoi qu'il en soit, le problème, c'est que l'accès à un élément k d'une liste prend un temps O(k). Tu devrais plutôt utiliser un tableau, dont l'accès à un élément prend un temps O(1).

A bientôt.

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

RE,

stocker le bon xk, c'est pas difficile mais ça m'a quand même pris 1/2 journée pour avoir l'idée...
J'ai fait défiler les i et les 2**int(log(i)/log(2))-1
  i    k
  1   0
  2   1
  3   1
  4   3
  5   3
  6   3
  7   3
  8   7
  9   7
10   7
11   7
12   7
13   7
14   7
15   7
16  15
17  15
18  15
.........
Et j'ai constaté que que les xk à stocker étaient placés juste avant que i soit une puissance de 2, donc des puissances de 2 - 1
j'ai donc calculé k = 2**int(log(i)/log(2)) sans enlever 1, ce qui permet en fin de boucle le :
if == i:
     xk=x
Et j'ai donc mon xk pour les tours suivants...

@+

---

Arx Tarpeia Capitoli proxima...

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Et j'ai constaté que que les xk à stocker étaient placés juste avant que i soit une puissance de 2, donc des puissances de 2 - 1
j'ai donc calculé k = 2**int(log(i)/log(2)) sans enlever 1, ce qui permet en fin de boucle le :
if k == i:
     xk=x
Et j'ai donc mon xk pour les tours suivants...

OK. Merci beaucoup pour l'idée.

Ah oui, j'oubliais un truc : peut-être que tu essaies avec des nombres trop petits pour voir la différence en complexité asymptotique ?

Dernière modification par thadrien (26-10-2009 14:55:01)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Salut,

Est-ce que, pour toi, 10023859281455311421 est trop petit ?

@+

---

Arx Tarpeia Capitoli proxima...

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Est-ce que, pour toi, 10023859281455311421 est trop petit ?

Peut-être. Essaie plutôt un truc style : 654964894651563467 * 19873265519 = 13016291257034383768171194373. Factoris de WIMS le factorise très rapidement, donc tu ne devrais pas avoir trop de difficultés.

Dernière modification par thadrien (26-10-2009 17:59:34)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

RE :

Le nombre 13016291257034383768171194373 se factorise ainsi :
           19873265519 * 654964894651563467

Temps de travail : 6.18799996376 s

;-)

@+

---

Arx Tarpeia Capitoli proxima...

thadrien

Membre

Lieu : Grenoble

Inscription : 18-06-2009

Messages : 526

Site Web

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Ça commence à devenir des temps assez longs pour voir quelque chose. Faut continuer les essais avec des nombres de plus en plus longs.

Florim

Invité

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Salut,
Ca date un peu mais j'arrive pas à importer gcd, qqun a une explication ?

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Re,

>>> from fractions import gcd
>>> print (gcd(48,60))
12

Si ça ne marche pas,
- vérifie la variable d'environnement path
- version de Python ? Installée par qui ? comment ?

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 698

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

Bonjour
@Yoshi
effectivement on ne peut importer gcd :
voici le message d'erreur :
Traceback (most recent call last):
  File "/usr/lib/python3.9/idlelib/run.py", line 559, in runcode
    exec(code, self.locals)
  File "/home/gilbert/Programmes/Python/crible_G.py", line 3, in <module>
    from fractions import gcd
ImportError: cannot import name 'gcd' from 'fractions' (/usr/lib/python3.9/fractions.py)

Pour le reste :

si $i$ est un nombre de Mersenne = $2^n -1$

Je suis parti du nombre X = 13016291257034383768171194373 du post au dessus ..

je récupère le PGCD = X ; puis on le met au carré et on ajoute 1 : (" donc on transforme le PGCD en  un nombre de Fermat ")

j'ai ce nombre de 86 digit :

X = 19283635235010757318836917200237668345470484572549790364309671655196725561403266082609 (86 digits)

$X^2+1$ qui serra divisible par 2 et un petit facteur premier  5, 13 .. 37... souvent inférieur à 41, mais on obtient un autre PGCD encore plus grand ....et ainsi de suite

X = 23875113860559757167662937759315939367424104813323103152324723911052620077274261982190596716880457550794712289293 (113 digits)

puis :

$X^2+1$ , donne le PGCD  X =

522940234641110080871440237169026575520056445068482721271514659620113046579137158316602265193446478575493707769537213347578599293266137328840297723950438194623421497640453023119295323273727844427406217 (201 digits)

$X^2+1$ =
273466489006499267 832361898879357151002069 267819429145867669189818 090938083709268339473377 741698138835813595246568 233560070532590024391761 648941990088923612330845 347587128317475619231482 151535276926055920510002 136167075931340016095041 440066546370552464102565 947409664313396740552674 437001195875434689244293 311785460720998204105111 396481312955938976921811 462299088961758337264233 320482765888370330251090 (402 digits) =
2 × 5 × 17 × 22921 × 61441 × 83680345945032973 × 13650227507023913855482568465061143226560716537647135962189698455945038749328492864900606446411070772037524295263706295300422004474877964178384810662707721917258889049396596743223617542361265300668342670604431057371869193023807253609944940345886264607243 605975490211409619446157793053381206971280518087242305729171812108290578577006176031527250696545091190485619947013440209 (
(374 digits) ; celui ci aucun résultat sur Alpertron.com au bout de 4h30 donc je suppose probablement prime....

Dernière modification par LEG (17-06-2021 12:58:57)

yoshi

Modo Ferox

Inscription : 20-11-2005

Messages : 17 101

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

B'jour,

La réponse est là :

Changed in version 3.9: The math.gcd() function is now used to normalize the numerator and denominator. math.gcd() always return a int type. Previously, the GCD type depended on numerator and denominator.

A partir de la v. 3.8 :

from math import gcd

@+

---

Arx Tarpeia Capitoli proxima...

LEG

Membre

Inscription : 19-09-2012

Messages : 698

Re : [Python] Factorisation d'un nombre (méthode de rho-Pollard)

re
impeccable merci

je viens de tester
Le nombre n = 13016291257034383768171194373 se factorise ainsi :
19873265519 * 6.549648946515635e+17
Temps de travail : 0.6110134124755859
>>>

je viens de regarder pour n = 19283635235010757318836917200237668345470484572549790364309671655196725561403266082609

il tourne....
il n'est pas premier :
6062144414067175 636201395811936711957057  × 3180992387819593789609 997698984136958924599537
 
il faut un peu plus de 20 minute sur Alpertron

et celui ci : 23875113860559757167662937759315939367424104813323103152324723911052620077274261982190596716880457550794712289293 est premier

Ainsi que : 522940234641110080871440237169026575520056445068482721271514659620113046579137158316602265193446478575493707769537213347578599293266137328840297723950438194623421497640453023119295323273727844427406217

Dernière modification par LEG (17-06-2021 07:59:10)