Exponenciación Modular (Potencia en Aritmética Modular)

Dados tres números x, y y p, calcule (x y ) % p. 

Ejemplos: 

Input:  x = 2, y = 3, p = 5
Output: 3
Explanation: 2^3 % 5 = 8 % 5 = 3.

Input:  x = 2, y = 5, p = 13
Output: 6
Explanation: 2^5 % 13 = 32 % 13 = 6.

Hemos discutido soluciones recursivas e iterativas para el poder.

A continuación se discute la solución iterativa. 

C++14

/* Iterative Function to calculate (x^y)%p in O(log y) */
#include <iostream>
using namespace std;
 
int power(int x, int y, int p)
{
 
    // Initialize answer
    int res = 1;
 
    // Check till the number becomes zero
    while (y > 0) {
 
        // If y is odd, multiply x with result
        if (y % 2 == 1)
            res = (res * x);
 
        // y = y/2
        y = y >> 1;
 
        // Change x to x^2
        x = (x * x);
    }
    return res % p;
}
 
int main()
{
    int x = 2;
    int y = 5;
    int p = 13;
    cout << "Power is " << power(x, y, p);
    return 0;
}
 
// This code is contributed by yaswanth0412

Java

/* Iterative Function to calculate (x^y)%p in O(log y) */
class GFG {
    static int power(int x, int y, int p)
    {
        int res = 1; // Initialize result
 
        while (y > 0) {
 
            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = res * x;
 
            // y must be even now
            y = y >> 1; // y = y/2
            x = x * x; // Change x to x^2
        }
        return res % p;
    }
 
    public static void main(String[] args)
    {
        int x = 2;
        int y = 5;
        int p = 13;
 
        int mod = power(x, y, p);
        System.out.print("Power is " + mod);
    }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Iterative Function to calculate (x^y)%p in O(log y)
def power(x, y, p):
 
    # Initialize result
    res = 1
 
    while (y > 0):
 
        # If y is odd, multiply x with result
        if ((y & 1) != 0):
            res = res * x
 
        # y must be even now
        y = y >> 1  # y = y/2
        x = x * x  # Change x to x^2
 
    return res % p
 
  # Driver Code
 
 
x = 2
y = 5
p = 13
print("Power is ", power(x, y, p))
# This code is contributed by Khushboogoyal499

Javascript

<script>
/* Iterative Function to calculate (x^y) % p in O(log y) */
function power(x, y, p)
{
    let res = 1;     // Initialize result
 
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = res*x;
 
        // y must be even now
        y = y>>1; // y = y/2
        x = x*x; // Change x to x^2
    }
    return res % p;
}
 
// Driver Code
let x = 2;
let y = 5;
let p = 13;
document.write("Power is " + power(x, y, p));
 
// This code is contributed by _saurabh_jaiswal
</script>

C#

/* Iterative Function to calculate (x^y)%p in O(log y) */
using System;
class GFG {
    static int power(int x, int y, int p)
    {
        int res = 1; // Initialize result
 
        while (y > 0) {
            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = res * x;
 
            // y must be even now
            y = y >> 1; // y = y/2
            x = x * x; // Change x to x^2
        }
        return res % p;
    }
 
    // Driver Code
    static public void Main()
    {
        int x = 2;
        int y = 5;
        int p = 13;
        Console.Write("Power is " + power(x, y, p));
    }
}
 
// This code is contributed by Dharanendra L V.
Producción

Power is 6

Complejidad de tiempo: O(log 2 y), donde y representa el valor de la entrada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
 

Enfoque eficiente:

El problema con las soluciones anteriores es que puede ocurrir un desbordamiento para valores grandes de n o x. Por lo tanto, la potencia generalmente se evalúa bajo el módulo de un gran número.

A continuación se muestra la propiedad modular fundamental que se utiliza para calcular eficientemente la potencia bajo la aritmética modular. 

(ab) mod p = ( (a mod p) (b mod p) ) mod p 

For example a = 50,  b = 100, p = 13
50  mod 13  = 11
100 mod 13  = 9

