找到一个^ B ^ C ^ ...模m [英] finding a^b^c^... mod m

问题描述

我想计算：

在 ^{B C ð。。。} 模m

你知道任何有效的方法，因为这个数目太大，但A，B，C，......和M适合在一个简单的32位int。

任何想法？

---

来自这个问题找到一个 ^B 模m不同。请注意，不要张贴无用的答案。

另外请注意， ^{B C} 是不一样的（A ^B ） ^C 。后者等于 ^BC 。幂是右结合。

感谢您！阿林Purcaru

解决方案

  

答案不包含正确性完全正式的数学证明。我认为这是不必要在这里。此外，这将是非常难以辨认上的SO，（无MathJax例如）。
  我将使用（只是一点点），具体因式分解算法。这不是最好的选择，但也足够。

TL;博士

我们要计算 A ^ X模m 。我们将使用功能 modpow（A，X，M）。下面描述

1. 如果 X 足够小（没有指数形式或存在点^ X | M ）只是计算它，返回
2. 拆分为素数，并计算点^ X模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的战俘。

主要问题：

由于目前最好的答案是大约只有特殊情况 GCD（A，M）= 1 ，和OP没有考虑这个假设的问题，我决定写这个答案。我也将使用欧拉定理totient 。引用维基百科：

  

欧拉定理totient ：
  如果 N 和 A 互质的正整数，然后   其中φ（n）是欧拉函数。

假设数字是互质数是非常重要的，因为Nabb的显示评论。所以，首先我们需要确保的数字是互质数。 （为了更清楚起见假设 X = B ^（C ^ ...））。因为，其中我们可以因式分解 A ，并分别计算出 Q1 =（ P1 ^阿尔法）^ X模m，Q2 =（P2 ^测试版）^ X模m ... ，然后计算出简单的方法（Q1 * Q2 * Q3的答案* ...模m）。数至多有 O（日志一）主要因素，因此我们将力至多执行 O（日志一）的计算。

其实，我们不必分裂 A （如果不是全部发生在 M 与其他指数），我们可以用相同的指数结合，但它不是值得注意现在

现在来看看（P ^ Z）^ X模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）模m'使用欧拉定理，因为这个数字是互质数！而且，使用上述观察，我们可以得到点^（ZX）模m 。从上面的假设 WC模m'c = P ^（ZX）模m ，所以现在的答案是点^（ZX）模m = WC 和 W，C 很容易计算。

因此​​，我们可以很容易地计算出 A ^ X模m 。

计算 A ^ X模m 使用欧拉定理

现在假设 A，M 是互质数。如果我们要计算 A ^ X模m ，我们可以计算出 T = totient（M）和通知 A ^ X模m = A ^（X模T）模m 。它可以是有帮助的，如果 X 大，我们知道 X ，如仅针对特定EX pression例如 X = 7 ^ 200 。

看例子 X = B ^ C 。我们可以计算出 T = totient（M）和 X'= B ^ C模牛逼使用的幂的平方算法Θ（日志C）的时间。及后（使用相同的算法） A ^ X'模m ，这等于解决方案。

如果 X = B ^（C ^（D ^ ...）我们会解决这个问题递归。首先计算 T1 = totient（M ），在 T2 = totient（T1）等。例如采取 X = B ^（C ^ D ）。如果 T1 = totient（M）， A ^ X模m = A ^（B ^（C ^ D）MOD T1），我们能够说 B ^（C ^ D）模T1 = B ^（C ^ D MOD T2）MOD T1 ，其中 T2 = totient（T1）。我们的一切都是使用指数的平方算法计算。 注意：如果某些totient不是互质数为指数，就必须使用同样的伎俩，如在主要问题（事实上，我们应该忘记，它的指数和递归地解决问题，就像在主要的问题）。在上面的例子中，如果 T2 不互质与C，我们要使用这一招。

计算φ（N）

注意简单的事实：

1. 如果 GCD（A，B）= 1 ，然后φ（AB）=φ（一）*φ（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）* ...

这是值得记住的是，如果我们将重复计算totient，我们可能要使用的埃拉托色尼筛和保存素数表。这将减少不变。

蟒蛇例如：（这是正确的，因为同样的原因为这种分解算法）

高清totient（N）：＃N - 无符号整型     结果= 1     P = 2 #prime号码 - 迭代     而第** 2'= N：         如果（正％对== 0）：＃*（P-1）             结果* =（P-1）             N / = P         而（正％对== 0）：＃* P ^（K-1）             结果* = P             N / = P         的p + 1 =     如果n = 1！         结果* =（N-1）     返回为O结果＃（的sqrt（N））

案例： A B C 模m

因为它其实做同样的事情多次，我相信这种情况会告诉你如何通常解决这个问题。
首先，我们必须拆分 A 成质的权力。最好再presentation将是对＆LT;号， 指数＆GT;
C ++ 11 例如：

的std ::矢量＆lt;的std ::元组＆LT;无符号，符号＆GT;＆GT;斯普利特（无符号N）{   的std ::矢量＆lt;的std ::元组＆LT;无符号，符号＆GT;＆GT;结果;   为（无符号​​P = 2; P * P＆LT; = N ++ P）{     无符号电流= 0;     同时（N％P == 0）{       当前+ = 1;       N / = P;      }     如果（当前！= 0）      result.emplace_back（对，电流）;    }   如果（N！= 1）    result.emplace_back（N，1）;   返回结果;  }

在分裂，我们要计算（P ^ Z）^（B ^ C）模m = P ^（Z *（B ^ C））模m 每对。首先，我们要检查，如果点^（Z *（B ^ C））|米。如果是答案就是（P ^ Z）^（B ^ C），但它可能只在情况下，其中 Z，B，C 是非常小的。我相信我没有表现出code例子吧。
最后，如​​果点^（Z * B ^ C）＆GT;米我们要算出答案。首先，我们要计算 C'= GCD（M，P ^（Z * B ^ C））。之后，我们能够计算 T = totient（M'）。和（Z * B ^ C - C'modT）。这是简单的方法来得到答案。

 函数modpow（P，Z，B​​，C，M：整数）＃（P ^ Z）^（B ^ C）模m
    C'= 0
    M'= M
    而M'％P == 0：
        C'+ = 1
        M'/ = P
    ＃现在M'= M / GCD（（P ^ Z）^（B ^ C），M）
    T = totient（M'）
    指数= Z *（B ^ C）-C'mod牛逼
    返回p ^ C'*（P ^指数模m'）
 

和下面的的Python 工作示例

高清modpow（P，Z，B​​，C，M）：＃（P ^ Z）^（B ^ C ）模m     CP = 0     而X％P == 0：         CP + = 1         M / = P＃M = M'现在     T = totient（M）     指数=（（POW（B，C，T）* Z）％T + T - （CP％T））％叔                             ＃指数= Z *（B ^ C）-cpmod牛逼     返回POW（P，CP）* POW（P，指数m）

使用这个功能，我们可以很容易地计算（P ^ Z）^（B ^ C）模m ，以后我们只需要多所有结果（模m ），我们也可以计算出一切在持续的基础。下面的例子。 （我希望我没有犯错，写作）。只有假设，b，c是足够大的（ B ^ c取代;记录（M） AK每个<$ C $ç>点^（Z * B ^ K）不分 M ），这是简单的检查，我没有看到点通过它，使混乱。

高清解决（A，B，C，M）：＃拆并解决     结果= 1     p为2＃素数     而第** 2'= A：         Z = 0         而％P == 0：                      ＃计算ž             A / = P             Z + = 1         如果Z = 0！             结果* = modpow（P，Z，B​​，C，M）             导致％= M         的p + 1 =     如果= 1：＃！可能最后黄金         结果* = modpow（一，1，B，C，M）     返回结果％M

看起来，就像它的工作原理。
演示 和<一href="http://www.wolframalpha.com/input/?i=%28109315800409857451726136757650%5E%289878789%5E1214712%29%29%20mod%201948502738"相对=nofollow>这是正确的！

I would like to calculate:

a^bcd... mod m

Do you know any efficient way since this number is too big but a , b , c , ... and m fit in a simple 32-bit int.

Any Ideas?

---

This question is different from finding a^b mod m. Please pay attention and don't post useless answers.

Also please note that a^bc is not same as (a^b)^c. The later is equal to a^bc. Exponentiation is right-associative.

Thank you! Alin Purcaru

解决方案

The answer does not contain full formal mathematical proof of correctness. I assumed that it is unnecessary here. Besides, it would be very illegible on SO, (no MathJax for example).
I will use (just a little bit) specific prime factorization algorithm. It's not best option, but enough.

tl;dr

We want calculate a^x mod m. We will use function modpow(a,x,m). Described below.

1. If x is small enough (not exponential form or exists p^x | m) just calculate it and return
2. Split into primes and calculate p^x mod m separately for each prime, using modpow function
   1. Calculate c' = gcd(p^x,m) and t' = totient(m/c')
   2. Calculate w = modpow(x.base, x.exponent, t') + t'
   3. Save pow(p, w - log_p c', m) * c' in A table

3. Multiple all elements from A and return modulo m

Here pow should look like python's pow.

Main problem:

Because current best answer is about only special case gcd(a,m) = 1, and OP did not consider this assumption in question, I decided to write this answer. I will also use Euler's totient theorem. Quoting wikipedia:

Euler's totient theorem:
If n and a are coprime positive integers, then where φ(n) is Euler's totient function.

The assumption numbers are co-primeis very important, as Nabb shows in comment. So, firstly we need to ensure that the numbers are co-prime. (For greater clarity assume x = b^(c^...).) Because , where we can factorize a, and separately calculate q1 = (p1^alpha)^x mod m,q2 = (p2^beta)^x mod m... and then calculate answer in easy way (q1 * q2 * q3 * ... mod m). Number has at most o(log a) prime factors, so we will be force to perform at most o(log a) calculations.

In fact we doesn't have to split to every prime factor of a (if not all occur in m with other exponents) and we can combine with same exponent, but it is not noteworthy by now.

Now take a look at (p^z)^x mod m problem, where p is prime. Notice some important observation:

If a,b are positive integers smaller than m and c is some positive integer and , then true is sentence .

Using the above observation, we can receive solution for actual problem. We can easily calculate gcd((p^z)^x, m). If x*z are big, it is number how many times we can divide m by p. Let m' = m /gcd((p^z)^x, m). (Notice (p^z)^x = p^(z*x).) Let c = gcd(p^(zx),m). Now we can easily (look below) calculate w = p^(zx - c) mod m' using Euler's theorem, because this numbers are co-prime! And after, using above observation, we can receive p^(zx) mod m. From above assumption wc mod m'c = p^(zx) mod m, so the answer for now is p^(zx) mod m = wc and w,c are easy to calculate.

Therefore we can easily calculate a^x mod m.

Calculate a^x mod m using Euler's theorem

Now assume a,m are co-prime. If we want calculate a^x mod m, we can calculate t = totient(m) and notice a^x mod m = a^(x mod t) mod m. It can be helpful, if x is big and we know only specific expression of x, like for example x = 7^200.

Look at example x = b^c. we can calculate t = totient(m) and x' = b^c mod t using exponentiation by squaring algorithm in Θ(log c) time. And after (using same algorithm) a^x' mod m, which is equal to solution.

If x = b^(c^(d^...) we will solve it recursively. Firstly calculate t1 = totient(m), after t2 = totient(t1) and so on. For example take x=b^(c^d). If t1=totient(m), a^x mod m = a^(b^(c^d) mod t1), and we are able to say b^(c^d) mod t1 = b^(c^d mod t2) mod t1, where t2 = totient(t1). everything we are calculating using exponentiation by squaring algorithm. Note: If some totient isn't co-prime to exponent, it is necessary to use same trick, as in main problem (in fact, we should forget that it's exponent and recursively solve problem, like in main problem). In above example, if t2 isn't relatively prime with c, we have to use this trick.

Calculate φ(n)

Notice simple facts:

1. if gcd(a,b)=1, then φ(ab) = φ(a)*φ(b)
2. if p is prime φ(p^k)=(p-1)*p^(k-1)

Therefore we can factorize n (ak. n = p1^k1 * p2^k2 * ...) and separately calculate φ(p1^k1),φ(p2^k2),... using fact 2. Then combine this using fact 1. φ(n)=φ(p1^k1)*φ(p2^k2)*...

It is worth remembering that, if we will calculate totient repeatedly, we may want to use Sieve of Eratosthenes and save prime numbers in table. It will reduce the constant.

python example: (it is correct, for the same reason as this factorization algorithm)

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))

Case: abc mod m

Cause it's in fact doing the same thing many times, I believe this case will show you how to solve this generally.
Firstly, we have to split a into prime powers. Best representation will be pair <number, exponent>.
c++11 example:

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;
 }

After split, we have to calculate (p^z)^(b^c) mod m=p^(z*(b^c)) mod m for every pair. Firstly we should check, if p^(z*(b^c)) | m. If, yes the answer is just (p^z)^(b^c), but it's possible only in case in which z,b,c are very small. I believe I don't have to show code example to it.
And finally if p^(z*b^c) > m we have to calculate the answer. Firstly, we have to calculate c' = gcd(m, p^(z*b^c)). After we are able to calculate t = totient(m'). and (z*b^c - c' mod t). It's easy way to get an answer.

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')

And below Python working example:

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)

Using this function, we can easily calculate (p^z)^(b^c) mod m, after we just have to multiple all results (mod m), we can also calculate everything on an ongoing basis. Example below. (I hope I didn't make mistake, writing.) Only assumption, b,c are big enough (b^c > log(m) ak. each p^(z*b^k) doesn't divide m), it's simple check and I don't see point to make clutter by it.

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

Looks, like it works.
DEMO and it's correct!

这篇关于找到一个^ B ^ C ^ ...模m的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！