20 lines
392 B
Python
20 lines
392 B
Python
|
def extended_euclidean(a, b):
|
||
|
|
if a == 0:
|
||
|
|
return b, 0, 1
|
||
|
|
else:
|
||
|
|
g, x, y = extended_euclidean(b % a, a)
|
||
|
|
return g, y - (b // a) * x, x
|
||
|
|
|
||
|
|
def mod_inverse(e, phi):
|
||
|
|
g, x, _ = extended_euclidean(e, phi)
|
||
|
|
if g != 1:
|
||
|
|
raise Exception('modular inverse does not exist')
|
||
|
|
else:
|
||
|
|
return x % phi
|
||
|
|
|
||
|
|
e = 13
|
||
|
|
phi = 1362240
|
||
|
|
|
||
|
|
d = mod_inverse(e, phi)
|
||
|
|
print(d)
|