Merge pull request #33 from roopbiswas/patch1

abranhe · web-flow · commit 99fe7f9fbb71 · 2018-10-07T23:46:11.000-04:00
Create modular_exponentiation.cpp
diff --git a/math/modular_exponentiation.cpp b/math/modular_exponentiation.cpp
@@ -0,0 +1,35 @@
+// modular exponentiation implemented in C++
+//Author : Rituparno Biswas
+
+//Given three numbers x, y and p, compute (power(x,y)) % p. where power(a,b) calculates a to power of b 
+
+
+#include<bits/stdc++.h>
+using namespace std;
+
+typedef long long int ll;
+
+ll power(ll x, ll y, ll p)
+{
+	if(x==0)
+		return 0;
+	if(y==0)
+		return 1;
+	if (y%2==0)
+	{
+		ll g=power(x,y/2,p);
+		return (g*g)%p;
+	}
+	else
+	{
+		ll g=power(x,y/2,p);
+		return (x*(g*g)%p)%p;
+	}
+}
+
+int main() 
+{ 
+   ll x = 2,y = 5, p = 13; 
+   printf("Power is %lld", power(x, y, p)); 
+   return 0; 
+} 
