math/mpreduce.h: Missing include files.

[u/mdw/catacomb] / math / ec-exp.c

/* -*-c-*-
 *
 * Point multiplication for elliptic curves
 *
 * (c) 2004 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.
 */

/*----- Header files ------------------------------------------------------*/

#include "ec.h"
#include "ec-exp.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @ec_imul@, @ec_mul@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p@ = pointer to the generator point
 *		@mp *n@ = integer multiplier
 *
 * Returns:	The destination @d@.
 *
 * Use:		Multiplies a point by a scalar, returning %$n p$%.  The
 *		@imul@ variant uses internal representations for argument
 *		and result.
 */

ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
{
  ec t = EC_INIT;

  EC_COPY(&t, p);
  if (t.x && (n->f & MP_BURN))
    t.x->f |= MP_BURN;
  MP_SHRINK(n);
  EC_SETINF(d);
  if (MP_ZEROP(n))
    ;
  else {
    if (MP_NEGP(n))
      EC_NEG(c, &t, &t);
    if (MP_LEN(n) < EXP_THRESH)
      EXP_SIMPLE(*d, t, n);
    else
      EXP_WINDOW(*d, t, n);
  }
  EC_DESTROY(&t);
  return (d);
}

ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
{
  EC_IN(c, d, p);
  ec_imul(c, d, d, n);
  return (EC_OUT(c, d, d));
}

/* --- @ec_mmul@, @ec_immul@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec_mulfactor *f@ = pointer to vector of factors
 *		@size_t n@ = number of factors
 *
 * Returns:	The destination @d@.
 *
 * Use:		Does simultaneous point multiplication.  The @immul@ variant
 *		uses internal representations for arguments and result.
 */

#undef EXP_WINSZ
#define EXP_WINSZ 3

static ec *immul(ec_curve *c, ec *d, ec_mulfactor *f, size_t n)
{
  size_t i;

  for (i = 0; i < n; i++) {
    MP_SHRINK(f[i].exp);
    if (MP_NEGP(f[i].exp))
      EC_NEG(c, &f[i].base, &f[i].base);
    if (f[i].base.x && f[i].exp->f & MP_BURN)
      f[i].base.x->f |= MP_BURN;
  }
  EC_SETINF(d);
  EXP_SIMUL(*d, f, n);
  for (i = 0; i < n; i++)
    EC_DESTROY(&f[i].base);
  xfree(f);
  return (d);
}

ec *ec_immul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
{
  ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
  size_t i;

  for (i = 0; i < n; i++) {
    EC_CREATE(&ff[i].base);
    EC_COPY(&ff[i].base, &f[i].base);
    ff[i].exp = f[i].exp;
  }
  return (immul(c, d, ff, n));
}

ec *ec_mmul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
{
  ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
  size_t i;

  for (i = 0; i < n; i++) {
    EC_CREATE(&ff[i].base);
    EC_IN(c, &ff[i].base, &f[i].base);
    ff[i].exp = f[i].exp;
  }
  immul(c, d, ff, n);
  return (EC_OUT(c, d, d));
}

/*----- That's all, folks -------------------------------------------------*/