时间戳

首页 > 解决方案 > 为什么在数字大于 48 位的情况下函数会失败？

c++ - 为什么在数字大于 48 位的情况下函数会失败？

问题描述

我试图找到

(a^b) % 模式

其中 b 和 mod 最大为 10^9，而 l 可能非常大，我已经使用这种关系成功测试了多达 48 位数字

(a^b) % mod = (a%mod)^b % mod

#define ll long long int
ll powerLL(ll x, ll n,ll MOD)
        {

        ll result = 1;
   

 while (n) {
        if (n & 1)
            result = result * x % MOD;
        n = n / 2;
        x = x * x % MOD;
    }
    return result;
}


ll powerStrings(string sa, string sb,ll MOD)
{


    ll a = 0, b = 0;


    for (size_t i = 0; i < sa.length(); i++)
        a = (a * 10 + (sa[i] - '0')) % MOD;

    for (size_t i = 0; i < sb.length(); i++)
        b = (b * 10 + (sb[i] - '0')) % (MOD - 1);

    return powerLL(a, b,MOD);
}

powerStrings("5109109785634228366587086207094636370893763284000","362323789",354252525) 返回208624800但它应该返回323419500。在这种情况下 a 是 49 位

powerStrings("300510498717329829809207642824818434714870652000","362323489",354255221) 返回282740484，这是正确的。在这种情况下，a 是 48 位数字

代码有问题还是我将不得不使用其他方法来做同样的事情？

标签： c++algorithmbigintegernumber-theory

解决方案

它不起作用，因为它在数学上不正确。

一般来说，我们有那个pow(a, n, m) = pow(a, n % λ(m), m)（与a互质m），其中λ是Carmichael 函数。作为一种特殊情况，当m是素数时，则λ(m) = m - 1。费马小定理也涵盖了这种情况。这只是一种特殊情况，它并不总是有效。

λ(354252525) = 2146980，如果我破解它，那么正确的结果就会出来。（虽然基数实际上并不与模数互质）

一般来说，您需要计算模数的 Carmichael 函数，这很重要，但对于小模数是可行的。

推荐阅读