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 Shanks(n,a,b):
        ''' Implements the Shanks algorithm for solving the Discrete Logarithm Problem'''
        m = math.ceil(math.sqrt(n))
        d = a**m % n

        # Generate and sort list L1
        L1 = dict()
        for i in range(m):
                L1[i] = d**i % n
        print('L1: (unsorted)')
        for i in range(m):
                print("%d\t:\t%d" % (i, L1[i]))
        L1 = sorted(L1.items(), key=lambda x: x[1])
        
        # Generate and sort list L2
        L2 = dict()
        for i in range(m):
                L2[i] = b * Inverse(a**i, n) % n
        print('L2: (unsorted)')
        for i in range(m):
                print("%d\t:\t%d" % (i, L2[i]))
        L2 = sorted(L2.items(), key=lambda x: x[1])

        # Search for a pair with identical second coordinates
        for e in L1:
                for f in L2:
                        if e[1] == f[1]:
                                j = e[0]
                                k = f[0]
                                break;

        return m * j + k % n

if __name__ == '__main__':
        # a = 2
        # b = 767
        # n = 526483
        # d = Shanks(n, a, b)
        # print(d)

        # a = 2
        # b = 48
        # n = 101
        # d = Shanks(n, a, b)
        # print(d)

        # a = 2
        # b = (48**27)*(27**33)
        # n = 101
        # d = Shanks(n, a, b)
        # print(d)

        a = 2
        b = 19
        n = 4481
        d = Shanks(n, a, b)
        print(d)