17.2.5. Difficult Computation in Certain Cyclic Groups

Try these first

1. 1.

   What is the discrete logarithm of 1 to any base g in a cyclic group?

   Hint

   Think about the exponent needed to get the identity element.

2. 2.

   Is it possible for a cyclic group to have no generators?

   Hint

   Recall the definition of cyclic groups.

3. 3.

   What is the discrete logarithm of 1 for any base g?

   • True
   • False

   Hint

   Recall the fundamental property of logarithms.

4. 4.

   In the group Z_5, if g=2 and y=4, what is the discrete log?

   • 1
   • 2
   • 3
   • 4

   Hint

   Calculate powers of g modulo 5.

5. 5.

   In a large cyclic group Z_{23} where g=5, compute the discrete log of y=17 using brute force and provide a step-by-step explanation.

   Hint

   Keep calculating powers until matching y=17.

6. 6.

   Explain why an efficient algorithm for computing discrete logarithm in Z*_p (where p is prime) is currently conjectured to exist or not.

   Hint

   Focus on patterns in behavior.