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 [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]: