Question

Let p 37, and let g-5, which is a primitive root. Let h 31. We will use the baby-step giant step method with N 6 (which satisfies N p-1). (a) Compute g,g,g.g( p) (b) Compute hgo, hg , hg 1,hg18, hg24, hg30 (mod p). (c) Determine Lg(h) by spotting the match between these two lists.

Answer 1

a)

a) g^0 Identicalto 1 (mod 37) g^1 Identicalto 5 (mod 37) g^2 Identicalto 25 (mod 37) g^3 Identicalto 14 (mod 37) g^4 Identicalto 33 (mod 37) g^5 Identicalto 17 (mod 37) b) g^6 Identicalto 11 (mod 37) rightwardsdoublearrow g^-6 Identicalto 27 (mod 37) So hg^-0 Identicalto 31 (mod 37) hg^-6 Identicalto 23 (mod 37) hg^-12 Identicalto 29 (mod 37) hg^-18 Identicalto 6 (mod 37) hg^-24 Identicalto 14 (mod 37) hg^-30 Identicalto 8 (mod 37) c) Comparing the two tables, we have: 14 Identicalto g^3 Identicalto hg^-24 (mod 37) So that h Identicalto g^27 (mod 37) rightwardsdoublearrow L_g (h) = 27

b) $g^6\equiv 11\pmod{37}\Rightarrow g^{-6}\equiv 27\pmod{37}$

So

$\newline hg^{-0}\equiv 31\pmod{37}\newline hg^{-6}\equiv 23\pmod{37}\newline h g^{-12}\equiv 29\pmod{37}\newline hg^{-18}\equiv 6\pmod{37}\newline hg^{-24}\equiv 14\pmod{37}\newline h g^{-30}\equiv 8\pmod{37}$

c) Comparing the two tables, we have:

$14\equiv g^3\equiv hg^{-24}\pmod{37}$

So that $h\equiv g^{27}\pmod{37}\Rightarrow L_g(h)={\color{Red} 27}$