c++ - 模幂 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使用整数，因为它对浮点数进行运算并失去精度。

对于主要问题，作为解决方法，您可以使用 O(log^2(n))解决方案，它应该适用于最多 63 位的参数(因为它只使用 2 的加法和乘法)。请注意，如果您只是以从小到大的顺序迭代这些位，那么所有这些字符串魔术都是不必要的:

#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 中，一个(非标准) __uint128_t可用于某些目标。 (可以用普通乘法代替 modular_mul)