Vrftsjtryk

Suppose I have a group $G$ of unknown order $n$ where $n=p^kcdot s$, $gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,sge1$. (Known - $p$ and $pmid 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

2. 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).




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

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'=lfloorlog_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$.