Subversion Repositories Code-Repo

Compare Revisions

No changes between revisions

Regard whitespace Rev 146 → Rev 219

/Classwork/MATH4176 - Cryptography 2/ElGamal.py
0,0 → 1,82
# Encrypted Data
data_set = ((3781,14409),(31552,3930),(27214,15442),(5809,30274),
(5400,31486),(19936,721),(27765,29284),(29820,7710),
(31590,26470),(3781,14409),(15898,30844),(19048,12914),
(16160,3129),(301,17252),(24689,7776),(28856,15720),
(30555,24611),(20501,2922),(13659,5015),(5740,31233),
(1616,14170),(4294,2307),(2320,29174),(3036,20132),
(14130,22010),(25910,19663),(19557,10145),(18899,27609),
(26004,25056),(5400,31486),(9526,3019),(12962,15189),
(29538,5408),(3149,7400),(9396,3058),(27149,20535),
(1777,8737),(26117,14251),(7129,18195),(25302,10248),
(23258,3468),(26052,20545),(21958,5713),(346,31194),
(8836,25898),(8794,17358),(1777,8737),(25038,12483),
(10422,5552),(1777,8737),(3780,16360),(11685,133),
(25115,10840),(14130,22010),(16081,16414),(28580,20845),
(23418,22058),(24139,9580),(173,17075),(2016,18131),
(19886,22344),(21600,25505),(27119,19921),(23312,16906),
(21563,7891),(28250,21321),(28327,19237),(15313,28649),
(24271,8480),(26592,25457),(9660,7939),(10267,20623),
(30499,14423),(5839,24179),(12846,6598),(9284,27858),
(24875,17641),(1777,8737),(18825,19671),(31306,11929),
(3576,4630),(26664,27572),(27011,29164),(22763,8992),
(3149,7400),(8951,29435),(2059,3977),(16258,30341),
(21541,19004),(5865,29526),(10536,6941),(1777,8737),
(17561,11884),(2209,6107),(10422,5552),(19371,21005),
(26521,5803),(14884,14280),(4328,8635),(28250,21321),
(28327,19237),(15313,28649))
 
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 Decrypt(n):
'''Decodes an encoding where n = a * 26^2 + b * 26 + c'''
a = int(n / 676)
n = n - (a * 676)
b = int(n / 26)
n = n - (b * 26)
c = n
return (a, b, c)
 
if __name__ == '__main__':
p = 31847
a = 7899
 
# For each encrypted data packet, decrypt it using the following function:
# d(y_1,y_2) = y_2(y_1^a)^-1 mod p
for i in data_set:
d = i[1] * Inverse(i[0]**a,p) % p
s = Decrypt(d)
print("%c%c%c" % (chr(s[0]+65), chr(s[1]+65), chr(s[2]+65)), end='')
print()
/Classwork/MATH4176 - Cryptography 2/EllipticCurve.py
0,0 → 1,112
 
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'''
if (a < 0):
a = a + b
ret = Extended_Euclidian(a,b)
if (ret[1] < 0):
inv = ret[1] + b
else:
inv = ret[1]
return inv
 
def Elliptic_Curve_Add(p, a, b, point_1, point_2):
'''Adds two points on an Elliptical Curve and returns the result'''
# Adding a point at infinity results in the same point
if point_1[0] == 'x' and point_1[1] == 'x':
return point_2
if point_2[0] == 'x' and point_2[1] == 'x':
return point_1
 
# Test to make sure both points are on the curve
z = (point_1[0]**3 + a*point_1[0] + b) % p
if z**((p-1)//2)%p != 1:
print("Point", point_1, "is not on the elliptic curve!")
return
z = (point_2[0]**3 + a*point_2[0] + b) % p
if z**((p-1)//2)%p != 1:
print("Point", point_2, "is not on the elliptic curve!")
return
 
# If x_1 == x_2 and y_1 != y_2, return point at infinity
if point_1[0] == point_2[0] and point_1[1] != point_2[1]:
return ('x','x')
 
# If point_1 == point_2, slope = (3 x_1^2 + a)(2 y_1)^-1
if point_1[0] == point_2[0] and point_1[1] == point_2[1]:
inv = Inverse(2*point_1[1], p)
slope = ((3 * point_1[0]**2 + a) * inv) % p
else: # Otherwise point_1 != point_2, slope = (y_2 - y_1)(x_2 - x_1)^-1
inv = Inverse(point_2[0] - point_1[0], p)
slope = ((point_2[1] - point_1[1]) * inv) % p
 
# Calculate the third point given the slope
x_3 = (slope**2 - point_1[0] - point_2[0]) % p
y_3 = (slope * (point_1[0] - x_3) - point_1[1]) % p
return (x_3,y_3)
 
def Elliptic_Curve_Multiple(p, a, b, point, multiple):
'''Returns a multiple of a point on an Elliptical Curve'''
ret = point
for i in range(multiple-1):
ret = Elliptic_Curve_Add(p, a, b, ret, point)
print(i+2,":",ret)
return ret
 
if __name__ == '__main__':
# print("For the following tests, the curve y^2 = x^3 + x + 6 is used")
# print("\nResult when point is not on the curve (quadratic residue failed):")
# print(Elliptic_Curve_Add(11, 1, 6, (1,2), (2,7)))
 
# print("\nResult when one or both points being the point at infinity:")
# print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), (2,7)))
# print(Elliptic_Curve_Add(11, 1, 6, (2,7), ('x','x')))
# print(Elliptic_Curve_Add(11, 1, 6, ('x','x'), ('x','x')))
 
# print("\nResult when adding two distinct points:")
# print(Elliptic_Curve_Add(11, 1, 6, (2,7), (7,9)))
 
# print("\nResult when adding a point to itself:")
# print(Elliptic_Curve_Add(11, 1, 6, (2,7), (2,7)))
 
# print("\nResult when computing multiples of a point:")
# Elliptic_Curve_Multiple(11, 1, 6, (2,7), 3)
 
# print("\nFor the following tests, the curve y^2 = x^3 + 5x + 4 is used")
# print("\nAttempting to add point (220,407) to itself:")
# print(Elliptic_Curve_Add(997, 5, 4, (220,407), (220,407)))
 
# print("\nResult of 267(220,407):")
# Elliptic_Curve_Multiple(997, 5, 4, (220,407), 267)
 
Elliptic_Curve_Multiple(71,1,28,(1,32),10)
/Classwork/MATH4176 - Cryptography 2/Factoring.py
0,0 → 1,88
 
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))
/Classwork/MATH4176 - Cryptography 2/GCD.py
0,0 → 1,31
 
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)
 
if __name__ == '__main__':
a = 99
b = 101
res = Extended_Euclidian(a, b)
print("%d = %d * %d + %d * %d" % (res[0], res[1], a, res[2], b))
/Classwork/MATH4176 - Cryptography 2/Notes.pdf
Cannot display: file marked as a binary type.
svn:mime-type = application/octet-stream
/Classwork/MATH4176 - Cryptography 2/Notes.pdf
Property changes:
Added: svn:mime-type
+application/octet-stream
\ No newline at end of property
/Classwork/MATH4176 - Cryptography 2/PollardRhoLog.py
0,0 → 1,71
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))
/Classwork/MATH4176 - Cryptography 2/RSA.py
0,0 → 1,116
import random
 
RSA_Text_1 = [12423,11524,7243,7459,14303,6127,10964,16399,9792,13629,14407,18817,
18830,13556,3159,16647,5300,13951,81,8986,8007,13167,10022,17213,2264,961,17459,
4101,2999,14569,17183,15827,12693,9553,18194,3830,2664,13998,12501,18873,12161,
13071,16900,7233,8270,17086,9792,14266,13236,5300,13951,8850,12129,6091,18110,
3332,15061,12347,7817,7946,11675,13924,13892,18031,2620,6276,8500,201,8850,
11178,16477,10161,3533,13842,7537,12259,18110,44,2364,15570,3460,9886,8687,4481,
1231,7547,11383,17910,12867,13203,5102,4742,5053,15407,2976,9330,12192,56,2471,
15334,841,13995,17592,13297,2430,9741,11675,424,6686,738,13874,8168,7913,6246,
14301,1144,9056,15967,7328,13203,796,195,9872,16979,15404,14130,9105,2001,9792,
14251,1498,11296,1105,4502,16979,1105,56,4118,11302,5988,3363,15827,6928,4191,
4277,10617,874,13211,11821,3090,18110,44,2364,15570,3460,9886,9988,3798,1158,
9872,16979,15404,6127,9872,3652,14838,7437,2540,1367,2512,14407,5053,1521,297,
10935,17137,2186,9433,13293,7555,13618,13000,6490,5310,18676,4782,11374,446,
4165,11634,3846,14611,2364,6789,11634,4493,4063,4576,17955,7965,11748,14616,
11453,17666,925,56,4188,18031,9522,14838,7437,3880,11476,8305,5102,2999,18628,
14326,9175,9061,650,18110,8720,15404,2951,722,15334,841,15610,2443,11056,2186]
 
RSA_Text_2 = [6340,8309,14010,8936,27358,25023,16481,25809,23614,7135,24996,30590,
27570,26486,30388,9395,27584,14999,4517,12146,29421,26439,1606,17881,25774,
7647,23901,7372,25774,18436,12056,13547,7908,8635,2149,1908,22076,7372,8686,
1304,4082,11803,5314,107,7359,22470,7372,22827,15698,30317,4685,14696,30388,
8671,29956,15705,1417,26905,25809,28347,26277,7897,20240,21519,12437,1108,
27106,18743,24144,10685,25234,30155,23005,8267,9917,7994,9694,2149,10042,27705,
15930,29749,8635,23646,11738,24591,20240,27212,27486,9741,2149,29329,2149,5501,
14015,30155,18154,22319,27705,20321,23254,13624,3249,5443,2149,16975,16087,
14600,27705,19386,7325,26277,19554,23614,7553,4734,8091,23973,14015,107,3183,
17347,25234,4595,21498,6360,19837,8463,6000,31280,29413,2066,369,23204,8425,
7792,25973,4477,30989]
 
def RSA_Encrypt(x, b, n):
'''Encrypts a plaintext x using b and n'''
return (x**b)%n
 
def RSA_Decrypt(y, a, n):
'''Decrypts a ciphertext y using a and n'''
return (y**a)%n
 
def PollardRho(N):
'''Implementation of the Pollard Rho algorithm for factoring primes'''
if N%2==0:
return 2
x = random.randint(1, N-1)
y = x
c = random.randint(1, N-1)
g = 1
while g==1:
x = ((x*x)%N+c)%N
y = ((y*y)%N+c)%N
y = ((y*y)%N+c)%N
g = GCD(abs(x-y),N)
return g
 
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
 
def Decrypt(n):
'''Decodes an encoding where n = a * 26^2 + b * 26 + c'''
a = int(n / 676)
n = n - (a * 676)
b = int(n / 26)
n = n - (b * 26)
c = n
return (a, b, c)
 
if __name__ == '__main__':
n = 31313
b = 4913
p = PollardRho(n) # Factor n to find a prime
q = int(n / p) # Find the other prime
phi = (q - 1) * (p - 1) # Calculate Phi(n)
a = Inverse(b, phi) # Calculate the decrypting exponent a
print("N = %d, p = %d, q = %d, phi = %d, a = %d, b = %d" % (n, p, q, phi, a, b))
 
# Decrypt the message
for entry in RSA_Text_2:
enc = Decrypt(RSA_Decrypt(entry, a, n))
print("%c%c%c" % (chr(enc[0]+65), chr(enc[1]+65), chr(enc[2]+65)), end='')
print()
/Classwork/MATH4176 - Cryptography 2/Shamir.py
0,0 → 1,82
from operator import mul
from random import randrange, sample
from functools import reduce
 
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 prod(nums):
"""Product of nums"""
return reduce(mul, nums, 1)
 
def horner_mod(coeffs, mod):
"""Polynomial with coeffs of degree len(coeffs) via Horner's rule; uses
modular arithmetic. For example, if coeffs = [1,2,3] and mod = 5, this
returns the function x --> (x, y) where y = 1 + 2x + 3x^2 mod 5."""
return lambda x: (x,
reduce(lambda a, b: a * x + b % mod, reversed(coeffs), 0) % mod)
 
 
def shamir_threshold(S, k, n, p):
"""Shamir's simple (k, n) threshold scheme. Returns xy_pairs genrated by
secret polynomial mod p with constant term = S. Information is given to n
different people any k of which constitute enough to reconstruct the secret
data."""
coeffs = [S]
# Independent but not necessarily unique; choose k - 1 coefficients from [1, p)
coeffs.extend(randrange(1, p) for _ in range(k - 1))
# x values are unique
return map(horner_mod(coeffs, p), sample(range(1, p), n))
 
 
def interp_const(xy_pairs, k, p):
"""Use Lagrange Interpolation to find the constant term of the degree k
polynomial (mod p) that gave the xy-pairs; we get to use a shortcut since
we are only after the constant term for which x = 0."""
assert len(xy_pairs) >= k, "Not enough points for interpolation"
x = lambda i: xy_pairs[i][0]
y = lambda i: xy_pairs[i][1]
return sum(y(i) * prod(x(j) * Inverse(x(j) - x(i), p) % p for j in range(k) if j != i) for i in range(k)) % p
 
 
if __name__ == "__main__":
k, n, p = 5, 9, 81342267667
pairs = [(11,29952055635),(22,26786192733),(33,77756881208),(44,80139093118),(55,24225052606),
(66,74666503567),(77,1078845979),(88,72806030240),(99,1471177497)]
for i in range(9):
lst = []
for j in range(9):
if i != j:
lst.append(pairs[j])
print("Omitting Share", (i), ":", interp_const(lst,k,p))
/Classwork/MATH4176 - Cryptography 2/Shanks-Tonelli.py
0,0 → 1,53
def modular_sqrt(a, p):
'''Finds the square root x^2 = a (mod p) and returns x'''
''' See http://www.math.vt.edu/people/brown/class_homepages/shanks_tonelli.pdf'''
 
if Jacobi_Symbol(a, p) != 1:
return 0
elif a == 0:
return 0
elif p == 2:
return p
elif p % 4 == 3:
return (a**((p+1)/4)) % p
 
s = p - 1
e = 0
while s % 2 == 0:
s /= 2
e += 1
 
n = 2
while Jacobi_Symbol(n, p) != -1:
n += 1
 
x = (a**((s+1)/2)) % p
b = (a**s) % p
g = (n**s) % p
r = e
 
while True:
t = b
m = 0
for m in range(r):
if t == 1:
break
t = (t**2) % p
 
if m == 0:
return x
 
gs = (g**(2 ** (r - m - 1))) % p
g = (gs * gs) % p
x = (x * gs) % p
b = (b * g) % p
r = m
 
def Jacobi_Symbol(a, p):
ls = (a**((p - 1) // 2)) % p
return -1 if ls == p - 1 else ls
 
if __name__ == '__main__':
print(modular_sqrt(2,113))
print(modular_sqrt(19,4481))
print(modular_sqrt(191,1009))
/Classwork/MATH4176 - Cryptography 2/Shanks.py
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)