Skip to content

Instantly share code, notes, and snippets.

@onkar27
Created April 1, 2018 17:31
Show Gist options
  • Save onkar27/1a6a3ec7502c7adca5ef6581470a8f0e to your computer and use it in GitHub Desktop.
Save onkar27/1a6a3ec7502c7adca5ef6581470a8f0e to your computer and use it in GitHub Desktop.
Greatest Common Divisor + Power + Inverse Modulo
ll modularExponentiation(ll x,ll n,ll M)
{
ll result=1;
while(n>0)
{
if(n % 2 ==1)
result=(result * x)%M;
x=(x*x)%M;
n=n/2;
}
return result;
}
ll d, x, y;
void extendedEuclid(ll A, ll B) {
if(B == 0) {
d = A;
x = 1;
y = 0;
}
else {
extendedEuclid(B, A%B);
ll temp = x;
x = y;
y = temp - (A/B)*y;
}
}
ll modInverse(ll A, ll M)
{
extendedEuclid(A,M);
return (x%M+M)%M; //x may be negative
}
int main( ) {
extendedEuclid(16, 10);
cout << ”The GCD of 16 and 10 is ” << d << endl;
cout << ”Coefficients x and y are ”<< x << “and “ << y << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment