SAGE implementation of discrete logarithm in subgroup of group of units

Question

This is a question related to this one. Briefly, in ElGammal cryptosystem with underlying group the group of units modulo a prime number p I'm told to find a subgroup of index 2 to solve discrete logarithm problem in order to break the system.

Clearly, as the group of units modulo a prime number is cyclic, if x is a generator then x^2 generates a subgroup of index 2. Now, what is a good way of solving discrete logarithm problem on sage? How would I use the result of solving discrete logarithm problem in this subgroup to solve it in the whole group?

Answer 1

Sage knows how to compute discrete logarithms in finite fields:

sage: K = GF(19)
sage: z = K.primitive_element()
sage: a = K.random_element()
sage: b = a.log(z)
sage: z^b == a
True

you can use this functionality to solve the discrete logarithm in the subgroup of index 2

sage: x = z^2
sage: a = K.random_element()^2
sage: a.log(x)
6

This is only a toy example, but note that this is not more efficient than solving the discrete logarithm in the full group ₁₉*.

It is true that the efficiency of generic algorithms (e.g., Baby step-Giant step, Pollard rho, ...) is directly related to the size of the subgroup; however algorithms used to solve discrete logarithms in finite fields (number field sieve, function field sieve) are mostly insensitive to the size of the multiplicative subgroup, and are in general much more efficient than generic algorithms.