Optimizing a c# program that creates 2 dictionaries and searches both for a matching value

I have 2 Dictionaries. I am trying to optimize this code to run as fast as possible.

This is for solving Shanks Baby Step Giant Step Algorithm

Algorithm:

Given b = a^x (mod p)
First choose n, such that n^2 >= p-1
Then create 2 lists:
    1. a^j (mod p) for 0  0)
    {
        BigInteger t = i / a, x = a;
        a = i % x;
        i = x;
        x = d;
        d = v - t * x;
        v = x;
    }
    v %= n;
    if (v  b = new Dictionary();
    Dictionary g = new Dictionary();
    temp = modInverse(two, mod);
    temp = BigInteger.ModPow(temp, n, mod);
    for (int j = 0; (BigInteger)j  d in g)
        {
            if (d.Value.Equals(tm))
            {
                Console.WriteLine("j={0}   B*t^j(mod m) = {1}",d.Key,d.Value);
                Console.WriteLine("a^"+i+" = "+tm);
            }
        }
        b.Add(i,tm);
    }
    Console.ReadKey();
    return 0;
}

There are some really obvious optimisations.

• Delete all the code relating to b. A dictionary you only insert into is a waste of time, memory, and programmer ability to understand what's going on.

• Use g as a dictionary. The way to do that is to change it from a Dictionary into a Dictionary. Then your foreach can be replaced with a simple TryGetValue.

-
Ditch the cast of j to BigInteger:

int n_int = ((int)Math.Sqrt(247457076132467-1))+1;
... 
n = (BigInteger)n_int

And compare j to n_int. If it doesn't fit in an int, j shouldn't be an int either.

-
Exploit basic arithmetic properties in loops. E.g. rather than

tm = BigInteger.ModPow(2, i, mod);

you should have

tm = 1,
...
for (int i = 0; i < n_int; i++)
{
    ...
    tm = (tm * 2) % mod;
}

PS In fact, if you'd looked at the Wikipedia page on the algorithm you'd have found pseudocode which handles all this already.

StackExchange Code Review Q#4932, answer score: 2