Hashtable размером 2 ^ 24 выдает исключение из памяти, пытаясь решить дискретные журналы с помощью Shanks BSGS

Question

Я пытаюсь решить дискретный журнал 2 ^ x = r (mod m).где m, 2 ^ 47

Итак, я создал хеш-таблицу размером 2 ^ 24 и использовал ее для хранения целочисленного ключа и значения BigInteger.

Вот мой код:

using System;
    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;
            }
        }
    }

Также, если это имеет значение.Я запускаю это на Visual C # 2010 Express на 6-летнем ноутбуке с 1,5 ГБ ОЗУ и 32-разрядной Windows 7. Заранее спасибо.

Answer 1

Прежде всего, я думаю, вам нужно использовать значение temp в качестве ключа к вашим данным:

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

Что касается проблемы с памятью, .NET не позволяет никаким процессам использовать более 2 ГБ памяти, а позволяет даже меньше, если вам нужен непрерывный блок. Поскольку вы имеете дело с очень большими числами по мере продвижения, нехватка памяти неизбежна.

Одним из решений (предпочтительно, если вам нужен только конечный результат) было бы использование другого алгоритма ( Алгоритм Полларда ), который намного более экономно использует пространство и имеет аналогичное время выполнения.

Если вы действительно хотите протестировать алгоритм BSGS, вам, вероятно, понадобится хеш-таблица на основе диска. Я не знаю каких-либо реализаций для .NET, но вы можете найти несколько проектов C ++ и посмотреть, сможете ли вы их легко портировать (например, DBH ).

Если вы не можете найти такую ​​хеш-таблицу, более простым решением, чем портирование (ну, в зависимости от ваших навыков работы с БД), может быть использование реляционной базы данных, с которой вам удобно, используя схему, которая может допускать достаточно большие целые числа. Вы можете попробовать с SQLite, он будет становиться медленнее по мере роста, но я считаю, что скорость не так важна для вас. SQL Server с определенной индексацией может работать хорошо.

Answer 2

temp становится очень большим (до 16777216 бит).Таким образом, ваш хэшсет содержит 16 миллионов длинных BigIntegers.Может быть, вы хотите уменьшить временный мод m, но, конечно, это в конечном итоге станет 0, когда g = 2 и m является степенью 2. Так что не совсем понятно, что вы хотите сделать.