{{ message }}

Instantly share code, notes, and snippets.

# Ivoz/dlp.py

Last active Dec 25, 2017
Naive way to solve the Discrete Logarithm Problem
 #!/usr/bin/env python from __future__ import print_function def find_discrete_log(h, g, p): H = {} print('Generating table...') for x1 in range(0, B): gx1inv = mod_mul_inv(pow(g, x1, p), p) H[(h * gx1inv) % p] = x1 x1 = -1 x0 = -1 print('Finding x0...') for x in range(0, B): gbx = pow(pow(g, B, p), x, p) if gbx in H: x1 = H[gbx] x0 = x break if x1 > 0: return x0 * B + x1 else: raise Exception('Could not find discrete log') def mod_mul_inv(e, m): """ Modular Multiplicative Inverse. Returns x such that: (x*e) mod m == 1 """ x1, y1, x2, y2 = 1, 0, 0, 1 a, b = e, m while b > 0: q, r = divmod(a, b) xn, yn = x1 - q * x2, y1 - q * y2 a, b, x1, y1, x2, y2 = b, r, x2, y2, xn, yn return x1 % m p = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171 # noqa g = 11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568 # noqa h = 3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333 # noqa B = 2**20 # p = 2283959089817 # g = 1327839429874 # h = 402451193989 # B = 2**10 if __name__ == '__main__': print("prime (p):", p) print("base (g):", g) print("result (h):", h) print("finding x, such that g^x % p = h") x = find_discrete_log(h, g, p) assert(pow(g, x, p) == h) print("power (x):", x)

### MejziniSead commented Dec 25, 2017

 can u tell me how did u implement this pow function