X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/22bab86c9df047bdd258283c6567821319ba7a6f..2a7c52031aa0096b4f20ec1dd72e5f6e08a19aa9:/mpcrt.c

diff --git a/mpcrt.c b/mpcrt.c
index de61d4b..bf6459f 100644
--- a/mpcrt.c
+++ b/mpcrt.c
@@ -1,13 +1,13 @@
 /* -*-c-*-
  *
- * $Id: mpcrt.c,v 1.3 2000/10/08 12:11:22 mdw Exp $
+ * $Id$
  *
  * Chinese Remainder Theorem computations (Gauss's algorithm)
  *
  * (c) 1999 Straylight/Edgeware
  */
 
-/*----- Licensing notice --------------------------------------------------* 
+/*----- Licensing notice --------------------------------------------------*
  *
  * This file is part of Catacomb.
  *
@@ -15,36 +15,23 @@
  * it under the terms of the GNU Library General Public License as
  * published by the Free Software Foundation; either version 2 of the
  * License, or (at your option) any later version.
- * 
+ *
  * Catacomb is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU Library General Public License for more details.
- * 
+ *
  * You should have received a copy of the GNU Library General Public
  * License along with Catacomb; if not, write to the Free
  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  * MA 02111-1307, USA.
  */
 
-/*----- Revision history --------------------------------------------------* 
- *
- * $Log: mpcrt.c,v $
- * Revision 1.3  2000/10/08 12:11:22  mdw
- * Use @MP_EQ@ instead of @MP_CMP@.
- *
- * 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 ---------------------------------------------------------*/
@@ -82,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$% --- */
@@ -104,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;
@@ -114,7 +106,7 @@ void mpcrt_create(mpcrt *c, mpcrt_mod *v, size_t k, mp *n)
 	i = 0, j = 1;
       else
 	i = 1, j = 0;
-      
+
       x = mp_mul(MP_NEW, v[j].n, v[j].ni);
       x = mp_sub(x, x, MP_ONE);
       mp_div(&x, 0, x, v[i].n);
@@ -132,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);
   }
@@ -253,8 +245,8 @@ static int verify(size_t n, dstr *v)
   mp_drop(a);
   mp_drop(b);
   mpcrt_destroy(&c);
-  free(m);
-  free(r);
+  xfree(m);
+  xfree(r);
   assert(mparena_count(MPARENA_GLOBAL) == 0);
   return (ok);
 }