Can this integer factorization in Python be improved?

Question

I've seen many ways of doing integer factorizations in Python, but didn't really understand them, so I tried to do it on my own way:

def factorisation(n):
    fact = []
    i = 2
    while i <= n:   
        if n % i == 0:      
            fact.append(i)
            n //= i
        else:
            i += 1
    return fact

I think it is working, but I don't really know why the while loop from i to n... From my lesson I learnt that we have to do it from 2 to sqrt(n).

Did I misunderstand something?

Can I improve it?

Answer 1

You can use Pollard's rho integer factorization algorithm. It's quite efficient and fast compared to other algorithms that are much slower. For example:

Python 3:

from math import gcd

def factorization(n):

    factors = []

    def get_factor(n):
        x_fixed = 2
        cycle_size = 2
        x = 2
        factor = 1

        while factor == 1:
            for count in range(cycle_size):
                if factor > 1: break
                x = (x * x + 1) % n
                factor = gcd(x - x_fixed, n)

            cycle_size *= 2
            x_fixed = x

        return factor

    while n > 1:
        next = get_factor(n)
        factors.append(next)
        n //= next

    return factors

With small numbers it's very fast, in this case it has taken only 0.035 seconds.

print(factorization(823767))

~$ time python3 factorization.py
[3, 7, 39227]

real    0m0,035s
user    0m0,031s
sys     0m0,004s

If we use slightly larger numbers the calculation time increases, but it's still very fast, in this case just 0.038 seconds.

print(factorization(41612032092))

~$ time python3 factorization.py
[3, 4, 37, 1681, 127, 439]

real    0m0,038s
user    0m0,034s
sys     0m0,004s

And if we use very large numbers it takes a little more time, but it's still a very reasonable time considering that it's a huge number. In this case just 28.128 seconds.

print(factorization(23756965471926357236576238546))

~$ time python3 factorization.py
[3, 3, 2, 479, 11423, 582677, 413975744296733]

real    0m28,128s
user    0m28,120s
sys     0m0,008s

I hope it helps you. Greetings.