Understanding Baby-Step Giant-Step Algorithm and discrete logarithm

Studying the Baby-Step/Giant-Step Algorithm, I have some questions:

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

2. (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$$?
(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?

• can you explain more detail about 2(b) ? I read the Polih-Hellman, is it because subgroup of prime order q is hard to compute , thus it cannot apply the Chinese remainder theorem to recover the final solution x ?Is there no any efficient algorithm to solve DLP in group of prime order? Apr 2, 2019 at 14:13

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

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

1. (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).

• Thank you for your answer!But I still confuse that why discrete logarithm computation is hard in group of prime order ? is it because from which we cannot use efficient algorithm like Rho algorithms? Apr 3, 2019 at 11:19
• @Laura: why the dlog problem is hard for some groups? Well, no one really knows that; all we know is that there are groups where the best known algorithm is infeasible. Now, if we're working on a group with a composite order of known factorization, we can solve it by solving the dlog group in the various prime subgroups; hence it is considerably easier than a group of prime order of about the same size; hence we prefer groups of prime order. BTW: the (Pollard) Rho algorithm is a generic one; it takes a constant factor more computation than Big Step/Little Step, but takes far less memory... Apr 3, 2019 at 11:47