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

  • 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;


Snippets Manager replied on Sat, 2011/07/16 - 2: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 - 4: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 Sat, 2009/09/19 - 11:35pm

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