X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/d34decd2b2b88240cf4ca68a2a5feb7bf36de6e7..c65df27983057ec76ed0e72bb370f9a5ae7dad28:/mpmont.c diff --git a/mpmont.c b/mpmont.c index e7b9bb7..39f51ed 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpmont.c,v 1.9 2000/06/17 11:45:09 mdw Exp $ + * $Id: mpmont.c,v 1.19 2004/04/08 01:36:15 mdw Exp $ * * Montgomery reduction * @@ -27,45 +27,6 @@ * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: mpmont.c,v $ - * Revision 1.9 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 - * (e.g., replace MP_MODIFY by MP_DEST). - * - * Revision 1.8 1999/12/22 15:55:00 mdw - * Adjust Karatsuba parameters. - * - * Revision 1.7 1999/12/11 01:51:14 mdw - * Use a Karatsuba-based reduction for large moduli. - * - * Revision 1.6 1999/12/10 23:18:39 mdw - * Change interface for suggested destinations. - * - * Revision 1.5 1999/11/22 13:58:40 mdw - * Add an option to disable Montgomery reduction, so that performance - * comparisons can be done. - * - * Revision 1.4 1999/11/21 12:27:06 mdw - * Remove a division from the Montgomery setup by calculating - * %$R^2 \bmod m$% first and then %$R \bmod m$% by Montgomery reduction of - * %$R^2$%. - * - * 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. - * - * Revision 1.1 1999/11/17 18:02:16 mdw - * New multiprecision integer arithmetic suite. - * - */ - /*----- Header files ------------------------------------------------------*/ #include "mp.h" @@ -81,7 +42,7 @@ /* #define MPMONT_DISABLE */ -/*----- Main code ---------------------------------------------------------*/ +/*----- Reduction and multiplication --------------------------------------*/ /* --- @mpmont_create@ --- * * @@ -113,15 +74,9 @@ void mpmont_create(mpmont *mm, mp *m) mp *r2 = mp_new(2 * n + 1, 0); mp r; - /* --- Validate the arguments --- */ - - assert(((void)"Montgomery modulus must be positive", - (m->f & MP_NEG) == 0)); - assert(((void)"Montgomery modulus must be odd", m->v[0] & 1)); - /* --- Take a copy of the modulus --- */ - mp_shrink(m); + assert(MP_ISPOS(m) && MP_ISODD(m)); mm->m = MP_COPY(m); /* --- Determine %$R^2$% --- */ @@ -133,8 +88,7 @@ void mpmont_create(mpmont *mm, mp *m) /* --- Find the magic value @mi@ --- */ mp_build(&r, r2->v + n, r2->vl); - mm->mi = MP_NEW; - mp_gcd(0, 0, &mm->mi, &r, m); + mm->mi = mp_modinv(MP_NEW, m, &r); mm->mi = mp_sub(mm->mi, &r, mm->mi); /* --- Discover the values %$R \bmod m$% and %$R^2 \bmod m$% --- */ @@ -190,7 +144,7 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Check for serious Karatsuba reduction --- */ - if (n > KARATSUBA_CUTOFF * 3) { + if (n > MPK_THRESH * 3) { mp al; mpw *vl; mp *u; @@ -241,8 +195,12 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) memmove(d->v, d->v + n, MPWS(MP_LEN(d) - n)); d->vl -= n; - if (MP_CMP(d, >=, mm->m)) - d = mp_sub(d, d, mm->m); + if (MPX_UCMP(d->v, d->vl, >=, mm->m->v, mm->m->vl)) + mpx_usub(d->v, d->vl, d->v, d->vl, mm->m->v, mm->m->vl); + if (d->f & MP_NEG) { + mpx_usub(d->v, d->vl, mm->m->v, mm->m->vl, d->v, d->vl); + d->f &= ~MP_NEG; + } MP_SHRINK(d); return (d); } @@ -271,7 +229,7 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) { - if (mm->n > KARATSUBA_CUTOFF * 3) { + if (mm->n > MPK_THRESH * 3) { d = mp_mul(d, a, b); d = mpmont_reduce(mm, d, d); } else { @@ -326,10 +284,12 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) memmove(d->v, dv, MPWS(dvl - dv)); d->vl -= dv - d->v; + if (MPX_UCMP(d->v, d->vl, >=, mm->m->v, mm->m->vl)) + mpx_usub(d->v, d->vl, d->v, d->vl, mm->m->v, mm->m->vl); + if ((a->f ^ b->f) & MP_NEG) + mpx_usub(d->v, d->vl, mm->m->v, mm->m->vl, d->v, d->vl); MP_SHRINK(d); d->f = (a->f | b->f) & MP_BURN; - if (MP_CMP(d, >=, mm->m)) - d = mp_sub(d, d, mm->m); MP_DROP(a); MP_DROP(b); } @@ -339,69 +299,6 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) #endif -/* --- @mpmont_expr@ --- * - * - * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context - * @mp *d@ = fake destination - * @mp *a@ = base - * @mp *e@ = exponent - * - * Returns: Result, %$a^e R \bmod m$%. - */ - -mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e) -{ - mpscan sc; - mp *ar = mpmont_mul(mm, MP_NEW, a, mm->r2); - mp *x = MP_COPY(mm->r); - mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW; - - mp_scan(&sc, e); - - if (MP_STEP(&sc)) { - size_t sq = 0; - for (;;) { - mp *dd; - if (MP_BIT(&sc)) { - while (sq) { - dd = mp_sqr(spare, ar); - dd = mpmont_reduce(mm, dd, dd); - spare = ar; ar = dd; - sq--; - } - dd = mpmont_mul(mm, spare, x, ar); - spare = x; x = dd; - } - sq++; - if (!MP_STEP(&sc)) - break; - } - } - MP_DROP(ar); - if (spare != MP_NEW) - MP_DROP(spare); - if (d != MP_NEW) - MP_DROP(d); - return (x); -} - -/* --- @mpmont_exp@ --- * - * - * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context - * @mp *d@ = fake destination - * @mp *a@ = base - * @mp *e@ = exponent - * - * Returns: Result, %$a^e \bmod m$%. - */ - -mp *mpmont_exp(mpmont *mm, mp *d, mp *a, mp *e) -{ - d = mpmont_expr(mm, d, a, e); - d = mpmont_reduce(mm, d, d); - return (d); -} - /*----- Test rig ----------------------------------------------------------*/ #ifdef TEST_RIG @@ -426,7 +323,7 @@ static int tcreate(dstr *v) ok = 0; } - if (MP_CMP(mm.r, !=, r)) { + if (!MP_EQ(mm.r, r)) { fputs("\n*** bad r", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r, stderr, 10); @@ -435,7 +332,7 @@ static int tcreate(dstr *v) ok = 0; } - if (MP_CMP(mm.r2, !=, r2)) { + if (!MP_EQ(mm.r2, r2)) { fputs("\n*** bad r2", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r2, stderr, 10); @@ -468,7 +365,7 @@ static int tmul(dstr *v) mp *qr = mp_mul(MP_NEW, a, b); mp_div(0, &qr, qr, m); - if (MP_CMP(qr, !=, r)) { + if (!MP_EQ(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); @@ -487,7 +384,7 @@ static int tmul(dstr *v) mp *br = mpmont_mul(&mm, MP_NEW, b, mm.r2); mp *mr = mpmont_mul(&mm, MP_NEW, ar, br); mr = mpmont_reduce(&mm, mr, mr); - if (MP_CMP(mr, !=, r)) { + if (!MP_EQ(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); @@ -511,46 +408,9 @@ static int tmul(dstr *v) return ok; } -static int texp(dstr *v) -{ - mp *m = *(mp **)v[0].buf; - mp *a = *(mp **)v[1].buf; - mp *b = *(mp **)v[2].buf; - mp *r = *(mp **)v[3].buf; - mp *mr; - int ok = 1; - - mpmont mm; - mpmont_create(&mm, m); - - mr = mpmont_exp(&mm, MP_NEW, a, b); - - if (MP_CMP(mr, !=, r)) { - fputs("\n*** montgomery modexp failed", stderr); - fputs("\n m = ", stderr); mp_writefile(m, stderr, 10); - fputs("\n a = ", stderr); mp_writefile(a, stderr, 10); - fputs("\n e = ", 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); - mpmont_destroy(&mm); - assert(mparena_count(MPARENA_GLOBAL) == 0); - return ok; -} - - static test_chunk tests[] = { { "create", tcreate, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, { "mul", tmul, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, - { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, { 0, 0, { 0 } }, };