大小为2^24的哈希表抛出内存异常，试图用Shanks BSGS解决离散日志

本文关键字：Shanks BSGS 解决 日志 异常 小为 哈希表 内存 | 更新日期: 2023-09-27 18:09:00

我试图解决一个离散对数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;
            }
        }
    }

如果有影响的话。我在一台6年的旧笔记本电脑上运行Visual c# 2010 Express，内存为1.5 gb, Windows 7为32位。

大小为2^24的哈希表抛出内存异常，试图用Shanks BSGS解决离散日志

temp变得非常大(高达16777216位)。你的哈希集包含1600万个非常长的biginteger。也许你想降低温度对m取模，但当然，当g = 2 m是2的幂时，它最终会变成0。所以你想做什么就不太清楚了

首先，我认为您需要使用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++项目，看看你是否可以很容易地移植它们(例如DBH)。

如果您找不到这样的散列表，那么比移植(取决于您的DB技能)更简单的解决方案可能是使用您熟悉的关系数据库，使用允许足够大整数的模式。您可以尝试SQLite，它将变慢，因为它的增长，但我相信速度不是那么重要。SQL Server有一些适当的索引可能会工作得很好

相关文章：