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?

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.

• 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... Nov 17, 2018 at 23:05

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$$.