基于Diffie-Hellman循环分解N求p/q：BigInteger.Pow性能优化求助

问题核心 #

实现了基于Diffie-Hellman循环算法的大整数N素因子分解程序，小素数（如p=11、q=7）场景下运行正常，但使用大素数（如p=13147、q=13229）时，BigInteger.Pow(g, r2)的执行速度远慢于GetCycles方法（后者耗时约9100ms，前者几乎无法完成），需要优化A = BigInteger.Pow(g, r2) + 1和B = BigInteger.Pow(g, r2) - 1的计算方式。

优化方案 #

1. 用模幂运算替代普通幂运算

直接计算g^r2会生成远超内存承载能力的超大整数，而我们最终只需要用A/B和N求最大公约数。根据模运算性质：

gcd(g^r2 ± 1, N) = gcd( (g^r2 mod N) ± 1, N )

因此只需计算g^r2 mod N，再加减1即可，全程数值大小控制在N范围内。.NET自带的BigInteger.ModPow方法采用快速幂算法，且全程取模，效率远高于BigInteger.Pow。

2. 复用GetCycles的中间计算结果

GetCycles过程中已经逐步计算了g^1 mod N、g^2 mod N…直到g^cycles mod N，而r2 = cycles / 2，可以在遍历过程中记录g^r2 mod N的值，避免后续重复计算，进一步节省时间。

修改后的代码 #

using System.Diagnostics;
using System.Numerics;

BigInteger g = 8; // 生成元
BigInteger p = 13147; // 大素数
BigInteger q = 13229; // 大素数
var N = p * q; // 待分解的大整数

bool GetCycles(out int cycleCount, out BigInteger gToR2ModN)
{
    BigInteger m = 1;
    cycleCount = 1;
    var baseValue = g;

    gToR2ModN = 1;

    while (baseValue != 1)
    {
        baseValue = baseValue * g % N;
        m = m * g % N;
        m = (m + 1) % N;
        cycleCount++;

        if (m == 1)
        {
            break;
        }
    }

    // 直接用ModPow计算g^r2 mod N，避免遍历维护中间值出错
    gToR2ModN = BigInteger.ModPow(g, cycleCount / 2, N);

    if (cycleCount % 2 != 0)
    {
        Console.WriteLine($"{cycleCount} 必须为偶数");
        return true;
    }

    return false;
}

var cycles = -1;
BigInteger gR2ModN = 1;
var exit = SW("Cycles", () => GetCycles(out cycles, out gR2ModN));

if (exit) return;

Console.WriteLine("找到循环长度: " + cycles);

// 用模后的值计算A和B
var A = gR2ModN + 1;
var B = gR2ModN - 1;

// 求最大公约数（用原生Gcd方法替代手动实现，更高效简洁）
BigInteger GetPrime(BigInteger f)
{
    return BigInteger.Gcd(f, N);
}

var pSolution = SW("A", () => GetPrime(A));
var qSolution = SW("B", () => GetPrime(B));

Console.WriteLine($"p={pSolution}\nq={qSolution}");

T SW<T>(string key, Func<T> action)
{
    var sw = Stopwatch.StartNew();
    var t = action();
    sw.Stop();

    Console.WriteLine($"[{key}] 耗时 {sw.ElapsedMilliseconds} ms!");
    return t;
}

关键修改说明 #

• 替换BigInteger.Pow为BigInteger.ModPow，避免生成超大整数，计算效率提升几个数量级。
• 用BigInteger.Gcd简化原来的手动GCD实现，代码更简洁且性能更优。
• 在GetCycles结束后直接调用ModPow计算目标模幂，逻辑清晰且避免遍历维护中间值的潜在错误。

内容的提问来源于stack exchange，提问作者z3nth10n