# B.8 Examples for Chapter 10

# Example 35

Let’s solve the discrete log problem ${2}^{x}\equiv 71\text{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}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{\hspace{0.17em}}(\text{mod}\text{\hspace{0.17em}}131)\text{.}$ Therefore,

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