/* -*-c-*-
*
- * $Id: mpbarrett.c,v 1.1 1999/12/10 23:21:59 mdw Exp $
+ * $Id: mpbarrett.c,v 1.3 1999/12/12 15:08:52 mdw Exp $
*
* Barrett modular reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett.c,v $
+ * Revision 1.3 1999/12/12 15:08:52 mdw
+ * Don't bother shifting %$q$% in @mpbarrett_reduce@, just skip the least
+ * significant digits.
+ *
+ * Revision 1.2 1999/12/11 01:50:56 mdw
+ * Improve initialization slightly.
+ *
* Revision 1.1 1999/12/10 23:21:59 mdw
* Barrett reduction support: works with even moduli.
*
mp_shrink(m);
mb->k = MP_LEN(m);
mb->m = MP_COPY(m);
- b = mp_lsl(MP_NEW, MP_ONE, 2 * MPW_BITS * mb->k);
+ b = mp_create(2 * mb->k + 1);
+ MPX_ZERO(b->v, b->vl - 1);
+ b->vl[-1] = 1;
mp_div(&b, 0, b, m);
mb->mu = b;
}
mp qq;
mp_build(&qq, m->v + (k - 1), m->vl);
q = mp_mul(MP_NEW, &qq, mb->mu);
- q = mp_lsr(q, q, MPW_BITS * (k + 1));
+ if (MP_LEN(q) <= k) {
+ m = MP_COPY(m);
+ MP_DROP(d);
+ return (m);
+ }
}
/* --- Second stage --- */
else
mvl = m->v + k + 1;
r = mp_create(k + 1);
- mpx_umul(r->v, r->vl, q->v, q->vl, mb->m->v, mb->m->vl);
+ mpx_umul(r->v, r->vl, q->v + k + 1, q->vl, mb->m->v, mb->m->vl);
r->f = (q->f | mb->m->f) & MP_BURN;
MP_MODIFY(d, k + 1);
mpx_usub(d->v, d->vl, m->v, mvl, r->v, r->vl);