# A problem about the discrete logarithm

suppose there are a multiplicative cyclic group $F_p^*(p \;is\;big\; prime)$, and $G=\langle g \rangle(g \;is\; a\; generator)$ is a subgroup of it and $G$'s order is $q(q\;is\;big\;prime \;and \;q|p-1)$.

Now choose a number $x\in Z_q$ at your own way,that is to say you can set $x$ to the value of whatever you like, only if $x\in G$.Then, denote $X=g^x$.

Next there are a $b \in Z_q$ which is unknown. Denote $U=X^b$,which is known. And the discrete logarithm problem on $G$ is hard. All the computations are under $\pmod{p}$

My question is ：are there some ways to recover $b$ ? can Quadratic residue solve this？ Or maybe we can map $U$ to a space $\mathfrak{A}$ on which the the discrete logarithm problem is easy to solve, then inverse to the original space. I just have these thought about this question and i'm not sure if it is feasible. who can help me? thanks a lot

-
You seem to be asking whether a problem which is generally thought to be hard is really easy, so I am not sure what sort of answer you would expect. There has been a huge amount of research on discrete log algorithms. –  Derek Holt Sep 18 '13 at 9:27

Yes, there are several ways to recover $b$. The most known methods are algorithms which have names, e.g., Baby-step giant-step algorithm, Pollard's rho algorithm for logarithms, Pollard's kangaroo algorithm, Pohlig–Hellman algorithm, Index calculus algorithm, Number field sieve and Function field sieve. From the viewpoint of complexity, none of them runs in polynomial time (in the number of digits in the size of the group). This is why the discrete logarithm problem is considered to be hard. It is an open problem whether the discrete logarithm can be computed in polynomial time on a classical computer. Your "map" from $U$ to $\mathfrak{A}$ would immediately solve this.
maybe we could use some tricks of choosing some special $x$ that can reveal some information of $b$. –  Nax Sep 18 '13 at 14:53