I actually have two questions related to how hard the discrete logarithm problem is. In the two questions, I will use the following notation for the DLP:
- $g^x\equiv h \pmod{p}$, where $p$ is a prime, and $g$ is of order $n$
The first question: I'm reading a book about cryptography, in which the author, trying to demonstrate how hard it is to solve the DLP, states "we might try choosing random values of $x$, compute $g^x$, and
check if $g^x = h$. Using the fast exponentiation method,
it takes a small multiple of $\log_2(x)$ modular multiplications to compute $g^x$". So, when I tried to find bounds for this "small multiple" of $\log_2(x)$ mathematically, I found that it can be at most $2$ and can be as low as $1$. Is this what he meant or is there something that I am missing? NOTE: in the book, he uses the fast powering algorithm to do exponentiation.
The second question: In the same book, the author continues by saying "If $n$ and $x$ are $k$-bit numbers, that is, they are each approximately $2^k$, then this
trial-and-error approach requires about $k·2^k$ multiplications". If the author means that this is the number of multiplication that is needed to brute force the DLP over all exponents $1\le x\le n$, then it won't be true because for example small exponets will take much less multiplications than bigger exponents, So obviously, the number of multiplications will be less than that. But, I don't think he meant that because he says that $x $ and n are $k$-bit numbers. Does this mean that $x$ is fixed, and if it is fixed how is this different from the situations I described in the first question.