Never been to DZone Snippets before?

Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS 

Modular inverse function

This function calculates & returns the inverse of a modulo n, both of which should be positive. If the inverse does not exist, 0 is returned. If you don't know what this means, don't bother.
int modInverse(int a, int n) {
 int i = n, v = 0, d = 1;
 while (a>0) {
  int t = i/a, x = a;
  a = i % x;
  i = x;
  x = d;
  d = v - t*x;
  v = x;
 }
 v %= n;
 if (v<0) v = (v+n)%n;
 return v;
}
to c math modulus by Minimiscience on Jul 04, 2007
« Newer Snippets
Older Snippets »
Showing 1-1 of 1 total  RSS