Modular Exponentiation (Power in Modular Arithmetic)
Given three numbers x, y and p, compute (xy) % p.
Examples :
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.
We have discussed recursive and iterative solutions for power.
Below is discussed iterative solution.
/* Iterative Function to calculate (x^y) in O(log y) */ int power( int x, unsigned int y) { ���� int res = 1;���� // Initialize result �� ����� while (y > 0) ���� { �������� // If y is odd, multiply x with result �������� if (y & 1) ������������ res = res*x; �� ��������� // n must be even now �������� y = y>>1; // y = y/2 �������� x = x*x;� // Change x to x^2 ���� } ���� return res; } |
chevron_right
filter_none
The problem with above solutions is, overflow may occur for large value of n or x. Therefore, power is generally evaluated under modulo of a large number.
Below is the fundamental modular property that is used for efficiently computing power under modular arithmetic.
(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
Below is the implementation based on above property.
C
// Iterative C program to compute modular power #include <stdio.h> � �/* Iterative Function to calculate (x^y)%p in O(log y) */ int power( int 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 � ����� 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 program to test above functions int main() { ��� int x = 2; ��� int y = 5; ��� int p = 13; ��� printf ( "Power is %u" , power(x, y, p)); ��� return 0; } |
chevron_right
filter_none
Java
// Iterative Java program to� // compute modular power import java.io.*; � �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 & 1 )== 1 ) ���������������� res = (res * x) % p; ����� ������������� // y must be even now ������������ // y = y / 2 ������������ y = y >> 1 ;� ������������ x = (x * x) % p;� �������� } �������� return res; ���� } � ����� // Driver Program to test above functions ���� public static void main(String args[]) ���� { �������� int x = 2 ; �������� int y = 5 ; �������� int p = 13 ; �������� System.out.println( "Power is " + power(x, y, p)); ���� } } � �// This code is contributed by Nikita Tiwari. |
chevron_right
filter_none
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� � ����� 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. |
chevron_right
filter_none
C#
// Iterative C# program to� // compute modular power 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 & 1) == 1) ������������ res = (res * x) % p; � ��������� // y must be even now �������� // y = y / 2 �������� y = y >> 1;� �������� x = (x * x) % p;� ���� } ���� return res; } � �// Driver Code public static void Main() { ���� int x = 2; ���� int y = 5; ���� int p = 13; ���� System.Console.WriteLine( "Power is " +� ������������������������������ power(x, y, p)); } } � �// This code is contributed by mits |
chevron_right
filter_none
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 ;� � ����� 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 ?> |
chevron_right
filter_none
Output :
Power is 6
Time Complexity of above solution is O(Log y).
Modular exponentiation (Recursive)
This article is contributed by Shivam Agrawal. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Recommended Posts:
- Modular exponentiation (Recursive)
- Modular Division
- Modular multiplicative inverse from 1 to n
- Trick for modular division ( (x1 * x2 .... xn) / b ) mod (m)
- Modular multiplicative inverse
- How to avoid overflow in modular multiplication?
- Number of solutions to Modular Equations
- Find modular node in a linked list
- Using Chinese Remainder Theorem to Combine Modular equations
- Matrix Exponentiation
- Find Nth term (A matrix exponentiation example)
- Check if given number is a power of d where d is a power of 2
- Compute power of power k times % m
- Find power of power under mod of a prime
- Larger of a^b or b^a (a raised to power b or b raised to power a)
No comments:
Post a Comment