About an integer factoring algorithm

Question

I have been toying with the following algorithm:

Z = integers
P = primes

Z factor(Z n, Z base)
    if n in P (implement using a probabilistic primality test)
        return n
    if gcd(n, base) > 1
        return gcd(n, base)
    i <- 1
    while i <= k (k is some constant, big enough)
        m <- log_base(n)
        j <- 1
        while j <= i*m
            q <- n^i (mod base^j)
            g <- gcd(q, n) (mod n)
            if g > 1
                return g
            j <- j + 1
        i <- i + 1

The question is: does it always find a factor? And if it does how big must k be? I have implemented this in Python and in C++ and in C, and one particular number that seems to require a lot of computation is $2^{67}-1$, it seems to take "forever" on my currently modest hardware, when base = 2.