Hashtable of size 2^24 throws out of memory exception, trying to solve discrete logs with Shanks BSGS

I am trying to solve a discrete log 2^x = r (mod m). where m, 2^47

So i created a hashtable of size 2^24 and using it to store an integer key and a BigInteger value.

Here is my code:

using Sys开发者_JS百科tem;
    using System.Collections.Generic;
    using System.Collections;
    using System.Linq;
    using System.Text;
    using System.Numerics;

    namespace Shanks_BSGS_Algorithm
    {
        class Program
        {
            static int Main()
            {
                BigInteger g = 2,temp = 2,n = (Math.Sqrt(281474976710656));
                Hashtable b = new Hashtable(n);
                int i=0;
                b.Add(0, 1);
                i++;
                for (i = 1; (BigInteger)i < n ; i++)
                {
                    temp *= g;
                    b.Add(i,temp);
                }

                return 0;
            }
        }
    }

Also if it makes a difference. I am running this on Visual C# 2010 Express on a 6yr old laptop with 1.5 gb RAM and 32-bit Windows 7. Thanks in advance.

temp becomes very big (up to 16777216 bit). So your hashset contains 16 million very long BigIntegers. Maybe you want to reduce temp mod m, but of course this will eventually become 0 when g = 2 and m is a power of 2. So it's not really clear what you want to do.

First of all, I think you need to use the temp value as the key to your data:

// this makes more sense, otherwise you
// could simply have an array of BigIntegers
b.Add(temp,i);

Regarding the memory issue, .NET doesn't allow any process to use more than 2Gb of memory, and allows even less if you need a contiguous block. Since you are dealing with very large numbers as you go along, running out of memory is inevitable.

One solution (preferred, if you only need the end result) would be to use a different algorithm (Pollard's rho algorithm), which is much more space efficient, and has a similar running time.

If you really want to test the BSGS algorithm, you will probably need to go for a disk-based hashtable. I am not aware of any implementations for .NET, but you might find several C++ projects around and see if you can port them easily (DBH, for instance).

If you cannot find such a hashtable, a simpler solution than porting (well, depending on your DB skills) might be to use a relational database you are comfortable with, using a schema that can allow sufficiently large integers. You could try with SQLite, it will get slower as it grows, but I believe speed is not that important to you. SQL Server with some proper indexing might work well.