[Math] Modulus trick in programming

modular arithmeticnumber-systems

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.

Best Answer

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.

Related Question