- In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?
The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term comes from the time taken iterating through the various $i$ values.
It should be easy to see that that time is minimized if $m \approx \sqrt{p}$
- (a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?
If $p$ is quite large, then $\sqrt{p}$ is also large (even if it isn't as large as $p$); for example, if we want $\sqrt{p} \ge 2^{128}$ so that the number of steps that Big Step-Little Step takes is infeasibly large, we just take $p \ge 2^{256}$.
Just one note: if we're working in the group $\mathbb{Z}^*_p$, then there are other attacks against the Discrete Log problem other than the generic Big Step-Little Step (and Rho) algorithms; hence we generally need a much larger $p$
- (b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?
If we are working in the group $\mathbb{Z}^*_p$ (that is, the multiplicative group modulo $p$), well, that group has a size $p-1$; any prime subgroup will have a size $q$ which is a divisor of $p-1$. One way (but not the only way) to make sure that there is a good $q$ is to make $p$ a "safe prime", that is, a prime such that $q = (p-1)/2$ is also prime.
On the other hand, that applies only to the group $\mathbb{Z}^*_p$; if you go to (say) Elliptic Curve groups, there is no corresponding reason to prefer safe primes (either for the characteristic or the group size).
