/* -*-c-*-
*
- * $Id: mpbarrett.c,v 1.2 1999/12/11 01:50:56 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.
*
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);