DZone 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

Snippets has posted 5883 posts at DZone. View Full User Profile

Modular Inverse Function

07.04.2007
| 14384 views |
  • submit to reddit
        This function calculates & returns the inverse of <I>a modulo n</I>, 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;
}
    

Comments

Snippets Manager replied on Sat, 2011/07/16 - 3:16am

Its great code.. Actually i was trying it fro last full 3 days and nights..its helps me...

Snippets Manager replied on Mon, 2010/12/13 - 5:00pm

oh, thank you! it's really useful source code for really lazy me ^^ and it's worth it to log in just to say Thank You from russia with love :)

Snippets Manager replied on Sun, 2009/09/20 - 12:35am

Thank you so muchhhhhhh!!!! I created an account just to say thanks for this ;)