Tutorialspoint.dev

Find (a^b)%m where ‘a’ is very large

Given three numbers a, b and m where 1<=b,m<=10^6 and 'a' may be very large and contains upto 10^6 digits. The task is to find (a^b)%m.

Examples:

Input  : a = 3, b = 2, m = 4
Output : 1
Explanation : (3^2)%4 = 9%4 = 1

Input : a = 987584345091051645734583954832576, b = 3, m = 11
Output: 10

This problem is basically based on modular arithmetic. We can write (a^b) % m as (a%m) * (a%m) * (a%m) * … (a%m), b times. Below is a algorithm to solve this problem :

  • Since ‘a’ is very large so read ‘a’ as string.
  • Now we try to reduce ‘a’. We take modulo of ‘a’ by m once, i.e; ans = a % m , in this way now ans=a%m lies between integer range 1 to 10^6 i.e; 1 <= a%m <= 10^6.
  • Now multiply ans by b-1 times and simultaneously take mod of intermediate multiplication result with m because intermediate multiplication of ans may exceed range of integer and it will produce wrong answer.

C++

// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
  
// utility function to calculate a%m
unsigned int aModM(string s, unsigned int mod)
{
    unsigned int number = 0;
    for (unsigned int i = 0; i < s.length(); i++)
    {
        // (s[i]-'0') gives the digit value and form
        // the number
        number = (number*10 + (s[i] - '0'));
        number %= mod;
    }
    return number;
}
  
// Returns find (a^b) % m
unsigned int ApowBmodM(string &a, unsigned int b,
                                  unsigned int m)
{
    // Find a%m
    unsigned int ans = aModM(a, m);
    unsigned int mul = ans;
  
    // now multiply ans by b-1 times and take
    // mod with m
    for (unsigned int i=1; i<b; i++)
        ans = (ans*mul) % m;
  
    return ans;
}
  
// Driver program to run the case
int main()
{
    string a = "987584345091051645734583954832576";
    unsigned int b=3, m=11;
    cout << ApowBmodM(a, b, m);
    return 0;
}

Java

// Java program to find (a^b) mod m for a large 'a'
  
public class GFG {
      
    // utility function to calculate a%m
    static int aModM(String s, int mod)
    {
        int number = 0;
        for (int i = 0; i < s.length(); i++)
        {
              
            // (s[i]-'0') gives the digit
            // value and form the number
            number = (number * 10 );
            int x = Character.getNumericValue(s.charAt(i));
            number = number + x;
            number %= mod;
        }
          
        return number;
    }
  
    // Returns find (a^b) % m
    static int ApowBmodM(String a, int b, int m)
    {
          
        // Find a%m
        int ans = aModM(a, m);
        int mul = ans;
      
        // now multiply ans by b-1 times 
        // and take mod with m
        for (int i = 1; i < b; i++)
            ans = (ans * mul) % m;
      
        return ans;
    }
  
    // Drive code
    public static void main(String args[])
    {
        String a = "987584345091051645734583954832576";
        int b = 3, m = 11;
        System.out.println(ApowBmodM(a, b, m));
    }
}
  
// This code is contributed by Sam007

Python

# Python program to find (a^b) mod m for a large 'a'
def aModM(s, mod):
    number = 0
  
    # convert string s[i] to integer which gives
    # the digit value and form the number
    for i in range(len(s)):
        number = (number*10 + int(s[i]))
        number = number % m
  
    return number
  
# Returns find (a^b) % m
def ApowBmodM(a, b, mod):
  
    # Find a%m    
    ans = aModM(a, m)
    mul = ans
  
    # now multiply ans by b-1 times and take
    # mod with m
    for i in range(1,b):
        ans = (ans*mul) % m
          
    return ans
  
  
# Driver program to run the case
a = "987584345091051645734583954832576"
b, m = 3, 11
print ApowBmodM(a, b, m)

C#

// C# program to find (a^b) mod m
// for a large 'a'
using System;
  
class GFG {
      
// utility function to calculate a%m
static int aModM(string s, int mod)
{
    int number = 0;
    for (int i = 0; i < s.Length; i++)
    {
          
        // (s[i]-'0') gives the digit
        // value and form the number
        number = (number * 10 );
        int x = (int)(s[i] - '0');
        number = number + x;
        number %= mod;
    }
    return number;
}
  
// Returns find (a^b) % m
static int ApowBmodM(string a, int b, 
                              int m)
{
      
    // Find a%m
    int ans = aModM(a, m);
    int mul = ans;
  
    // now multiply ans by b-1 times 
    // and take mod with m
    for (int i = 1; i < b; i++)
        ans = (ans * mul) % m;
  
    return ans;
}
  
// Driver Code
public static void Main()
{
    string a = "987584345091051645734583954832576";
    int b=3, m=11;
    Console.Write(ApowBmodM(a, b, m));
      
}
}
  
// This code is contributed by Sam007
  
  
  
  

PHP

<?php
// PHP program to find (a^b)
// mod m for a large 'a'
  
// utility function to 
// calculate a%m
function aModM($s, $mod)
{
    $number = 0;
    for ($i = 0; $i < strlen($s); $i++)
    {
          
        // (s[i]-'0') gives the digit
        // value and form the number
        $number = ($number * 10 + 
                  ($s[$i] - '0'));
        $number %= $mod;
    }
    return $number;
}
  
// Returns find (a^b) % m
function ApowBmodM($a, $b,$m)
{
      
    // Find a%m
    $ans = aModM($a, $m);
    $mul = $ans;
  
    // now multiply ans by 
    // b-1 times and take
    // mod with m
    for ($i = 1; $i < $b; $i++)
        $ans = ($ans * $mul) % $m;
  
    return $ans;
}
  
    // Driver code
    $a = "987584345091051645734583954832576";
    $b = 3;
    $m = 11;
    echo ApowBmodM($a, $b, $m);
    return 0;
  
// This code is contributed by nitin mittal.
?>


Output:

10

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter