大小为2^24的Hashtable抛出内存不足异常，尝试用Shanks BSGS解决离散日志

Question

我正在尝试求解离散 log 2^x = r (mod 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;
            }
        }
    }

如果它有所作为的话。我正在一台拥有 1.5 GB RAM 和 32 位 Windows 7 的 6 年旧笔记本电脑上的 Visual C# 2010 Express 上运行此程序。 提前致谢。

Answer 1

temp 变得非常大（高达 16777216 位）。所以你的哈希集包含 1600 万个非常长的 BigIntegers。也许你想减少 temp mod m，但是当 g = 2 并且 m 是 2 的幂时，当然这最终会变成 0。所以目前还不清楚你想要做什么。

Answer 2

首先，我认为您需要使用 temp 值作为数据的关键：

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

关于内存问题，.NET 不允许任何进程使用超过 2Gb 的内存，并且允许如果您需要连续的块，则更少。由于您在处理过程中要处理非常大的数字，因此内存不足是不可避免的。

一种解决方案（如果您只需要最终结果，则首选）是使用不同的算法（Pollard's rho算法），其空间效率更高，并且具有相似的运行时间。

如果您确实想测试 BSGS 算法，您可能需要使用基于磁盘的哈希表。我不知道 .NET 的任何实现，但您可能会发现几个 C++ 项目，看看是否可以轻松移植它们 (例如，胸径）。

如果您找不到这样的哈希表，比移植更简单的解决方案（好吧，取决于您的数据库技能）可能是使用您熟悉的关系数据库，使用可以允许足够大的整数的模式。您可以尝试使用 SQLite，随着它的增长，它会变慢，但我相信速度对您来说并不那么重要。具有适当索引的 SQL Server 可能会工作得很好。