Primfaktoren mittels Backtracking ermitteln

Der hier gezeigte und in Python 2 implementierte Algorithmus kann mittels binärer Suche und Backtracking natürliche Zahlen in ihre Primfaktoren zerlegen. Das macht den Algorithmus allerdings nicht besser oder schneller als andere Algorithmen. Die Laufzeit dürfte im Bereich von $\mathcal{O} \sqrt{2^n}$ liegen, wobei $n$ die Länge der zu faktorisierenden Zahl in Bits ist.

import sys
def getbit(i,n):
        return (i>>n)&1
 
def setbit(i,n,val=1):
        if val==1:
                return i | (1<<n)
        return i & (~(1<<n))
 
def bitcmp(i1,i2,n):
        for i in range (0,n):
                b2 = getbit(i2,i)
                b1 = getbit(i1,i)
                if b1!=b2:
                        return b1-b2
        return 0
 
def fac_check(i,i1,i2,bits):
        p = i1*i2
        if p>i:
                return -3
        if p==i:
                if i1==1 or i2==1:
                        return -4
                return 10
        return bitcmp(i,p,bits)
 
def factorize_run(i,i1,i2,n):
        for b in range (0,4):
                i1 = setbit(i1,n,getbit(b,0))
                i2 = setbit(i2,n,getbit(b,1))
                rc = fac_check(i,i1,i2,n+1)
                if rc==10:
                        return factorize(i1)+factorize(i2)
                if rc==0:
                        f = factorize_run(i,i1,i2,n+1)
                        if f!=[i]:
                                return f
        return [i]
 
 
def factorize(i):
        l = factorize_run(i,0,0,0)
        l.sort()
        return l
 
fpr = int(sys.argv[1])
 
print "Factorizing "+str(fpr)+" ..."
rc = factorize(fpr)
print rc
Code-Sprache: Python (python)