Modular Exponentiation

Yesterday i came through a question where , the user was asked to compute  modulus of exponential value of a number raised to power of a big number.  For example let , b =4,e=13, m =497.  we have  to  find c. where   c = (b^e)%m  .  obviously its time taking   to compute   (b^e).  
Here is the question :   question link

Note that b is only one digit in length and that e is only two digits in length, but the value b^e is 8 digits in length. i.e  b^e   =  67,108,864.   but  what happen  when ,, Consider b = 5 × 10⁷⁶ and e = 17, both of which are perfectly reasonable values. In this example, b is 77 digits in length and e is 2 digits in length, but the value b^e is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slow considerably. 

 There are three methods  to compute this value :

1.) first one  is  the basic  one . i.e   calculate b^e and then take its modulus with m .

2.) Memory Efficient : this method requires much more operations than the previous method  but  it is much  better  and less time consuming  than  the previous one . The algorithm for the second one is 

if   c can be expressed as ,  c = a.b ,

 then :

c mod m = (a ⋅ b) mod m

c mod m = [(a mod m) ⋅ (b mod m)] mod m

The algorithm is as follows:

1. Set c = 1, e′ = 0.
2. Increase e′ by 1.
3. Set c = (b ⋅ c) mod m.
4. If e′ < e, go to step 2. Else, c contains the correct solution to c ≡ b^e mod 'm.

Note that in every pass through step 3, the equation c ≡ b^e′ mod m holds true. When step 3 has been executed e times, then, c contains the answer that was sought. In summary, this algorithm basically counts up e′ by ones until e′ reaches e, doing a multiply by b and the modulo operation each time it adds one (to ensure the results stay small).

The example b = 4, e = 13, and m = 497 is presented again. The algorithm passes through step 3 thirteen times:

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
• e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

The final answer for c is therefore 445, as in the first method.

Try  to  visualize the  solution  step by step on  your  own using the above algorithm .

The time taken  to compute this one  is much less as  compared to  the first method.

3.) Right to left binary method :

This method  is more efficient than above given  two methods as well  It is a combination of the previous method and a more general principle called exponentiation by squaring (also known as binary exponentiation). and the number of operations is equal to the number of digits in binary representation  of the exponential .

first of all convert  e  in binary form . i.e for e = 13 , its binary equivalent is 1101 . store this in an array . i.e arr[3] = 1 , arr[2] = 1 , arr[1] = 0, arr[0] = 1 .

The implementation of  this method is as  follows :

set, result=1, and base=b,j=0;  

    while(j<=size of array) 

    {

if(arr[j]==1)

    {

      result = (result * base) % m;

    }

j++;

        base = (base*base)% m;;

    }cout<<result<<endl;

Try  to implement  these methods on  your  own ,  because  that is  the only way  you are gonna learn  things . I am doing the same things ,  share  knowledge, it helps you to learn more and more :) keep coding