This recipe uses trial division to get factors below 1 milion then switches to Brent's algorithm to get bigger factors. No fast enough to break a RSA key :)
Python, 70 lines
Download
Copy to clipboard1 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | from fractions import gcd
from random import randint
def brent(N):
# brent returns a divisor not guaranteed to be prime, returns n if n prime
if N%2==0: return 2
y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
g,r,q = 1,1,1
while g==1:
x = y
for i in range(r):
y = ((y*y)%N+c)%N
k = 0
while (k<r and g==1):
ys = y
for i in range(min(m,r-k)):
y = ((y*y)%N+c)%N
q = q*(abs(x-y))%N
g = gcd(q,N)
k = k + m
r = r*2
if g==N:
while True:
ys = ((ys*ys)%N+c)%N
g = gcd(abs(x-ys),N)
if g>1: break
return g
def factorize(n1):
if n1<=0: return []
if n1==1: return [1]
n=n1
b=[]
p=0
mx=1000000
while n % 2 ==0 : b.append(2);n//=2
while n % 3 ==0 : b.append(3);n//=3
i=5
inc=2
#use trial division for factors below 1M
while i <=mx:
while n % i ==0 : b.append(i); n//=i
i+=inc
inc=6-inc
#use brent for factors >1M
while n>mx:
p1=n
#iterate until n=brent(n) => n is prime
while p1!=p:
p=p1
p1=brent(p)
b.append(p1);n//=p1
if n!=1:b.append(n)
b.sort()
return b
from functools import reduce
from sys import argv
def main():
if len(argv)==2:
n=int(argv[1])
else:
n=int(eval(input(" Integer to factorize? ")))
li=factorize(n)
print (n,"= ",li)
print ("n - product of factors = ",n - reduce(lambda x,y :x*y ,li))
if __name__ == "__main__":
main()
|
