gistfile1.py

"""
Compute discrete log modulo a prime p
In other words finds a x such that h=g^x in ℤp. 
Implements the meet in the middle attack
author: mjbecze <[email protected]>
"""

import gmpy2
from gmpy2 import mpz

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
g = mpz(11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
h = mpz(3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)

b = mpz(2 ** 20)
x = 0
table = {}

invert = gmpy2.invert(g, p)
t = invert
hi = h

#create a hash table
for x1 in range(0, b+1):
    n = hi % p
    table[n] = x1
    hi = h * t
    t = invert * t % p

print("searching the hash table")
gb = g ** b % p
xn = 1
for x0 in range(0, b+1):
    n = xn % p
    if table.has_key(n):
        x1 = table[n]
        x = x0 * b + x1
        #print the found result
        print(x)
        break
    else:
        xn = xn * gb % p