cinvmod

[Bill Allombert <allomber@math.u-bordeaux.fr>]

Hello pari-dev,

Here a patch that add a cinvmod front-end to xgcduu,
similar to cgcd and clcm, that compute the modular inverse
of a mod b.

It could be argued that the name sould be 
gcdss, lcmss and invmodss to better fit with the
general naming convention of kernel routine.

Cheers,
Bill.

Index: src/kernel/none/gcdll.c
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/kernel/none/gcdll.c,v
retrieving revision 1.4
diff -u -r1.4 gcdll.c
--- src/kernel/none/gcdll.c	2003/04/22 09:01:02	1.4
+++ src/kernel/none/gcdll.c	2003/06/03 12:57:58
@@ -1049,3 +1049,31 @@
 
   return res;
 }
+
+/*  x<m */
+ulong uinvmod(ulong x, ulong m)
+{
+  ulong xv,xv1; 
+  long s;
+  ulong d=xgcduu(m, x, 1, &xv, &xv1, &s);
+  if (d!=1UL)
+    err(invmoder,"%Z",gmodulss(d,m));
+  xv = xv1 % m; if (s < 0) xv = m - xv;
+  return xv;
+}
+
+long
+cinvmod(long a,long m)
+{
+  m=labs(m);
+  if (a>=0)
+  {
+   if (a>m) a %= m;
+  }
+  else
+  {
+   if (-a>m) a %= m;
+   a+=m;
+  }
+  return ((long)uinvmod((ulong)a, (ulong)m));
+}