Subversion Repositories Code-Repo

import math

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 = 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 = a//b
                r = a - q * b
                # print("%d\t= %d * %d + %d" % (a, q, b, r))
        r = b
        return (r, s, t)

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

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

def PollardRhoLog(G,p,n,alpha,beta):
        '''Implements the Pollard Rho discrete log factoring algorithm'''
        def PollardRhoFunction(x,a,b):
                '''Helper functions for defining sets'''
                if x % 3 == 1:
                        return (beta*x%p,a,(b+1)%n)
                elif x % 3 == 0:
                        return (x**2%p,2*a%n,2*b%n)
                else:
                        return (alpha*x%p,(a+1)%n,b)

        i = 1
        (x,a,b) = PollardRhoFunction(G[0],G[1],G[2])
        (x_,a_,b_) = PollardRhoFunction(x,a,b)
        print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_))

        while x != x_:
                i += 1
                (x,a,b) = PollardRhoFunction(x,a,b)
                (x_,a_,b_) = PollardRhoFunction(x_,a_,b_)
                (x_,a_,b_) = PollardRhoFunction(x_,a_,b_)
                print("i =", i, ":", (x,a,b), "\t2i :", (x_,a_,b_))
        if GCD(b_-b,n) != 1:
                return -1
        else:
                return (a-a_)*Inverse((b_-b), n)%n


if __name__ == '__main__':
        print(PollardRhoLog((1,0,0),526483,87747,13,59480))