Implement efficient reduction for pleasant-looking primes.

[u/mdw/catacomb] / field.h

/* -*-c-*-
 *
 * $Id: field.h,v 1.7 2004/03/27 00:04:46 mdw Exp $
 *
 * Definitions for field arithmetic
 *
 * (c) 2000 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: field.h,v $
 * Revision 1.7  2004/03/27 00:04:46  mdw
 * Implement efficient reduction for pleasant-looking primes.
 *
 * Revision 1.6  2004/03/23 15:19:32  mdw
 * Test elliptic curves more thoroughly.
 *
 * Revision 1.5  2004/03/23 12:08:26  mdw
 * Random field-element selection.
 *
 * Revision 1.4  2004/03/21 22:52:06  mdw
 * Merge and close elliptic curve branch.
 *
 * Revision 1.3.4.2  2004/03/21 22:39:46  mdw
 * Elliptic curves on binary fields work.
 *
 * Revision 1.3.4.1  2004/03/20 00:13:31  mdw
 * Projective coordinates for prime curves
 *
 * Revision 1.3  2002/01/13 13:48:44  mdw
 * Further progress.
 *
 * Revision 1.2  2001/05/07 17:30:13  mdw
 * Add an internal-representation no-op function.
 *
 * Revision 1.1  2001/04/29 18:12:33  mdw
 * Prototype version.
 *
 */

#ifndef CATACOMB_FIELD_H
#define CATACOMB_FIELD_H

#ifdef __cplusplus
  extern "C" {
#endif

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

#ifndef CATACOMB_GRAND_H
#  include "grand.h"
#endif

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

/*----- Data structures ---------------------------------------------------*/

typedef struct field {
  const struct field_ops *ops;		/* Field operations */
  mp *zero, *one;			/* Identities in the field */
} field;

enum {
  FTY_PRIME,
  FTY_BINARY
};

typedef struct field_ops {

  /* --- General information --- */

  unsigned ty;				/* What kind of field this is */
  const char *name;			/* Human-readable name string */

  /* --- Universal operations --- */

  void (*destroy)(field */*f*/);
  mp *(*rand)(field */*f*/, mp */*d*/, grand */*r*/);

  mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);

  int (*zerop)(field */*f*/, mp */*x*/);
  mp *(*neg)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/);
  mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/);

  /* --- Operations for binary fields only --- */

  mp *(*quadsolve)(field */*f*/, mp */*d*/, mp */*x*/);

  /* --- Operations for prime fields only --- */

  mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*qdl)(field */*f*/, mp */*d*/, mp */*x*/);
  mp *(*hlv)(field */*f*/, mp */*d*/, mp */*x*/);

} field_ops;

#define F_TYPE(f)		(f)->ops->ty
#define F_NAME(f)		(f)->ops->name

#define F_DESTROY(f)		(f)->ops->destroy((f))
#define F_RAND(f, d, r)		(f)->ops->rand((f), (d), (r))

#define F_IN(f, d, x)		(f)->ops->in((f), (d), (x))
#define F_OUT(f, d, x)		(f)->ops->out((f), (d), (x))

#define F_ZEROP(f, x)		(f)->ops->zerop((f), (x))
#define F_NEG(f, d, x)		(f)->ops->neg((f), (d), (x))
#define F_ADD(f, d, x, y)	(f)->ops->add((f), (d), (x), (y))
#define F_SUB(f, d, x, y)	(f)->ops->sub((f), (d), (x), (y))
#define F_MUL(f, d, x, y)	(f)->ops->mul((f), (d), (x), (y))
#define F_SQR(f, d, x)		(f)->ops->sqr((f), (d), (x))
#define F_INV(f, d, x)		(f)->ops->inv((f), (d), (x))
#define F_REDUCE(f, d, x)	(f)->ops->reduce((f), (d), (x))
#define F_SQRT(f, d, x)		(f)->ops->sqrt((f), (d), (x))

#define F_QUADSOLVE(f, d, x)	(f)->ops->quadsolve((f), (d), (x))

#define F_DBL(f, d, x)		(f)->ops->dbl((f), (d), (x))
#define F_TPL(f, d, x)		(f)->ops->tpl((f), (d), (x))
#define F_QDL(f, d, x)		(f)->ops->qdl((f), (d), (x))
#define F_HLV(f, d, x)		(f)->ops->hlv((f), (d), (x))

/*----- Helpful field operations ------------------------------------------*/

/* --- @field_id@ --- *
 *
 * Arguments:	@field *f@ = pointer to a field
 *		@mp *d@ = a destination element
 *		@mp *x@ = a source element
 *
 * Returns:	The result element.
 *
 * Use:		An identity operation which can be used if your field has no
 *		internal representation.
 */

extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);

/*----- Creating fields ---------------------------------------------------*/

/* --- @field_prime@ --- *
 *
 * Arguments:	@mp *p@ = the characteristic of the field
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a prime field of size %$p$%,
 *		using Montgomery reduction for arithmetic.
 */

extern field *field_prime(mp */*p*/);

/* --- @field_niceprime@ --- *
 *
 * Arguments:	@mp *p@ = the characteristic of the field
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a prime field of size %$p$%,
 *		using efficient reduction for nice primes.
 */

extern field *field_niceprime(mp */*p*/);

/* --- @field_binpoly@ --- *
 *
 * Arguments:	@mp *p@ = an irreducible polynomial over %$\gf{2}$%
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a binary field using naive
 *		arithmetic.
 */

extern field *field_binpoly(mp */*p*/);

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

#ifdef __cplusplus
  }
#endif

#endif