pohlig.sagews

factors = (p-1).factor()
remainders = []
bases = []
for factor in factors:
    p_i = factor[0]**factor[1]
    LHS = pow(e, int((p-1)/p_i), p)
    RHBase = pow(g, int((p-1)/p_i), p)
    if RHBase == 1:
        print "multiple"
    for r_i in range(p_i):
        if pow(RHBase, r_i, p) == LHS:
            remainders.append(r_i)
            bases.append(p_i)
            break
x_guess = crt(remainders, bases)
print x_guess, pow(g, x_guess, p) == e