/* -*-c-*-
*
- * $Id: mpbarrett.c,v 1.4 2000/06/17 11:45:09 mdw Exp $
+ * $Id: mpbarrett.c,v 1.5 2000/07/29 17:04:33 mdw Exp $
*
* Barrett modular reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett.c,v $
+ * Revision 1.5 2000/07/29 17:04:33 mdw
+ * Change to use left-to-right bitwise exponentiation. This will improve
+ * performance when the base is small.
+ *
* Revision 1.4 2000/06/17 11:45:09 mdw
* Major memory management overhaul. Added arena support. Use the secure
* arena for secret integers. Replace and improve the MP management macros
{
mpscan sc;
mp *x = MP_ONE;
- mp *spare = MP_NEW;
+ mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
+ unsigned sq = 0;
a = MP_COPY(a);
- mp_scan(&sc, e);
- if (e->f & MP_BURN)
- spare = MP_NEWSEC;
- if (MP_STEP(&sc)) {
- size_t sq = 0;
+ mp_rscan(&sc, e);
+ if (!MP_RSTEP(&sc))
+ goto exit;
+ while (!MP_RBIT(&sc))
+ MP_RSTEP(&sc);
+
+ /* --- Do the main body of the work --- */
+
+ for (;;) {
+ sq++;
+ while (sq) {
+ mp *y;
+ y = mp_sqr(spare, x);
+ y = mpbarrett_reduce(mb, y, y);
+ spare = x; x = y;
+ sq--;
+ }
+ {
+ mp *y = mp_mul(spare, x, a);
+ y = mpbarrett_reduce(mb, y, y);
+ spare = x; x = y;
+ }
for (;;) {
- mp *dd;
- if (MP_BIT(&sc)) {
- while (sq) {
- dd = mp_sqr(spare, a);
- dd = mpbarrett_reduce(mb, dd, dd);
- spare = a; a = dd;
- sq--;
- }
- dd = mp_mul(spare, x, a);
- dd = mpbarrett_reduce(mb, dd, dd);
- spare = x; x = dd;
- }
+ if (!MP_RSTEP(&sc))
+ goto done;
+ if (MP_RBIT(&sc))
+ break;
sq++;
- if (!MP_STEP(&sc))
- break;
}
}
+ /* --- Do a final round of squaring --- */
+
+done:
+ while (sq) {
+ mp *y;
+ y = mp_sqr(spare, x);
+ y = mpbarrett_reduce(mb, y, y);
+ spare = x; x = y;
+ sq--;
+ }
+
+exit:
MP_DROP(a);
if (spare != MP_NEW)
MP_DROP(spare);