Jupyter QtConsole 4.4.3
Python 3.7.1 (default, Dec 10 2018, 22:54:23) [MSC v.1915 64 bit (AMD64)]
Type 'copyright', 'credits' or 'license' for more information
IPython 7.2.0 -- An enhanced Interactive Python. Type '?' for help.
In [1]: def modinv(a,m):
...: d0, u0 = m, 0
...: d1, u1 = a, 1
...: while d1 != 0:
...: q = d0 // d1
...: d0,u0, d1,u1 = d1,u1, d0-q*d1,u0-q*u1
...: return u0%m
...:
In [2]: g = 7
In [3]: h = 183
In [4]: p = 599
In [5]: pow(7,13*23,p)
Out[5]: 598
In [6]: pow(183,13*23,p)
Out[6]: 598
In [7]: 598 * 598 % p
Out[7]: 1
In [8]: # 598 has order 2
In [9]: pow(g,2*23,p)
Out[9]: 212
In [10]: pow(h,2*23,p)
Out[10]: 536
In [10]:
In [11]: pow(g,2*13,p)
Out[11]: 103
In [12]: pow(h,2*13,p)
Out[12]: 39
In [13]: # will solve both DLP's by guess and check
In [14]: for e in range(13):
...: print(e, pow(212,e,p))
...:
0 1
1 212
2 19
3 434
4 361
5 459
6 270
7 335
8 338
9 375
10 432
11 536
12 421
In [14]:
In [14]:
In [15]: for e in range(23):
...: print(e, pow(103,e,p))
...:
0 1
1 103
2 426
3 151
4 578
5 233
6 39
7 423
8 441
9 498
10 379
11 102
12 323
13 324
14 427
15 254
16 405
17 384
18 18
19 57
20 480
21 322
22 221
In [16]: modinv(2,13)
Out[16]: 7
In [17]: modinv(2,13) * 10 % 13
Out[17]: 5
In [18]: modinv(26,23) * (6 - 11) % 23
Out[18]: 6
In [19]: 11 + 26 * 6
Out[19]: 167
In [20]: pow(7,167,p)
Out[20]: 183
In [21]: