Diffie-Hellman: Calculating the private key from the public key with Java I have the task to calculate the private key from the given public key and have the hint that the secret exponent lies in the range from $-2^{31} &lt; e &lt; 2^{31}$. 

To find the exponent I calculate a public key and compare it to the given key.
$$k_{pub} = 2^{e} \bmod {prime}$$ I start with $e = -2^{31}$ and then iterate my way up until I should find the $e$ where my calculated key equals the given public key. The problem is that it takes really long (about 20 days, if I calculated correctly). 
Is there a way to make it faster?

import java.math.BigInteger;


public class task {


        public static void main (String[] args) throws java.lang.Exception
        {

            BigInteger prime                = new BigInteger("FFF....FFF", 16);
            BigInteger BobPublicKey         = new BigInteger("b54.....da6", 16);

             BigInteger tmp = new BigInteger("0");

             BigInteger j = new BigInteger(new Integer(Integer.MIN_VALUE).toString());
             System.out.print("Starting to guess Bobs secret: \n" + j + "\n");

             while ( !(tmp.compareTo(BobPublicKey) == 0)){
                 tmp = BigInteger.valueOf(2).modPow(j, prime);
                 j = j.add(BigInteger.valueOf(1));  
                 System.out.print(j + "\n");
             }

             //correct for counting 1 too far in while loop after the actual e was found
             j = j.add(BigInteger.valueOf(-1));

             System.out.print("Bobs secret was: " + j + "\n");


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