Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.