Subversion Repositories Code-Repo

def PollardPM1(N,B):
        '''Implementation of the Pollard p-1 algorithm for factoring primes'''
        a = 2;
        for i in range(2,B):
                a = a**i % N
        d = GCD(a-1,N)
        if 1 < d < N:
                return d
        else:
                return -1;

def PollardRho(N,x_1):
        '''Implementation of the Pollard Rho algorithm for factoring primes'''
        x = x_1
        y = PollardRhoHelper(x) % N
        g = GCD(abs(x-y),N)
        iterations = 0;
        while g == 1:
                        iterations += 1
                        x = PollardRhoHelper(x) % N
                        y = PollardRhoHelper(y) % N
                        y = PollardRhoHelper(y) % N
                        g = GCD(abs(x-y),N)
        print("Iterations: %d\n" % (iterations))
        if g == N:
                return -1
        else:
                return g
        
def PollardRhoHelper(x):
        return x**2 + 1

def Extended_Euclidian(a, b):
        ''' Takes values a and b and returns a tuple (r,s,t) in the following format:
                r = s * a + t * b where r is the GCD and s and t are the inverses of a and b'''
        t_ = 0
        t = 1
        s_ = 1
        s = 0
        q = int(a/b)
        r = a - q * b
        # print("%d\t= %d * %d + %d" % (a, q, b, r))
        while r > 0:
                temp = t_ - q * t
                t_ = t
                t = temp
                temp = s_ - q * s
                s_ = s
                s = temp
                a = b
                b = r
                q = int(a/b)
                r = a - q * b
                # print("%d\t= %d * %d + %d" % (a, q, b, r))
        r = b
        return (r, s, t)

def GCD(q,N):
        '''Returns the multiplicative inverse of a and b'''
        ret = Extended_Euclidian(q,N)
        return ret[0]

def Inverse(a, b):
        '''Returns the multiplicative inverse of a mod b'''
        ret = Extended_Euclidian(a,b)
        if (ret[1] < 0):
                inv = ret[1] + b
        else:
                inv = ret[1]
        return inv

if __name__ == '__main__':
        prime1 = 112426043
        prime2 = 262063
        prime3 = 9420457

        for i in range(100):
                p = PollardPM1(prime1,i)
                if p != -1:
                        print("Prime found with B = %d with value %d\n" % (i,p))
                        break

        p = PollardRho(prime2,1)
        print("A prime factor of %d is %d\n" % (prime2,p))

        p = PollardRho(prime3,1)
        print("A prime factor of %d is %d\n" % (prime3,p))