X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/c141f4b60a664a91e0441d52e3010edd954cd8c3..21a7c4b1cffbf33a19e4cf421e29420187ed7a89:/mpbarrett.c diff --git a/mpbarrett.c b/mpbarrett.c new file mode 100644 index 0000000..e438d02 --- /dev/null +++ b/mpbarrett.c @@ -0,0 +1,288 @@ +/* -*-c-*- + * + * $Id: mpbarrett.c,v 1.1 1999/12/10 23:21:59 mdw Exp $ + * + * Barrett modular reduction + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: mpbarrett.c,v $ + * Revision 1.1 1999/12/10 23:21:59 mdw + * Barrett reduction support: works with even moduli. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "mp.h" +#include "mpbarrett.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @mpbarrett_create@ --- * + * + * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context + * @mp *m@ = modulus to work to + * + * + * Returns: --- + * + * Use: Initializes a Barrett reduction context ready for use. + */ + +void mpbarrett_create(mpbarrett *mb, mp *m) +{ + mp *b; + + /* --- Validate the arguments --- */ + + assert(((void)"Barrett modulus must be positive", (m->f & MP_NEG) == 0)); + + /* --- Compute %$\mu$% --- */ + + mp_shrink(m); + mb->k = MP_LEN(m); + mb->m = MP_COPY(m); + b = mp_lsl(MP_NEW, MP_ONE, 2 * MPW_BITS * mb->k); + mp_div(&b, 0, b, m); + mb->mu = b; +} + +/* --- @mpbarrett_destroy@ --- * + * + * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context + * + * Returns: --- + * + * Use: Destroys a Barrett reduction context releasing any resources + * claimed. + */ + +void mpbarrett_destroy(mpbarrett *mb) +{ + mp_drop(mb->m); + mp_drop(mb->mu); +} + +/* --- @mpbarrett_reduce@ --- * + * + * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context + * @mp *d@ = destination for result + * @mp *m@ = number to reduce + * + * Returns: The residue of @m@ modulo the number in the reduction + * context. + * + * Use: Performs an efficient modular reduction. The argument is + * assumed to be positive. + */ + +mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m) +{ + mp *q; + size_t k = mb->k; + + /* --- Special case if @m@ is too small --- */ + + if (MP_LEN(m) < k) { + m = MP_COPY(m); + MP_DROP(d); + return (m); + } + + /* --- First stage --- */ + + { + 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)); + } + + /* --- Second stage --- */ + + { + mp *r; + mpw *mvl; + + MP_COPY(m); + if (MP_LEN(m) <= k + 1) + mvl = m->vl; + 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); + 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); + d->f = (m->f | r->f) & MP_BURN; + MP_DROP(r); + MP_DROP(q); + MP_DROP(m); + } + + /* --- Final stage --- */ + + MP_SHRINK(d); + while (MPX_UCMP(d->v, d->vl, >=, mb->m->v, mb->m->vl)) + mpx_usub(d->v, d->vl, d->v, d->vl, mb->m->v, mb->m->vl); + + MP_SHRINK(d); + return (d); +} + +/* --- @mpbarrett_exp@ --- * + * + * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context + * @mp *d@ = fake destination + * @mp *a@ = base + * @mp *e@ = exponent + * + * Returns: Result, %$a^e \bmod m$%. + */ + +mp *mpbarrett_exp(mpbarrett *mb, mp *d, mp *a, mp *e) +{ + mpscan sc; + mp *x = MP_ONE; + mp *spare = MP_NEW; + + a = MP_COPY(a); + 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, 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; + } + sq++; + if (!MP_STEP(&sc)) + break; + } + } + + MP_DROP(a); + if (spare != MP_NEW) + MP_DROP(spare); + if (d != MP_NEW) + MP_DROP(d); + return (x); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +static int vmod(dstr *v) +{ + mp *x = *(mp **)v[0].buf; + mp *n = *(mp **)v[1].buf; + mp *r = *(mp **)v[2].buf; + mp *s; + mpbarrett mb; + int ok = 1; + + mpbarrett_create(&mb, n); + s = mpbarrett_reduce(&mb, MP_NEW, x); + + if (MP_CMP(s, !=, r)) { + fputs("\n*** barrett reduction failure\n", stderr); + fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); + fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr); + fputs("r = ", stderr); mp_writefile(r, stderr, 10); fputc('\n', stderr); + fputs("s = ", stderr); mp_writefile(s, stderr, 10); fputc('\n', stderr); + ok = 0; + } + + mpbarrett_destroy(&mb); + mp_drop(x); + mp_drop(n); + mp_drop(r); + mp_drop(s); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +static int vexp(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; + + mpbarrett mb; + mpbarrett_create(&mb, m); + + mr = mpbarrett_exp(&mb, MP_NEW, a, b); + + if (MP_CMP(mr, !=, r)) { + fputs("\n*** barrett 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); + mpbarrett_destroy(&mb); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return ok; +} + +static test_chunk tests[] = { + { "mpbarrett-reduce", vmod, { &type_mp, &type_mp, &type_mp, 0 } }, + { "mpbarrett-exp", vexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + sub_init(); + test_run(argc, argv, tests, SRCDIR "/tests/mpbarrett"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/