/* -*-c-*-
*
- * $Id: mpcrt.c,v 1.4 2001/04/19 18:25:38 mdw Exp $
+ * $Id$
*
* Chinese Remainder Theorem computations (Gauss's algorithm)
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
* 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.4 2001/04/19 18:25:38 mdw
- * Use mpmul for the multiplication.
- *
- * 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"
else {
mpmul mm;
mpmul_init(&mm);
- n = MP_COPY(v[0].m);
for (i = 0; i < k; i++)
mpmul_add(&mm, v[i].m);
n = mpmul_done(&mm);
*/
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;
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);
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);
}
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);
}