Welcome, guest | Sign In | My Account | Store | Cart

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
 ``` 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 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 (k1: 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() ```
 Created by Antoni Gual on Mon, 27 Apr 2015 (MIT)

### Required Modules

• (none specified)