modInverse.c

C

Public Domain

Calculate the multiplicative inverse of a modulo n

Download (right click, save as, rename as appropriate)

Embed

       

Tags:

C inverse math modular modulo modulus reciprocal 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int modInverse(int a, int n) {
 int i=n, h=a, v=0, d=1;
 while (h>0) {
  int t = i/h, x=h;
  h = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 }
 v %= n;
 if (v<0) v = (v+n) % n;
 return v;
}