找到一个^ b ^ c ^ ... mod m

Question

我想计算一下:

a ^{b c d ...}mod m

你知道任何有效的方法,因为这个数字太大但a,b,c,...和m适合一个简单的32位int.

有任何想法吗？

---

警告:这个问题是由寻找不同^b模m.

另请注意,^{b c}与(a ^b)^c不同.后者等于^bc.指数是右关联的.

Answer 1

a ^{b c} mod m = a ^{b c mod n} mod m,其中n =？(m)欧拉的函数.

如果m是素数,那么n = m-1.

编辑:正如Nabb指出的那样,这只有在与m相互作用时才有效.所以你必须先检查一下.

Answer 2

答案不包含完整的正式数学证明正确性.我认为这里没必要.此外,它在SO上会非常难以理解(例如,没有MathJax).
我将使用(只是一点点)特定的素数因子分解算法.这不是最好的选择,但足够了.

TL;博士

我们想要计算a^x mod m.我们将使用功能modpow(a,x,m).如下面所描述的.

1. 如果x足够小(不是指数形式或存在p^x | m),只需计算并返回
2. 分为素数并p^x mod m使用modpow函数 分别计算每个素数
   1. 计算c' = gcd(p^x,m)和t' = totient(m/c')
   2. 计算 w = modpow(x.base, x.exponent, t') + t'
   3. 保存pow(p, w - log_p c', m) * c'在A表格中
3. 来自A的多个所有元素和返回模m

这pow应该看起来像python的pow.

主要问题:

因为目前最好的答案只是特殊情况gcd(a,m) = 1,OP没有考虑这个假设,我决定写下这个答案.我也将使用欧拉的东西定理.引用维基百科:

欧拉定理欧拉:
如果n和a为互质的正整数,然后 其中φ(n)是欧拉的函数.

numbers are co-prime正如Nabb 在评论中所表达的那样,这个假设非常重要.因此,首先我们需要确保这些数字是共同素数.(为了更清楚地假设x = b^(c^...).)因为,哪里 我们可以分解a,分别计算q1 = (p1^alpha)^x mod m,q2 = (p2^beta)^x mod m...,然后以简单的方式计算答案(q1 * q2 * q3 * ... mod m).数字最多具有o(log a)素数因子,因此我们将强制执行大多数o(log a)计算.

事实上,我们不必分裂到每个主要因素a(如果不是全部m与其他指数一起发生),我们可以结合相同的指数,但现在不值得注意.

现在来看看(p^z)^x mod m问题,哪里p是素数.注意一些重要的观察:

如果a,b正整数小于m且c是一些正整数和那么真的就是判刑 .

使用上述观察,我们可以获得实际问题的解决方案.我们可以轻松计算gcd((p^z)^x, m).如果x*z很大,那么它是我们可以除以m的次数p.我们m' = m /gcd((p^z)^x, m).(注意(p^z)^x = p^(z*x).)让c = gcd(p^(zx),m).现在我们可以很容易地(看下面)w = p^(zx - c) mod m'使用欧拉定理计算,因为这个数字是共同素数!之后,通过以上观察,我们可以收到p^(zx) mod m.从上述的前提下wc mod m'c = p^(zx) mod m,所以现在的答案是p^(zx) mod m = wc,并w,c很容易计算.

因此,我们可以很容易地计算a^x mod m.

a^x mod m使用欧拉定理计算

现在假设a,m是共同素数.如果我们想要计算a^x mod m,我们可以计算t = totient(m)并注意a^x mod m = a^(x mod t) mod m.它可能很有帮助,如果x很大,我们只知道具体的表达x,例如x = 7^200.

看一下例子x = b^c.我们可以通过算法及时计算t = totient(m)和x' = b^c mod t使用取幂?(log c).之后(使用相同的算法)a^x' mod m,这等于解决方案.

如果x = b^(c^(d^...)我们将递归地解决它.首先计算t1 = totient(m),之后t2 = totient(t1)等等.比如拿x=b^(c^d).如果t1=totient(m),a^x mod m = a^(b^(c^d) mod t1)我们可以说b^(c^d) mod t1 = b^(c^d mod t2) mod t1,在哪里t2 = totient(t1).我们通过平方算法使用求幂计算的所有东西. 注意:如果某些totient不是指数的共同素数,则必须使用相同的技巧,如在主要问题中(事实上,我们应该忘记它是指数并递归地解决问题,就像在主要问题中一样).在上面的例子中,如果t2c不是相对素数,我们必须使用这个技巧.

计算 ?(n)

注意简单的事实:

1. 如果gcd(a,b)=1,那么?(ab) = ?(a)*?(b)
2. 如果p是素数?(p^k)=(p-1)*p^(k-1)

因此,我们可以分解n(ak.n = p1^k1 * p2^k2 * ...)并?(p1^k1),?(p2^k2),...使用事实2 单独计算.然后使用事实1将其组合.?(n)=?(p1^k1)*?(p2^k2)*...

值得记住的是,如果我们将反复计算总数,我们可能想要使用Eratosthenes筛选并在表格中保存素数.它会减少常数.

python示例:(这是正确的,出于与此分解算法相同的原因)

def totient(n) :          # n - unsigned int
    result = 1
    p = 2                 #prime numbers - 'iterator'
    while p**2 <= n :
        if(n%p == 0) :    # * (p-1)
            result *= (p-1)
            n /= p
        while(n%p == 0) : # * p^(k-1)
            result *=  p
            n /= p
        p += 1
    if n != 1 :
        result *= (n-1)
    return result         # in O(sqrt(n))

案件: abc mod m

因为它实际上做了很多次同样的事情,我相信这个案例会告诉你如何解决这个问题.
首先,我们必须分裂a为主要权力.最好的代表是成对<number, exponent>.
c ++ 11示例:

std::vector<std::tuple<unsigned, unsigned>> split(unsigned n) {
  std::vector<std::tuple<unsigned, unsigned>> result;
  for(unsigned p = 2; p*p <= n; ++p) {
    unsigned current = 0;
    while(n % p == 0) {
      current += 1;
      n /= p;
     }
    if(current != 0)
     result.emplace_back(p, current);
   }
  if(n != 1)
   result.emplace_back(n, 1);
  return result;
 }

拆分后,我们必须计算(p^z)^(b^c) mod m=p^(z*(b^c)) mod m每一对.首先我们应该检查,如果p^(z*(b^c)) | m.如果,是的,答案只是(p ^ z)^(b ^ c),但只有在z,b,c非常小的情况下才有可能.我相信我不必向它展示代码示例.
最后,如果p^(z*b^c) > m我们必须计算答案.首先,我们必须计算c' = gcd(m, p^(z*b^c)).在我们能够计算之后t = totient(m').和 (z*b^c - c' mod t).这是一个简单的方法来得到答案.

function modpow(p, z, b, c, m : integers) # (p^z)^(b^c) mod m
    c' = 0
    m' = m
    while m' % p == 0 :
        c' += 1
        m' /= p
    # now m' = m / gcd((p^z)^(b^c), m)
    t = totient(m')
    exponent = z*(b^c)-c' mod t
    return p^c' * (p^exponent mod m')

以下是Python工作示例:

def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod m
    cp = 0
    while m % p == 0 :
        cp += 1
        m /= p              # m = m' now
    t = totient(m)
    exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t
                            # exponent = z*(b^c)-cp mod t
    return pow(p, cp)*pow(p, exponent, m)

使用此函数,我们可以轻松计算(p^z)^(b^c) mod m,在我们只需要将所有结果(mod m)复用后,我们还可以持续计算所有内容.以下示例.(我希望我没有犯错,写作.)只有假设,b,c足够大(b^c > log(m)ak.每个p^(z*b^k)都不分m),这是简单的检查,我不认为有点混乱.

def solve(a,b,c,m) : # split and solve
    result = 1
    p = 2            # primes
    while p**2 <= a :
        z = 0
        while a % p == 0 :
                     # calculate z
            a /= p
            z += 1
        if z != 0 :
            result *=  modpow(p,z,b,c,m)
            result %= m
        p += 1
    if a != 1 :      # Possible last prime
        result *= modpow(a, 1, b, c, m)
    return result % m

看起来像是有效的.
DEMO,这是正确的!