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