| 0,0 → 1,93 |
|---|
| 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) |