Introduction to Cryptography with Coding Theory, 3rd Edition

D.6 Computations for Chapter 10

Let’s solve the discrete log problem $2^x\equiv 71(\mathrm{m}\mathrm{o}\mathrm{d}131)$ by the Baby Step-Giant Step method of Subsection 10.2.2. We take $N=12$ since $N^2>p-1=130$ and we form two lists. The first is $2^j(\mathrm{m}\mathrm{o}\mathrm{d}1)31$ for $0\le j\le 11$:

for i in range(0,12): print i, mod(2,131)i

0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 125
9 119
10 107 
11 83

The second is $71\cdot 2^{-j}(\mathrm{m}\mathrm{o}\mathrm{d}1)31$ for $0\le j\le 11$:

for i in range(0,12): print i, mod(71*mod(2,131)(-12*i),131)

0 71
1 17
2 124 
3 26
4 128 
5 86
6 111 
7 93
8 85
9 96
10 130 
11 116

The number 128 is on both lists, so we see that $2^7\equiv 71\cdot 2^{-12\ast 4}(\mathrm{m}\mathrm{o}\mathrm{d}131)$. Therefore,

$$71\equiv 2^{7+4\ast 12}\equiv 2^{55}(\mathrm{m}\mathrm{o}\mathrm{d}131)\text{.}$$