Encuentra el poder del poder bajo mod de un número primo

Dados cuatro números A, B, C y M, donde M es un número primo. Nuestra tarea es encontrar A ^BC (mod M).
Ejemplo: 
 

Input  : A = 2, B = 4, C = 3, M = 23
Output : 6
43 = 64 so,
2^64(mod 23) = 6 

Un enfoque ingenuo es calcular res = B ^C y luego calcular A ^res % M por exponencial modular. El problema de este enfoque es que no podemos aplicar directamente mod M en B ^C , por lo que tenemos que calcular este valor sin mod M. Pero si lo resolvemos directamente, obtendremos el gran valor del exponente de A que definitivamente se desbordará en la respuesta final.
Un enfoque eficiente es reducir B ^C a un valor más pequeño usando el pequeño teorema de Fermat y luego aplicar la exponencial modular.
 

According the Fermat's little
a(M - 1) = 1 (mod M) if M is a prime.

So if we rewrite BC as x*(M-1) + y, then the
task of computing ABC becomes Ax*(M-1) + y
which can be written as Ax*(M-1)*Ay.
From Fermat's little theorem, we know Ax*(M-1) = 1.
So task of computing ABC reduces to computing Ay

What is the value of y?
From BC = x * (M - 1) + y,
y can be written as BC % (M-1)

We can easily use the above theorem such that we can get
A ^ (B ^ C) % M = (A ^ y ) %  M

Now we only need to find two things as:-
1. y = (B ^ C) % (M - 1)
2. Ans = (A ^ y) % M

// C++ program to find (a^b) mod m for a large 'a'
#include<bits/stdc++.h>
using namespace std;
 
// Iterative Function to calculate (x^y)%p in O(log y)
unsigned int power(unsigned int x, unsigned int y,
                                   unsigned int p)
{
    unsigned int res = 1;      // Initialize result
 
    x = x % p;  // Update x if it is more than or
                // equal to p
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;
 
        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}
 
unsigned int Calculate(unsigned int A, unsigned int B,
                       unsigned int C, unsigned int M)
{
    unsigned int res, ans;
 
    // Calculate B ^ C (mod M - 1)
    res = power(B, C, M-1);
 
    // Calculate A ^ res ( mod M )
    ans = power(A, res, M);
 
    return ans;
}
 
// Driver program to run the case
int main()
{   // M must be a Prime Number
    unsigned int A = 3, B = 9, C = 4, M = 19;
 
    cout << Calculate(A, B, C, M);
 
    return 0;
}

// Java program to find (a^b)
// mod m for a large 'a'
import java.util.*;
 
class GFG {
     
// Iterative Function to
// calculate (x^y)%p in O(log y)
static int power(int x, int y, int p) {
     
    // Initialize result
    int res = 1;
 
    // Update x if it is more
    // than or equal to p
    x = x % p;
 
    while (y > 0) {
         
    // If y is odd, multiply x with result
    if (y % 2 != 0)
        res = (res * x) % p;
 
    // y must be even now
    y = y >> 1; // y = y/2
    x = (x * x) % p;
    }
    return res;
}
 
static int Calculate(int A, int B, int C, int M) {
    int res, ans;
 
    // Calculate B ^ C (mod M - 1)
    res = power(B, C, M - 1);
 
    // Calculate A ^ res ( mod M )
    ans = power(A, res, M);
 
    return ans;
}
 
// Driver code
public static void main(String[] args) {
     
    // M must be a Prime Number
    int A = 3, B = 9, C = 4, M = 19;
 
    System.out.print(Calculate(A, B, C, M));
}
}
 
// This code is contributed by Anant Agarwal.

# Python program to calculate the ans
def calculate(A, B, C, M):
 
    # Calculate B ^ C (mod M - 1)
    res = pow(B, C, M-1)
 
    # Calculate A ^ res ( mod M )
    ans = pow(A, res, M)
 
    return ans
 
# Driver program to run the case
A = 3
B = 9
C = 4
 
# M must be Prime Number
M = 19
print( calculate(A, B, C, M) )

// C# program to find (a^b) mod m for
// a large 'a'
using System;
 
class GFG {
     
    // Iterative Function to calculate
    // (x^y)%p in O(log y)
    static int power(int x, int y, int p)
    {
         
        // Initialize result
        int res = 1;
     
        // Update x if it is more
        // than or equal to p
        x = x % p;
     
        while (y > 0) {
             
            // If y is odd, multiply x
            // with result
            if (y % 2 != 0)
                res = (res * x) % p;
         
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
     
    static int Calculate(int A, int B,
                          int C, int M)
    {
        int res, ans;
     
        // Calculate B ^ C (mod M - 1)
        res = power(B, C, M - 1);
     
        // Calculate A ^ res ( mod M )
        ans = power(A, res, M);
     
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
         
        // M must be be a Prime Number
        int A = 3, B = 9, C = 4, M = 19;
     
        Console.Write(Calculate(A, B, C, M));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find
// (a^b) mod m for a
// large 'a'
 
// Iterative Function
// to calculate (x^y)%p
// in O(log y)
function power($x, $y, $p)
{
    $res = 1; // Initialize result
 
    $x = $x % $p; // Update x if it
                  // is more than or
                  // equal to p
 
    while ($y > 0)
    {
        // If y is odd, multiply
        // x with result
        if ($y & 1)
            $res = ($res * $x) % $p;
 
        // y must be even now
        $y = $y >> 1; // y = y/2
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
function Calculate($A, $B, $C, $M)
{
    $res; $ans;
 
    // Calculate B ^ C
    // (mod M - 1)
    $res = power($B, $C, $M - 1);
 
    // Calculate A ^
    // res ( mod M )
    $ans = power($A, $res, $M);
 
    return $ans;
}
 
// Driver Code
 
// M must be be
// a Prime Number
$A = 3; $B = 9;
$C = 4; $M = 19;
 
echo Calculate($A, $B, 
               $C, $M);
 
// This code is contributed
// by ajit
?>

<script>
 
// Javascript program to find (a^b)
// mod m for a large 'a'
  
// Iterative Function to 
// calculate (x^y)%p in O(log y)
function power(x, y, p) {
       
    // Initialize result
    let res = 1; 
   
    // Update x if it is more
    // than or equal to p
    x = x % p; 
   
    while (y > 0) {
           
    // If y is odd, multiply x with result
    if (y % 2 != 0)
        res = (res * x) % p;
   
    // y must be even now
    y = y >> 1; // y = y/2
    x = (x * x) % p;
    }
    return res;
}
   
function Calculate(A, B, C, M) {
    let res, ans;
   
    // Calculate B ^ C (mod M - 1)
    res = power(B, C, M - 1);
   
    // Calculate A ^ res ( mod M )
    ans = power(A, res, M);
   
    return ans;
}
 
// Driver Code
     
    // M must be be a Prime Number
    let A = 3, B = 9, C = 4, M = 19;
   
    document.write(Calculate(A, B, C, M));
     
</script>

Producción: 

18

Complejidad de tiempo: O(log(B) + log(C)) 
Espacio auxiliar: O(1) Shubham Bansal
contribuye con este artículo . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.