C program to find Modular Multiplicative Inverse of two Relatively Prime Numbers

In this article, we will learn how to create a program to calculate Inverse Modulo or Modular Multiplicative Inverse of two relatively prime numbers in C programming language but first, let us understand what is Inverse modulo.

The Modular Multiplicative Inverse is an integer ‘x’ such that

Also Read: Binary Search Program in C using Recursion

a x = 1 mod n

or you can represent the above equation as.

x = (a^-1)modn

The multiplicative inverse will only exist if a and m are relatively prime (if gcd(a,n)==1). Now let’s see the pseudo code to calculate Inverse Modulo of a and n where a and n are relatively prime.

solving for imod  where,  imod = (a^-1)modn  1. let i = 0 2. calculate x = n * i + 1 3. if x mod a == 0    imod = x/a(quotient)    goto step 7 5. i = i + 1 6. goto step 2 7. exit

We have the steps to calculate Modular Multiplicative Inverse/ Inverse Modulo now let’s code a C function for the above pseudo code.

int imod(int a,int n){ int c,i=1; while(1){ c = n * i + 1; if(c\%a==0){ c = c/a; break; } i++; } return c; }

In the above code, we have declared two variable c(the imod variable) and i then we are calculating (n * i + 1) and storing it in variable c in a condition based loop which will break out when it will find a number which will completely divide the value stored in variable c and the quotient of the performed division operation will be our inverse mod of a and n.

Now we need to check if the numbers entered by the user are relatively prime or not for that we are going to write a GCD function for validation.

int gcd(int a, int n){ int gcd, i; for(i=1; i <= a && i <= n; ++i){ if(a\%i==0 && n\%i==0) gcd = i; } return gcd; }

Now let’s write the driver function and complete our program.

Modular Multiplicative Inverse program in C

#include<stdio.h>  int gcd(int a, int n){ int gcd, i; for(i=1; i <= a && i <= n; ++i){ if(a\%i==0 && n\%i==0) gcd = i; } return gcd; }  int imod(int a,int n){ int c,i=1; while(1){ c = n * i + 1; if(c\%a==0){ c = c/a; break; } i++; } return c; }  int main(){ int a,n,mod; printf("Enter the value of a and n: "); scanf("\%d\%d",&a,&n); if (gcd(a,n)==1) printf("The Modular Multiplicative Inverse is: \%d",imod(a,n)); else printf("The numbers are not relatively prime."); return 0;  }

Output:

Enter the value of a and n: 343 158400 The Modular Multiplicative Inverse is: 12007 

Thank you for reading the article.

Special Thanks to Ashish Ghadi for providing the steps to calculate Modular Multiplicative Inverse.


Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями:
Добавить комментарий