I wrote a polynomial time integer factorization algorithm; I was wondering where it stands?

Question

Below is the Python code for my algorithm that computes the unique prime factors of an integer n in O(n*log(log(n))) time. I was wondering where it ranks among other integer factorization algorithms; from what I've read the current state-of-the-art algorithm GNFS is subexponential which is slower than polynomial time.

def compute_prime_factors(n):
    slots = [[],[],[2]]
    current_slot = 2
    for j in range(n):
        slots.append([])
    while current_slot <= n:
        current_slot_prime_factors = slots[current_slot]
        if current_slot_prime_factors == []:
            if current_slot+current_slot <= n:
                slots[current_slot+current_slot].append(current_slot)
        else:
            for prime_factor in current_slot_prime_factors:
                if current_slot+prime_factor <= n:
                    slots[current_slot+prime_factor].append(prime_factor)
        current_slot += 1
    return slots[n]

def compute_exponents(n, prime_factors):
    exponents = []
    for prime_factor in prime_factors:
        exponent = 0
        while n % prime_factor == 0:
            n = n // prime_factor
            exponent += 1
        exponents.append(exponent)
    return exponents

N = 5589222
prime_factors = compute_prime_factors(N)
exponents = compute_exponents(N, prime_factors)
print(N, prime_factors, exponents)

So to conclude, my algorithm has an O(n*log(log(n))) time-complexity and a O(n) space-complexity and it computes the prime factors of an integer n. I was wondering if this is faster than the current best integer factorization algorithms.

Answer 1

The algorithm you present is unique and correct, but not very efficient. Let's look at the simplest possible method, trail division.

std::vector<uint64_t> factors;
for (auto i = 2; i < n; ++i)
    while (n % i == 0) {
        factors.push_back(i);
        n /= i;
    }
}
if (n > 1)
    factors.push_back(n);

This algorithm has O(n) time complexity and O(1) space complexity which is superior to the posted method.

Modern factorization algorithms such as the General Number Field Sieve have O(log n * log log n) time complexity. Wikipedia provides a good overview.

I would suggest trying to implement some of the simpler methods such as Wheel Factorization or Pollard's Rho Algorithm to get a feel for some of the techniques.