Modular multiplicative inverse

Mahmudul Hasan November 23, 2020 0

1. When a and m are co-PRIME:

#include<bits/stdc++.h>
using namespace std;
int extdGcd(int a,int b, int* x,int* y)
{
    if(a==0)
    {
        *x=0, *y=1;
        return b;
    }

    int x1,y1;

    int gcd=extdGcd(b%a,a,&x1,&y1);

    *x=y1-(b/a)*x1;
    *y=x1;

    return gcd;

}




void InverseMod(int a,int m)
{
    int x,y;

    int g= extdGcd(a,m,&x,&y);

    if(g!=1)
    {
        printf("Modular Multiplicative Inverse doesn't exist.\n");
    } 
    else
    {
        int inv=(x%m+m)%m;
        printf("Modular Multiplicative Inverse is: %d\n",inv);
    }
    
}



int main()
{
    int a,m;
    scanf("%d %d",&a,&m);
    InverseMod(a,m);

    return 0;
}

2. When m is PRIME(Using FLT):

 #include<bits/stdc++.h>
using namespace std;

int gcd(int n,int m)
{
    if(n==0) return m;

    return gcd(m%n,n);
}

int bigMod(int x,int y,int m)
{
    if(y==0) return 1;
    
    if(y&1)
    {
        int p1=x%m;
        int p2=bigMod(x,y-1,m);

        return (p1*p2)%m;
    }
    else
    {
        int h1=bigMod(x,y/2,m);
        return (h1*h1)%m;
    }
    

}



void InverseMod(int n,int m)
{

  int g= gcd(n,m);
  if(g!=1)
    cout<<"Inverse doesn't exist.\n";

  else
  {
      cout<<"Modular Multiplicative Inverse is:"<<bigMod(n,m-2,m)<<endl;
  }

}







int main()
{
    int t;

    cin>>t;

    while(t--)
    {
        int n,m;
        cin>>n>>m;

        InverseMod(n,m);
    }

    return 0;
}

No comments

Subscribe to: Post Comments ( Atom )