找到 a^b^c^... mod m [英] finding a^b^c^... mod m

查看：31
本文介绍了找到 a^b^c^... mod m的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我想计算:

abcd... mod m

你知道有什么有效的方法吗，因为这个数字太大了，但是 a , b , c , ... and m 适合一个简单的 32 位整数.

有什么想法吗?

<小时>

警告:这个问题不同于寻找 ab mod m.

另请注意，abc 与 (ab)c 不同.后者等于abc.求幂是右结合的.

解决方案

答案不包含正确性的完整正式数学证明.我认为这里没有必要.此外，它在 SO 上非常难以辨认(例如，没有 MathJax).
我将使用(只是一点点)特定的.

假设数字互质非常重要，因为 Nabb 算法.和之后(使用相同的算法)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不是指数的互质，则需要使用与主问题相同的技巧(实际上，我们应该忘记它是指数并递归解决问题，例如主要问题).在上面的例子中，如果 t2 不是 c 的质数，我们必须使用这个技巧.

计算φ(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)*...

值得记住的是，如果我们要重复计算totient，我们可能想使用Sieve of Eratosthenes并将质数保存在表中.它将减少常数.

示例:strong>(这是正确的，与这个分解算法的原因相同)

def totient(n) : # n - unsigned int结果 = 1p = 2 #素数 - '迭代器'而 p**2 <= n :if(n%p == 0) : # * (p-1)结果 *= (p-1)n/= pwhile(n%p == 0) : # * p^(k-1)结果 *= pn/= pp += 1如果 n != 1 :结果 *= (n-1)在 O(sqrt(n)) 中返回结果 #

案例:abc mod m

因为它实际上做了很多次同样的事情，我相信这个案例会告诉你一般如何解决这个问题.
首先，我们必须将 a 拆分为质数.最好的表示将是对 .
示例:

std::vector>拆分(无符号 n){std::vector>结果;for(unsigned p = 2; p*p <= n;++p) {无符号电流 = 0;而(n % p == 0){当前 += 1;n/= p;}如果(当前！= 0)result.emplace_back(p, 当前);}如果(n ！= 1)result.emplace_back(n, 1);返回结果；}

分割后，我们必须为每一对计算(p^z)^(b^c) mod m=p^(z*(b^c)) mod m.首先我们应该检查，如果 p^(z*(b^c)) |米.如果是，答案就是 (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 mc' = 0米' = 米而 m' % p == 0 :c' += 1m'/= p# 现在 m' = m/gcd((p^z)^(b^c), m)t = totient(m')指数 = z*(b^c)-c' mod t返回 p^c' * (p^exponent mod m')

以及在 Python 下工作的示例:

def modpow(p, z, b, c, m) : # (p^z)^(b^c) mod mcp = 0而 m % p == 0 :cp += 1m/= p # m = m' 现在t = 吨(米)指数 = ((pow(b,c,t)*z)%t + t - (cp%t))%t# 指数 = z*(b^c)-cp mod t返回 pow(p, cp)*pow(p, 指数, m)

使用这个函数，我们可以很容易地计算出(p^z)^(b^c) mod m，之后我们只需要把所有的结果(mod m)，我们还可以持续计算所有内容.下面举例.(我希望我没有写错，写作.)只有假设，b,c 足够大(b^c > log(m) ak. each p^(z*b^k) 不划分 m)，这是简单的检查，我认为没有必要用它来弄乱.

def solve(a,b,c,m) : # 拆分并求解结果 = 1p = 2 # 素数而 p**2 <= a :z = 0而 % p == 0 :# 计算 za/= pz += 1如果 z != 0 :结果 *= modpow(p,z,b,c,m)结果 %= 米p += 1if a != 1 : # 可能的最后一个素数结果 *= modpow(a, 1, b, c, m)返回结果 % m

看起来，它起作用了.
DEMO 和 正确

I would like to calculate:

abcd... 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?

Caveat: This question is different from finding ab mod m.

Also please note that abc is not the same as (ab)c. The later is equal to abc. Exponentiation is right-associative.

解决方案

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.

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>.
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!

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

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