模幂 C++ 问题

Question

我正在尝试对大值（最多 64 位）执行模幂运算，我为此编写了这个函数：

uint64_t modularExp(uint64_t num, uint64_t exp, uint64_t mod) 
{
    string expBits = bitset<64>(exp).to_string();   
    expBits = expBits.substr(expBits.find("1")+1);
    
    string operations = "";
    
    uint64_t result = num;
    for (int i = 0; i < expBits.length(); ++i)
    {
        result = (uint64_t)pow(result, 2) % mod;
        if (expBits[i] == '1')
            result = (result * num) % mod;
    }   
            
    return result;  
}

这适用于小数字（8 位或更少），但对于大数字，即使它们在 64 位范围内，结果也会出错。

此外，当mod的值超过4294967296（最大32位值）时，结果只显示为零。我怀疑 pow 函数可能在这个问题中发挥了作用，但我不确定。

如有任何建议，我们将不胜感激。

Answer 1

首先，一些一般性建议：

在处理整数时最好不要使用字符串，因为字符串操作 慢很多 并且可能成为性能瓶颈。当涉及字符串时，实际执行的操作也不太清楚。
您不应将 std::pow 与整数一起使用，因为它对 floating-point 数字进行运算并失去精度。

对于主要问题，作为解决方法，您可以使用此 O(log^2(n)) 解决方案，它应该适用于最多 63 位的参数（因为它只使用加法和乘以 2）。请注意，如果您只是按 small-to-large 顺序遍历位：

，那么所有的字符串魔法都是不必要的

#include <cstdint>

uint64_t modular_mul(uint64_t a, uint64_t b, uint64_t mod) {
    uint64_t result = 0;
    for (uint64_t current_term = a; b; b >>= 1) {
        if (b & 1) {
            result = (result + current_term) % mod;
        }
        current_term = 2 * current_term % mod;
    }
    return result;
}

uint64_t modular_pow(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    for (uint64_t current_factor = base; exp; exp >>= 1) {
        if (exp & 1) {
            result = modular_mul(result, current_factor, mod);
        }
        current_factor = modular_mul(current_factor, current_factor, mod);
    }
    return result;
}

此外，在 gcc 中，a (non-standard) __uint128_t 可用于某些目标。（可以用普通乘法代替modular_mul）

模幂 C++ 问题

Issue with Modular Exponentiation C++

c++

base64

modular-arithmetic