Algoritmo extendido de Euclides

Haciendo algunos ejercicios criptográficos tenía que firmar digitalmente con elGamal los mensajes a enviar y para ello necesitaba calculo el inverso de a módulo n, así que:

os dejo un algoritmo para encontrar el inverso de a módulo n cuando mcd(a,n)=1.

     /// <summary>  
     /// Algoritmo extendido de Euclides   
     /// </summary>  
     /// <returns>devuelve x tal que ax mod n=1, donde "0<a<n" ></returns>  
     static private int algoritmo(int a, int n)  
     {  
       List<int> g=new List<int>();  
       g.Add(n); g.Add(a);  
       List<int> u = new List<int>();  
       List<int> v = new List<int>();  
       u.Add(1); v.Add(0);  
       u.Add(0); v.Add(1);  
       int i = 1;  
       while (g[i] != 0)  
       {  
         //g[i] = u[i] * n + v[i] * a;  
         int y = g[i - 1] / g[i];  
         g.Add(g[i - 1] - y * g[i]);  
         u.Add(u[i - 1] - y * u[i]);  
         v.Add(v[i - 1] - y * v[i]);  
         i++;  
       }  
       int x = v[i - 1];  
       if (x > 0)  
       { return x; }  
       else { return x + n; }  
     }