模幂C ++的问题 [英] Issue with Modular Exponentiation C++

问题描述

我正在尝试对大值(最多64位)执行模幂运算，并为此编写了以下函数:

I'm trying to perform Modular Exponentiation for large values (upto 64-bits) and I wrote this function for it:

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位范围内，结果也会出错.

This works good with small numbers (8 digits or less) but for large numbers, even though they're in the 64 bit range, the result comes out wrong.

此外，当mod的值超过4294967296(最大32位值)时，结果仅为零.我怀疑pow函数可能在此问题中起作用，但我不能确定.

Additionally, when the value of mod exceeds 4294967296 (Max 32 bit value), the result just comes out as zero. I suspect the pow function perhaps has a role to play in this issue but I can't figure it out for sure.

任何建议将不胜感激.

推荐答案

首先，一些一般性建议:

First of all, some general advice:

• 最好不要在使用整数时使用字符串，因为使用字符串的操作要慢得多，并且可能会成为性能瓶颈.还不清楚当涉及到字符串时实际上在做什么.
• 您不应将 std :: pow 与整数一起使用，因为它对浮点数进行运算并且会失去精度.

• It's better not to use strings when working with integers, as operations with strings are much slower and might become a bottleneck for performance. It's also less clear what is actually being done when strings are involved.
• You shouldn't use std::pow with integers, because it operates on floating-point numbers and loses precision.

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

For the main question, as a workaround, you can use this O(log^2(n)) solution, which should work for arguments up to 63 bits (since it only ever uses addition and multiplication by 2). Note how all that string magic is unnecessary if you just iterate over the bits in small-to-large order:

#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 替换为普通乘法)

Also, in gcc a (non-standard) __uint128_t is available for some targets. (which can be used to replace modular_mul with normal multiplication)

这篇关于模幂C ++的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！