빠른 소인수 분해 (Very Large Number Prime Factorization)

'''

    Factor1

'''

def factor1(n):

    if n == 1: return [1]

    i = 2

    limit = n**0.5

    while i <= limit:

        if n % i == 0:

            ret = factor1(n/i)

            ret.append(i)

            return ret

        i += 1

    return [n]

'''

    Factor2 - Improved Factor1

'''

def factor2(n):

##    yield 1

    i = 2

    limit = n**0.5

    while i <= limit:

        if n % i == 0:

            yield i

            n = n / i

            limit = n**0.5

        else:

            i += 1

    if n > 1:

        yield n

'''

    Factor3 - Pollard Rho Prime Factorization

'''

import random

from Queue import Queue

def gcd(a,b):

    while b:

        a,b=b,a%b

    return a

def rabin_miller(p):

if(p<2):

return False

if(p!=2 and p%2==0):

return False

s=p-1

while(s%2==0):

s>>=1

for i in xrange(10):

a=random.randrange(p-1)+1

temp=s

mod=pow(a,temp,p)

while(temp!=p-1 and mod!=1 and mod!=p-1):

mod=(mod*mod)%p

temp=temp*2

if(mod!=p-1 and temp%2==0):

return False

return True

def brent(n):

    if(n%2==0):

        return 2;

    x,c,m=random.randrange(0,n),random.randrange(1,n),random.randrange(1,n)

    y,r,q=x,1,1

    g,ys=0,0

    while(True):

        x=y

        for i in range(r):

            y,k=(y*y+c)%n,0

        while(True):

            ys=y

            for i in range(min(m,r-k)):

                y,q=(y*y+c)%n,q*abs(x-y)%n

            g,k=gcd(q,n),k+m

            if(k>= r or g>1):break

        r=2*r

        if(g>1):break

    if(g==n):

        while(True):

            ys,g=(x*x+c)%n,gcd(abs(x-ys),n)

            if(g>1):break

    return g

def pollard(n):

        if(n%2==0):

            return 2;

        x=random.randrange(2,1000000)

        c=random.randrange(2,1000000)

        y=x

        d=1

        while(d==1):

            x=(x*x+c)%n

            y=(y*y+c)%n

            y=(y*y+c)%n

            d=gcd(x-y,n)

            if(d==n):

                break;

        return d;

def factor3(n):
    if n==1: 

        return [1] 

    Q_1=Queue()

    Q_2=[]

    Q_1.put(n)

    while(not Q_1.empty()):

        l=Q_1.get()

        if(rabin_miller(l)):

            Q_2.append(l)

            continue

        d=pollard(l)

        if(d==l):Q_1.put(l)

        else:

            Q_1.put(d)

            Q_1.put(l/d)

    return Q_2

    

if  __name__ == "__main__":

    import time

    print 'factor1'

    start = time.time()

    print factor1(200000000000000000000000000009)

    print 'time : ', time.time() - start

    print '------------------------'

    print 'factor2'

    start = time.time()

    print [i for i in factor2(200000000000000000000000000009)]

    print 'time : ', time.time() - start

    print '------------------------'

    print 'factor3'

    start = time.time()

    print factor3(200000000000000000000000000009)

    print 'time : ', time.time() - start

    print '------------------------'


설명

Factor2는 Factor1을 개선한 버전
Factor3은 새로운 방식


실행 결과

factor1

[13430577524641L, 2094523, 89, 47, 47, 43, 29, 29]

time :  6.97499990463

------------------------

factor2

[29, 29, 43, 47, 47, 89, 2094523, 13430577524641L]

time :  4.16300010681

------------------------

factor3

[47L, 47L, 29L, 29L, 43L, 89L, 2094523L, 13430577524641L]

time :  0.0350000858307

------------------------

출처 

factor1, factor2
http://blog.dhananjaynene.com/2009/01/2009-is-not-a-prime-number-a-python-program-to-compute-factors/ 

factor3
http://code.activestate.com/recipes/577037-pollard-rho-prime-factorization/