2

Given two very large integers,assume the length=1,000,000 digits,how will you compute $a^b \mod 10^7$.Since the two numbers are large, of course the value of a^b will be large. So,we find only the last 7 digits using modulus $10^7$. I came across this solution where $\mod=10^7$.

    #include<stdio.h>
    ll ppow(ll b,ll p)
    {
      if(p==0) return 1;
      if(b==1) return 1;
      if(p%2==0)
      {
        ll res=ppow(b,p/2);
        return (res*res)%mod;
      }
      return (b*ppow(b,p-1))%mod;
    }

char A[100001],B[100001];
void solve()
 {
    scanf("%s %s",A,B);
    ll a=0;
    for(int i=0;A[i]!='\0';i++)
    {
        a=(10*a+A[i]-'0')%mod;
    }
    ll res=1;
    for(int i=0;B[i]!='\0';i++)
    {
        res=(ppow(res,10)*ppow(a,B[i]-'0'))%mod;
    }
    printf("%lld\n",res);
}

int main()
{
    int t;
    read(t);
    while(t--) 
     solve();
}

I can see that some beautiful trick is done using modulus.But,i'm not able to figure out that trick :(. I'm trying this from today morning. But i'm not able to figure this out. Can somebody give me an insight how this solution works ?

I know these types of problems can be easily done using PYTHON.But just want to know the math behind it .

Thanks.

vaidy_mit
  • 631
  • 2
    See http://en.wikipedia.org/wiki/Modular_exponentiation – Listing Nov 25 '13 at 17:04
  • 1
    The code is unreadable. – Ali Caglayan Nov 25 '13 at 17:05
  • I'm very sorry ! This is actually a solution i came across. I've intended it now. – vaidy_mit Nov 25 '13 at 17:09
  • @ listing Yeah okay sir ! But do you know any videos which perfectly explains that ? – vaidy_mit Nov 25 '13 at 17:12
  • 1
    Basically, the code is implementing the following: "ppow is a recursive function that squares it's result and takes the value modulo the modulus, returning additional multipliers for non-zero binary digits of the exponent". – abiessu Nov 25 '13 at 17:13
  • @abiessu Oh thanks ! But can you write an answer with taking two numbers as examples,so that i can understand it in a much better way ! – vaidy_mit Nov 25 '13 at 17:18
  • Note that the code shown does not detail the definition or value of mod so we are left to guess that it might be defined as some positive integer elsewhere... – abiessu Nov 25 '13 at 18:35

1 Answers1

5

Modular Exponentiation is the general term for $a^b\pmod c$. As an example, consider something "easy" like $2^{1386}\pmod{1387}$. Rewriting $1386$ as a sum of its binary digits helps later in this process, so note that $1386=2^{10}+2^8+2^6+2^5+2^3+2^1$.

So then we have

$$2^{1386}=2^{2^{10}+2^8+2^6+2^5+2^3+2^1}=2^{2^{10}}\cdot 2^{2^8}\cdot 2^{2^6}\cdot 2^{2^5}\cdot 2^{2^3}\cdot 2^{2^1}$$

I have written out the calculations for the above values, so rather than redoing that, here is what they become:

$$2^{2^1}=4,\ 2^{2^3}=256,\ 2^{2^5}\equiv -260\pmod{1387}\\2^{2^6}\equiv 1024\pmod {1387},\ 2^{2^8}\equiv 16\pmod{1387},\\2^{2^{10}}\equiv 347\pmod{1387}$$

Now we have a series of small numbers to multiply together, which is much faster than doing a loop $1386$ times and multiplying by $2$ each time and taking the modulus.

So the question becomes, why did we rewrite our exponent as a sum of binary digits? Essentially, it is because taking the square of a number multiplies its exponent by $2$:

$$(2^2)^2=2^{2^2}\\(2^{2^2})^2=2^{2^3}\\(2^{2^3})^2=2^{2^4}\\\dots$$

and in general,

$$(a^b)^2=a^{2b}\\(a^{2^b})^2=a^{2^{b+1}}$$

So the algorithm used by the ppow function is implementing this process; it squares the current result and applies the modulus, asks a recursive version of itself for the result with half the current exponent, and asks for the current value as well if the current exponent is odd, thereby capturing each binary digit of the exponent. Finding the value modulo $1387$ of the numbers $2^{2^{10}},\ 2^{2^8},\ 2^{2^6},\ 2^{2^5},\ 2^{2^3},\ 2^{2^1}$ was faster than looping $1386$ times because we only needed to square $2$ ten times to get to the value of $2^{2^{10}}$, and we got the modular value of all six numbers along the way.

This algorithm could be rewritten to use any particular numeric base in the exponent, but then that numeric base would also need to be the common exponent. So instead of squaring each time, we could cube each time and consider the exponent in base $3$, and so on.

Community
  • 1
abiessu
  • 8,115