# Tag Info

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a ...
In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = ... 2 Diffie-Hellman operates in a cyclic group by definition: the elements$g, g^a, g^b, g^{ab}$are in the cyclic group generated by$g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway. In your example, you operate in the cyclic group$c\mathbf{Z}$, and as you were told in the comments, ... 1 Since attacker does not know$m$, he can't directly apply discrete logarithm methods. On the other hand, small message space allows to run discrete log algorithm on each possible$m$. There are subexponential algorithms for dlog, but I am not sure if they are directly applicable here. But the general BSGS algorithm will find$e$in$sqrt(e)\$ operations, so ...