2

I am trying to compute a^b^c mod p for some positive integers a,b,c,p. One possible (and obvious) way is to use fast modular exponentiation which will run in O(log(b^c))=clog(b). While I don't mind the efficiency here, the obvious downfall of this method is that you need an explicit binary representation of b^c which in itself is already exponential.

So the question for me is, if I can not represent b^c as a binary representation, is there a way I can compute a^b^c mod p from the binary representations of a,b, and c?

AspiringMat
  • 2,161
  • 2
  • 21
  • 33
  • "can not represent b^c as a binary representation" - could you expand on this please – Jesse Oct 26 '17 at 01:55
  • @JesseBarnett From a programmatical point of view. For instance b=2 and c=200, the number cannot be "stored" as a binary representation inside the native datatypes of C++ for instance. – AspiringMat Oct 26 '17 at 01:56
  • im not really following why this is a problem. `#include cmath` and then once you have defined your variables, `answer = pow(pow(a,b),c) % p` doesn't work? – Jesse Oct 26 '17 at 02:08
  • Iff you know the factorization of p you can compute its Euler totient and a^x mod p = a^(x mod totient(p)) mod p for x = b^c is much easier/faster; see https://math.stackexchange.com/questions/1626/modular-exponentiation-using-euler-s-theorem . If you do it on a computer even bignums are usually still binary though. – dave_thompson_085 Oct 26 '17 at 02:16
  • @dave_thompson_085 But that assumes a and p are coprime. For me its not always the case – AspiringMat Oct 26 '17 at 02:18
  • 1
    @JesseBarnett What you did would calculate a^(bc) mod p and not a^b^c mod p. Here, the a is multiplied b^c times, not a^b multiplied c times – AspiringMat Oct 26 '17 at 02:20
  • Hmm... it feels to me like there should be a way to eliminate the common factors and reduce to a case where Euler/Fermat works, but I don't remember enough number theory to prove it. You might try that part on the math Stack. – dave_thompson_085 Oct 26 '17 at 02:44
  • 1
    If a and p are not co-prime then you'll still want to use Euler's totient function. Just compute a^(b^c) mod each prime power and use the chinese remainder theorem (CRT) to compute the answer. Or, more simply, if d=gcd(a, p), then compute a^x mod (p/d) where x = (b^c) mod ϕ(p/d) and use the CRT to get the answer. – President James K. Polk Oct 26 '17 at 02:59
  • 3
    Possible duplicate of [finding a^b^c^... mod m](https://stackoverflow.com/questions/4223313/finding-abc-mod-m) – phuclv Oct 26 '17 at 05:22
  • @JesseBarnett that just works for tiny numbers. There are ways to do that for big numbers much efficiently – phuclv Oct 26 '17 at 05:27

2 Answers2

0
(a^b^c) mod p = (((a^b) mod p)^c) mod p

So you can do

modpow(modpow(a,b,p),c,p);

Where all operands results and subresults are normal ints. As modpow you can use power by squaring in modulo p like here:

beware those are a bit optimized taking advantage of the properties of specific selected p so you need to change lines like

if (DWORD(d)>=DWORD(p)) d-=p;

into

d%=p;

[Example]

(2^3^5) % 6 = 
(8  ^5) % 6 =
  32768 % 6 = 2

(((2^3)%6)^5) % 6 = 
((   8 %6)^5) % 6 = 
(    2    ^5) % 6 =
    32        % 6 = 2
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • 2
    This calculated a^(bc) mod p NOT a^b^c. Here, a is multiplied to itself b^c times! – AspiringMat Oct 26 '17 at 04:27
  • never mind thanks for the answer, i got slightly confused. So this runs in log(b)log(c) correct? – AspiringMat Oct 26 '17 at 04:33
  • @AspiringMat For normal `int` variables the complexity is `O(log(b)+log(c))` if we assume both exponents are limited by `n` then the complexity is `O(log(n))`. For `bigint` operands however operations `+,-,*,/` are not `O(1)` anymore so the complexity is much worse in such case. – Spektre Oct 26 '17 at 08:21
  • @AspiringMat Also if you want to compute `a^(b^c) mod p` instead then this will not work and you need to use the linked possible duplicate. – Spektre Oct 26 '17 at 08:37
  • 1
    This answer is incorrect. (a^b^c) mod p is *not* equal to (((a^b) mod p)^c) mod p – President James K. Polk Oct 26 '17 at 12:56
  • @JamesKPolk if your mean `((a^b)^c) mod p` ? for that you're right but the OP is about `a^b^c mod p` or need to edit the equation properly if not. – Spektre Oct 26 '17 at 14:00
  • @Spektre: The expression `a^b^c` is almost always (in mathematics and in programming) interpreted as `a^(b^c)`, not as `(a^b)^c`. The OP is clearly working with the `a^(b^c)` interpretation, since the question mentions computing `b^c` as a substep. – Mark Dickinson Oct 26 '17 at 14:07
  • @JamesKPolk On the other hand OP's first comment here suggest you're right guys ... (making the question duplicate) ... However Looks like I can not delete accepted answer .... – Spektre Oct 26 '17 at 14:24
  • 1
    I agree it's not completely clear, that's why I didn't downvote. I just guessed from his discussion that he meant a^(b^c). – President James K. Polk Oct 26 '17 at 15:02
  • I ended up addapting your method. So I write a^b^c as a^(b*b*..*b) so i first compute a^b mod p then I calculate (a^b mod p)^b mod p and so on. This runs in O(c log b) – AspiringMat Oct 27 '17 at 05:12
  • @AspiringMat `O(n.log(m))` `n` is number of nested modpows and `m` is limit of the input variables size (`log(m)` is the bitwidth of your variables) . – Spektre Oct 27 '17 at 06:54
0

https://discuss.codechef.com/t/compute-a-b-c-mod-p/1989 check this page, after solve https://cses.fi/problemset/task/1712 . The above answer modpow(modpow(a,b,p),c,p); looks very logical , but it won't work(you can verify it through CSES problem mentioned above). Use this formula/method modpow(a,modpow(b,c,p-1),p); . They use Fermat's theorem to derive this modpow(a,modpow(b,c,p-1),p); . By the way cpp code is as follows :

#include <bits/stdc++.h>
#define ar array
#define int long long
using namespace std;

const int mxN=2e5+2,mxM=1003,M=1e9+7;

int pM(int n,int p,int M)
{
    int res=1;
    while(p)
    {
        if(p&1)
            res=res*n%M;
        n=n*n%M;
        p>>=1;
    }
    return res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
         int a,b,c;
        cin>>a>>b>>c;
        cout<<pM(a,pM(b,c,M-1),M)<<"\n";
    }

    return 0;
}
Abhishek More
  • 1
  • 2