Introduction to Cryptography with Coding Theory, 3rd Edition

B.8 Examples for Chapter 10

Example 35

Let’s solve the discrete log problem $2^x\equiv 71(\text{mod}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(\text{mod}131)$ for $0\le j\le 11\text{:}$

>for j from 0 while j <= 11 do; (j, 2&ĵ mod 131); end do;

                            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}(\text{mod}1)31$ for $0\le j\le 11\text{:}$

> for j from 0 while j <= 11 do; (j, 71*2&\^\: (-12*j) mod 131); end do;

                             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}(\text{mod}131)\text{.}$ Therefore,

$$71\equiv 2^{7+4\ast 12}\equiv 2^{55}(\text{mod}131)\text{.}$$