/* -*-c-*-
*
- * $Id: mpcrt.c,v 1.2 1999/12/10 23:22:32 mdw Exp $
+ * $Id$
*
* Chinese Remainder Theorem computations (Gauss's algorithm)
*
* 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 ---------------------------------------------------------*/
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$% --- */
*/
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;
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);
}
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);
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);
}