随机算法--Las Vegas算法--大数因子分解--Pollard Rho启发式算法（python版）
'''Created on 2012-3-10
@author: daweibalong
'''
from random import randint
f=[]
def gcd(m,n):
if n>0:
return gcd(n,m%n)
return m
def isPrime(n):
if n<2:
return True
for i in range(2,int(n**0.5)+1):
if n%i==0:
return False
return True
def ifenough(num):
m=1
for i in f:
m*=i
if m==num:
return 0
if m>num:
return 1
return 2
def PollardRho(num,n):
if(isPrime(n)):
f.append(n)
return;
x=[]
i=1
x.append(-1)
x.append(randint(1,n))
y=x
k=2
while True:
i+=1
x.append((abs(x*x-1))%n)
d=gcd(abs(y-x),n)
if d>1 and d<n:
PollardRho(num,d)
PollardRho(num,n/d)
if i==k:
y=x
k=2*k
if x.index(x,0,i+1)!=i or ifenough(num)==0 or ifenough(num)==1:
break
def repeat(n):
while True:
f[:]=[]
PollardRho(n,n)
if ifenough(n)==0:
f.sort(cmp=None, key=None, reverse=False)
for index,j in enumerate(f):
if index!=len(f)-1:
print j,'*',
else:
print j
break
if __name__=='__main__':
print 'please enter the number you want to divide:',
n=int(raw_input())
repeat(n)
页:
[1]