Diffie-Hellman: Calculating the private key from the public key with Java
There are several obvious ways to optimize the search.

The easiest approach would be to take advantage of the identity $g^e \cdot g = g^{e+1}$.  That is, if we have already computed $g^e$, and verified that it is not the value we're looking for, then to step to $g^{e+1}$, we don't compute $g^{e+1}$ from scratch; instead, we take the $g^e$ value we have, and multiply it by $g$ (modulo $p$), and that's the next value to check.

And, because you have $g=2$, this can be done as easily as adding $g^e$ to itself, and then subtracting $p$ if needed.

A more difficult (but ultimately more rewarding) optimization is to implement the 'bigstep/littlestep' algorithm.  This takes the equation $g^x = g^{ak+b}$ (for $k = 2^{16}$ and $-2^{-15} \le a &lt; 2^{15}$, $0 \le b &lt; 2^{16}$), and rewrites it as $g^x g^{-ak} = g^b$; we then create a list of the $2^{16}$ possible $g^x g^{-ak}$ values, and the $2^{16}$ possible $g^b$ values, and search for a match (which can be done in $O(n \log n)$ time using a fast sorting algorithm); this match gives us the $a, b$ values, which immediately gives us $x$.  This is obviously a lot more work; however doing this will allow you to find a match by doing around $2^{17}$ modular multiplications; this is a large gain over the previous optimization.