(50 * 100) mod 13 = ( (50 mod 13) * (100 mod 13) ) mod 13 
or (5000) mod 13 = ( 11 * 9 ) mod 13
or 8 = 8

A continuación se muestra la implementación basada en la propiedad anterior.  

C++14

// Iterative C++ program to compute modular power
#include <iostream>
using namespace std;
 
/* Iterative Function to calculate (x^y)%p in O(log y) */
int power(long long x, unsigned int y, int p)
{
    int res = 1;     // Initialize result
 
    x = x % p; // Update x if it is more than or
                // equal to p
  
    if (x == 0) return 0; // In case x is divisible by 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;
}
 
// Driver code
int main()
{
    int x = 2;
    int y = 5;
    int p = 13;
    cout << "Power is " << power(x, y, p);
    return 0;
}
 
// This code is contributed by shubhamsingh10

Java

// Iterative Java program to compute modular power
import java.io.*;
class GFG
{
 
  /* Iterative Function to calculate (x^y) in O(log y) */
  static int power(int x, int y, int p)
  {
    int res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    if (x == 0)
      return 0; // In case x is divisible by p;
 
    while (y > 0)
    {
 
      // If y is odd, multiply x with result
      if ((y & 1) != 0)
        res = (res * x) % p;
 
      // y must be even now
      y = y >> 1; // y = y/2
      x = (x * x) % p;
    }
    return res;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int x = 2;
    int y = 5;
    int p = 13;
    System.out.print("Power is " + power(x, y, p));
  }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Iterative Python3 program
# to compute modular power
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p) :
    res = 1     # Initialize result
 
    # Update x if it is more
    # than or equal to p
    x = x % p
     
    if (x == 0) :
        return 0
 
    while (y > 0) :
         
        # If y is odd, multiply
        # x with result
        if ((y & 1) == 1) :
            res = (res * x) % p
 
        # y must be even now
        y = y >> 1      # y = y/2
        x = (x * x) % p
         
    return res
     
 
# Driver Code
 
x = 2; y = 5; p = 13
print("Power is ", power(x, y, p))
 
 
# This code is contributed by Nikita Tiwari.

C#

using System;
public class GFG
{
 
  /* Iterative Function to calculate (x^y) in O(log y) */
  static int power(int x, int y, int p)
  {
    int res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    if (x == 0)
      return 0; // In case x is divisible by p;
 
    while (y > 0)
    {
 
      // If y is odd, multiply x with result
      if ((y & 1) != 0)
        res = (res * x) % p;
 
      // y must be even now
      y = y >> 1; // y = y/2
      x = (x * x) % p;
    }
    return res;
  }
 
  // Driver Code
  static public void Main ()
  {
    int x = 2;
    int y = 5;
    int p = 13;
    Console.Write("Power is " + power(x, y, p));
  }
}
 
// This code is contributed by Dharanendra L V.

PHP

<?php
// Iterative PHP program to
// compute modular power
 
// Iterative Function to
// calculate (x^y)%p in O(log y)
function power($x, $y, $p)
{
    // Initialize result
    $res = 1;
 
    // Update x if it is more
    // than or equal to p
    $x = $x % $p;
 
    if ($x == 0)
        return 0;
 
    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/2
        $y = $y >> 1;
        $x = ($x * $x) % $p;
    }
    return $res;
}
 
// Driver Code
$x = 2;
$y = 5;
$p = 13;
echo "Power is ", power($x, $y, $p);
 
// This code is contributed by aj_36
?>

Javascript

// Iterative Javascript program to
// compute modular power
 
// 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;
 
    if (x == 0)
        return 0;
 
    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/2
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
// Driver Code
let x = 2;
let y = 5;
let p = 13;
document.write("Power is " + power(x, y, p));
 
// This code is contributed by _saurabh_jaiswal
Producción

Power is 6

Complejidad de tiempo : O(Log y), donde y representa el valor de la entrada dada.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Exponenciación modular (recursiva)
Este artículo es una contribución de Shivam Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente. 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *