B.8 Examples for Chapter 10 – Introduction to Cryptography with Coding Theory, 3rd Edition

B.8 Examples for Chapter 10

Example 35

Let’s solve the discrete log problem 2x71(mod131) by the Baby Step-Giant Step method of Subsection 10.2.2. We take N=12 since N2>p1=130 and we form two lists. The first is 2j(mod131) for 0j11:

>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 712j(mod1)31 for 0j11:

> 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 27712124(mod131). Therefore,

7127+412255(mod131).