w5.py

import gmpy2
from gmpy2 import mpz

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
g = mpz(11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
h = mpz(3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)
B = 2**20
gi = gmpy2.invert(g, p)


def gb_mod_p():
    result = 1
    for i in xrange(B):
        result = gmpy2.f_mod(result*g, p)
    return result


def build_dict():
    dict = {h: 0}
    key = h
    val = 0  # x1
    while val < B:
        val += 1
        key = gmpy2.f_mod(key*gi, p)
        dict[key] = val
    return dict


def find():
    dict = build_dict()
    gb = gb_mod_p()
    x0 = 0
    rhs = 1
    keys = set(dict.keys())
    while x0 < B:
        if rhs in keys:
            return B*x0+dict[rhs]
        x0 += 1
        rhs = gmpy2.f_mod(rhs*gb, p)