X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/5bda60bd9209028aa3db06bccd7c708a1d3a9c5e..578a86d91941a0f722b87973d88e84ec2cf9a608:/mpcrt.c

diff --git a/mpcrt.c b/mpcrt.c
index 51d9b68..c79b00b 100644
--- a/mpcrt.c
+++ b/mpcrt.c
@@ -1,6 +1,6 @@
 /* -*-c-*-
  *
- * $Id: mpcrt.c,v 1.2 1999/12/10 23:22:32 mdw Exp $
+ * $Id: mpcrt.c,v 1.6 2004/04/08 01:36:15 mdw Exp $
  *
  * Chinese Remainder Theorem computations (Gauss's algorithm)
  *
@@ -27,21 +27,11 @@
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: mpcrt.c,v $
- * Revision 1.2  1999/12/10 23:22:32  mdw
- * Interface changes for suggested destinations.  Use Barrett reduction.
- *
- * Revision 1.1  1999/11/22 20:50:57  mdw
- * Add support for solving Chinese Remainder Theorem problems.
- *
- */
-
 /*----- Header files ------------------------------------------------------*/
 
 #include "mp.h"
 #include "mpcrt.h"
+#include "mpmul.h"
 #include "mpbarrett.h"
 
 /*----- Main code ---------------------------------------------------------*/
@@ -79,9 +69,11 @@ void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
   if (n != MP_NEW)
     n = MP_COPY(n);
   else {
-    n = MP_COPY(v[0].m);
-    for (i = 1; i < k; i++)
-      n = mp_mul(n, n, v[i].m);
+    mpmul mm;
+    mpmul_init(&mm);
+    for (i = 0; i < k; i++)
+      mpmul_add(&mm, v[i].m);
+    n = mpmul_done(&mm);
   }
 
   /* --- A quick hack if %$k = 2$% --- */
@@ -101,7 +93,10 @@ void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
      */
 
     if (!v[0].ni && !v[1].ni) {
-      mp_gcd(0, &v[0].ni, &v[1].ni, v[0].n, v[1].n);
+      mp *g = MP_NEW;
+      mp_gcd(&g, &v[0].ni, &v[1].ni, v[0].n, v[1].n);
+      assert(MP_EQ(g, MP_ONE));
+      mp_drop(g);
       v[0].ni = mp_add(v[0].ni, v[0].ni, v[1].n);
     } else {
       int i, j;
@@ -129,7 +124,7 @@ void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
     if (!v[i].n)
       mp_div(&v[i].n, 0, n, v[i].m);
     if (!v[i].ni)
-      mp_gcd(0, &v[i].ni, 0, v[i].n, v[i].m);
+      v[i].ni = mp_modinv(MP_NEW, v[i].n, v[i].m);
     if (!v[i].nni)
       v[i].nni = mp_mul(MP_NEW, v[i].n, v[i].ni);
   }
@@ -223,7 +218,7 @@ static int verify(size_t n, dstr *v)
   mpcrt_create(&c, m, n, 0);
   b = mpcrt_solve(&c, MP_NEW, r);
 
-  if (MP_CMP(a, !=, b)) {
+  if (!MP_EQ(a, b)) {
     fputs("\n*** failed\n", stderr);
     fputs("n = ", stderr);
     mp_writefile(c.mb.m, stderr, 10);