-
Notifications
You must be signed in to change notification settings - Fork 0
/
discretelogmodulo.py
27 lines (20 loc) · 907 Bytes
/
discretelogmodulo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
p=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
g=11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568
h=3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333
B = 2 ** 20
from numbthy import powmod, invmod
table = {}
def build_table():
for x1 in xrange(0, B + 1):
val = (h * invmod(powmod(g, x1, p), p))%p
table[val] = x1
def find_x():
for x0 in xrange(0, B + 1):
val = powmod(g, x0*B, p)
if val in table:
x1 = table[val]
break
print "x = " + str(x0 * B + x1)
if __name__ == "__main__":
build_table()
find_x()