import gmpy2
from Crypto.Hash import MD4

p = gmpy2.mpz('13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171')
h = gmpy2.mpz('3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333')
g = gmpy2.mpz('11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568')

B = 2**20

#buidling the table
tbl = {}
x1 = 0
x0 = 0

for i in range(0, B):
	tmp = gmpy2.powmod(g, i, p)	#get g^x1
	tmp = gmpy2.invert(tmp, p)	#get (g^x1)^-1
	tmp = gmpy2.t_mod(gmpy2.mul(h, tmp), p)
	
	hash = MD4.new(gmpy2.digits(tmp))
	tbl[hash.hexdigest()] = i
	
#start bruteforcing
for i in range(0, B):
	tmp = gmpy2.powmod(g, gmpy2.mul(B, i), p)
	hash = MD4.new(gmpy2.digits(tmp))
	
	if hash.hexdigest() in tbl:
		x1 = tbl[hash.hexdigest()]
		x0 = i
		break
		
res = (x0*B) + x1
print(res)
print(x0)
print(x1)
	
	

