Algorithms for factorizing a 30 decimal digit number

Question

My professor has given me an RSA factoring problem has assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a headache to choose one for my given requirements. Which all algorithms give better performance for 30 decimal digit numbers?

Note: So far I have read about Brute force approach and Quadratic Sieve. The latter is complex and the former time consuming.

Answer 1

There's another method called Pollard's Rho algorithm, which is not as fast as the GNFS but is capable of factoring 30-digit numbers in minutes rather than hours.

The algorithm is very simple. It stops when it finds any factor, so you'll need to call it recursively to obtain a complete factorisation. Here's a basic implementation in Python:

def rho(n):
    def gcd(a, b):
        while b > 0:
            a, b = b, a%b
        return a
    g = lambda z: (z**2 + 1) % n
    x, y, d = 2, 2, 1
    while d == 1:
        x = g(x)
        y = g(g(y))
        d = gcd(abs(x-y), n)
    if d == 0:
        print("Can't factor this, sorry.")
        print("Try a different polynomial for g(), maybe?")
    else:
        print("%d = %d * %d" % (n, d, n // d))

rho(441693463910910230162813378557) # = 763728550191017 * 578338290221621

Or you could just use an existing software library. I can't see much point in reinventing this particular wheel.