Skip to content

Instantly share code, notes, and snippets.

@Ivoz

Ivoz/dlp.py

Last active Dec 25, 2017
Embed
What would you like to do?
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

This comment has been minimized.

Copy link

@MejziniSead MejziniSead commented Dec 25, 2017

can u tell me how did u implement this pow function

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment