ModPow 计算速度不够快 c#

Question

您好，我正在尝试尽快进行 ModPow 计算，计算结果为 P^e%n。测试数据是 888999000^202404606%237291793913，我知道 BigInteger.ModPow(P, e, n) 但是我不应该使用这个函数所以我写了以下功能比较慢，我真的需要加快这个过程。 （我敢肯定，也许如果我将计算数字分成两半并将其变成两个单独的计算，它有望加快该过程），无论如何，这就是我到目前为止所写的内容。

private static BigInteger ModPow(BigInteger baseNum, BigInteger exponent, BigInteger modulus)
{
    BigInteger c;
    if (modulus == 1)
        return 0;
    c = 1;
    for (BigInteger e_prime = 1; e_prime <= exponent; e_prime++)
    {
        c = (c * baseNum) % modulus;
    }
    return c;
}

Answer 1

您需要的可能是 Exponentiation by squaring，它也适用于模功率。代码应该是这样的：

private static BigInteger ModPow(BigInteger baseNum, BigInteger exponent, BigInteger modulus)
{
    BigInteger pow = 1;
    if (modulus == 1)
        return 0;
    BigInteger curPow = baseNum % modulus;
    BigInteger res = 1;
    while(exponent > 0){
        if (exponent % 2 == 1)
            res = (res * curPow) % modulus;
        exponent = exponent / 2;
        curPow = (curPow * curPow) % modulus;  // square curPow
    }
    return res;
}

此方法的性能是 O(log(exponent)) 而不是 O(exponent) 对于您的代码而言，就乘法和模运算的数量而言（对于 BigInteger 可能不是 O(1) 但细节取决于实现）。还要注意，上面的代码不应该用于任何现实世界的 crypto-related 实现，因为它引入了漏洞（性能取决于 exponent 的实际值，特别是那里有多少 1 位（有关详细信息，请参阅 Timing attack）。

Answer 2

好吧，试试这个

private static BigInteger ModPow(BigInteger baseNum, BigInteger exponent, BigInteger modulus)
{
       BigInteger B, D;
       B = baseNum;

       B %= modulus;
       D = 1;
       if ((exponent & 1) == 1)
       {
           D = B;
       }

        while (exponent > 1)
        {
             exponent >>= 1;
             B = (B * B) % modulus;
             if ((exponent & 1) == 1)
             {
                 D = (D * B) % modulus;
             }
         }
         return (BigInteger)D;
}