From 0a5d0bc7225e8abcab0519447a82d87c6d05884a Mon Sep 17 00:00:00 2001
From: mdw <mdw>
Date: Sun, 12 Dec 1999 15:08:52 +0000
Subject: [PATCH] Don't bother shifting %$q$% in @mpbarrett_reduce@, just skip
 the least significant digits.

---
 mpbarrett.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/mpbarrett.c b/mpbarrett.c
index 025d4e4..711b7ab 100644
--- a/mpbarrett.c
+++ b/mpbarrett.c
@@ -1,6 +1,6 @@
 /* -*-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
  *
@@ -30,6 +30,10 @@
 /*----- 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.
  *
@@ -124,7 +128,11 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m)
     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 --- */
@@ -139,7 +147,7 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m)
     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);
-- 
2.11.0