Invert a number mod N

[tition]

Dear all, I need to invert numbers mod N - the faster the better. I would appreciate any comments on the below code.

To invert a number X mod N means to find a number Y such that there is some number A for which X*Y = A*N+1. This is only possible if X and N are relatively prime (that is, they do not have a common divisor).

#include <iostream>
#include <assert.h>
// Uses Euclidean algorithm to invert X mod N
int InvertModN( int X, int N)
{ static int q,r,p,d; // d - divisor, q - quotient, r - remainder, 
// p is the number to be divided
  static int vD[2],vP[2], temp;
  vP[0]=1; vP[1]=0;// at any given moment, p=vP[0]*N+vP[1]*X
  vD[0]=0; vD[1]=1;// at any given momoent, d=vD[0]*N+vD[1]*X
  p=N; d=X;
  while (d>0)
  { q=p/d;
    r=p%d;
    p=d;
    d=r;
    for(int i=0;i<2;i++)
    { temp=vP[i];
      vP[i]= vD[i];
      vD[i]= temp-q*vD[i];
    }
  }
  assert(p==1);//if d and p were relatively prime this should be so. 
               //Otherwise the function was not called properly.
  return (vP[1]%N);
}
int _tmain(int argc, _TCHAR* argv[])
{ std::cout << InvertModN(67,100);
  int x;
  std::cin>>x;
  return 0;
}

Another question related to my work, do you know of any library offering Gaussian elimination (a.k.a. "row-echelon form") for matrices mod N, where N is not prime? The matrices are integer valued, of course. Thanks for your comments!

[rachitagrawal]

well what you are trying to do is the galois field arithmatic if i m not wrong and there are some libraries available to do all the arithmetic in galois field. google it you will find it.

And if language is not a constraint, I would suggest do gaussian elimination and all in Mathematica. Even the inverse thing, you can do in mathematica. You have functions for both of this operation.

[tition]

The language is a constraint, although probably less so than the functionality of Mathematica.

No, I am not computing anything in galois fields. Actually, I am not aware of any direct connection between galois field and gaussian elimination mod N. An example of a reduced wrt. Gaussian elimination matrix would be

2 1 
0 2

mod 6, since you cannot divide the last row by 2 to cancel out the one in the first row.

PS. I just realized that Gaussian elimination is sometimes studied as "putting a matrix in row-echelon form" by the more applied majors!