Let’s solve the discrete log problem 2x≡71(mod131) by the Baby Step-Giant Step method of Subsection 10.2.2. We take N=12 since N2>p−1=130 and we form two lists. The first is 2j(mod1)31 for 0≤j≤11:
for i in range(0,12): print i, mod(2,131)i0 11 22 43 84 165 326 647 1288 1259 11910 107 11 83
The second is 71⋅2−j(mod1)31 for 0≤j≤11:
for i in range(0,12): print i, mod(71*mod(2,131)(-12*i),131)0 711 172 1243 264 1285 866 1117 938 859 9610 13011 116
The number 128 is on both lists, so we see that 27≡71⋅2−12∗4(mod131). Therefore,