Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,s$). Assume that it is easy to solve the discrete log problem in the subgroup of order $p$.

Questions

  1. I know that if I have an upper bound on $n$, I can use Baby step-giant step to solve the discrete log in $G$. Does Pohlig-Hellman also work if you know the upper bound?

  2. Can I solve the discrete log problem in $G$ using the Pohlig-Hellman algorithm or any other algorithm that has square root complexity in the above group setting?

  3. Can one find $k$ using any of the discrete log solving algorithms?

My probable answers

  1. Assuming that Pohlig-Hellman only works if you precisely know the group order, then no I can't solve the discrete log problem in $G$ as I don't know $n$(or $k$ for that matter).

  2. Not sure what the answer is if I use baby step-giant step but I think you can not find $k$ using Pohlig-Hellman.

Need help in filling the gaps and verifying my answers.

  • 1
    I believe that the Pollard-Rho algorithm can be adjusted to work on a group of unknown order; it does increase the computation by a constant factor... – poncho Nov 17 at 23:05
up vote 2 down vote accepted

Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows:

  1. Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used.
  2. Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}$. Now, the orders of $g'$ and $h'$ divide $s$.
  3. Use baby-step giant-step algorithm to find discrete logarithm of $h'$ to the base $g'$. If a good upper bound on $s$ is not known, it is possible to run the algorithm multiple times with exponentially increasing upper bound.
  4. Similarly, use baby-step giant-step algorithm to find $s$, for example, by finding discrete logarithm of $(g')^{-1}$ to the base $g'$. If $g$ is not a generator, you may find a value $s'$ different than $s$ (but it will divide $s$). In this case, $g$ lies in a subgroup of size $p^ks'$, so you may just assume that this subgroup is the whole group.
  5. Then, use Pohlig–Hellman algorithm to find discrete logarithm of $h^s$ to the base $g^s$. Both elements are in the subgroup of size $p^k$.
  6. Use Chinese remainder theorem to find the logarithm of $h$ to the base $g$.

To find $k$, first use the above algorithm to find $s$. Then, if you have a generator $g$, find the smallest $k$ such that $g^{p^ks}=e$, where $e$ is a neutral element. If there is no known generator, it is possible to use multiple random elements instead to make the probability of finding the correct $k$ arbitrarily close to $1$. There is no deterministic algorithm that works with arbitrary groups when no generator is known, because it is possible that all known elements will lie in the subgroup of size $p^{k-1}s$, so it will be impossible to tell that the real size is not $p^{k-1}s$ but actually $p^ks$.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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