/* -*-c-*-
*
- * $Id: gf-gcd.c,v 1.3 2004/04/08 01:36:15 mdw Exp $
+ * $Id$
*
* Euclidian algorithm on binary polynomials
*
return;
}
- /* --- Take a reference to the arguments --- */
-
- a = MP_COPY(a);
- b = MP_COPY(b);
-
- /* --- Make sure @a@ and @b@ are not both even --- */
-
- MP_SPLIT(a); a->f &= ~MP_NEG;
- MP_SPLIT(b); b->f &= ~MP_NEG;
+ /* --- Main extended Euclidean algorithm --- */
u = MP_COPY(a);
v = MP_COPY(b);
- while (MP_LEN(v)) {
+ while (!MP_ZEROP(v)) {
mp *t;
gf_div(&q, &u, u, v);
if (f & f_ext) {
t = gf_mul(MP_NEW, X, q);
- t = gf_add(t, x, t);
+ t = gf_add(t, t, x);
MP_DROP(x); x = X; X = t;
t = gf_mul(MP_NEW, Y, q);
- t = gf_add(t, y, t);
+ t = gf_add(t, t, y);
MP_DROP(y); y = Y; Y = t;
}
t = u; u = v; v = t;
MP_DROP(v);
MP_DROP(X); MP_DROP(Y);
- MP_DROP(a); MP_DROP(b);
}
/* -- @gf_modinv@ --- *