cryptographyprime-factoringfactorization

Algorithms for factorizing a 30 decimal digit number


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.


Solution

  • 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.