/* -*-c-*-
*
- * $Id: mpmont.c,v 1.2 1999/11/19 13:17:26 mdw Exp $
+ * $Id: mpmont.c,v 1.3 1999/11/21 11:35:10 mdw Exp $
*
* Montgomery reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont.c,v $
+ * Revision 1.3 1999/11/21 11:35:10 mdw
+ * Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
+ * @mpmont_mul@ for squaring in exponentiation.
+ *
* Revision 1.2 1999/11/19 13:17:26 mdw
* Add extra interface to exponentiation which returns a Montgomerized
* result.
n = MP_LEN(mm->m);
if (d == a)
- MP_MODIFY(d, 2 * n);
+ MP_MODIFY(d, 2 * n + 1);
else {
- MP_MODIFY(d, 2 * n);
+ MP_MODIFY(d, 2 * n + 1);
memcpy(d->v, a->v, MPWS(MP_LEN(a)));
memset(d->v + MP_LEN(a), 0, MPWS(MP_LEN(d) - MP_LEN(a)));
}
mp *dd;
if (MP_BIT(&sc)) {
while (sq) {
- dd = mpmont_mul(mm, spare, ar, ar);
+ dd = mp_sqr(spare, ar);
+ dd = mpmont_reduce(mm, dd, dd);
spare = ar; ar = dd;
sq--;
}
mp *a = *(mp **)v[1].buf;
mp *b = *(mp **)v[2].buf;
mp *r = *(mp **)v[3].buf;
- mp *mr, *qr;
int ok = 1;
mpmont mm;
mpmont_create(&mm, m);
{
+ mp *qr = mp_mul(MP_NEW, a, b);
+ mp_div(0, &qr, qr, m);
+
+ if (MP_CMP(qr, !=, r)) {
+ fputs("\n*** classical modmul failed", stderr);
+ fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+ fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+ fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
+ fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+ fputs("\nqr = ", stderr); mp_writefile(qr, stderr, 10);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(qr);
+ }
+
+ {
mp *ar = mpmont_mul(&mm, MP_NEW, a, mm.r2);
mp *br = mpmont_mul(&mm, MP_NEW, b, mm.r2);
- mr = mpmont_mul(&mm, MP_NEW, ar, br);
+ mp *mr = mpmont_mul(&mm, MP_NEW, ar, br);
mr = mpmont_reduce(&mm, mr, mr);
+ if (MP_CMP(mr, !=, r)) {
+ fputs("\n*** montgomery modmul failed", stderr);
+ fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+ fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+ fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
+ fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+ fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
+ fputc('\n', stderr);
+ ok = 0;
+ }
MP_DROP(ar); MP_DROP(br);
+ mp_drop(mr);
}
- qr = mp_mul(MP_NEW, a, b);
- mp_div(0, &qr, qr, m);
-
- if (MP_CMP(qr, !=, r)) {
- fputs("\n*** classical modmul failed", stderr);
- fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
- fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
- fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
- fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
- fputs("\nqr = ", stderr); mp_writefile(qr, stderr, 10);
- fputc('\n', stderr);
- ok = 0;
- }
-
- if (MP_CMP(mr, !=, r)) {
- fputs("\n*** montgomery modmul failed", stderr);
- fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
- fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
- fputs("\n b = ", stderr); mp_writefile(b, stderr, 10);
- fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
- fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
- fputc('\n', stderr);
- ok = 0;
- }
MP_DROP(m);
MP_DROP(a);
MP_DROP(b);
MP_DROP(r);
- MP_DROP(mr);
- MP_DROP(qr);
mpmont_destroy(&mm);
return ok;
}