Add cyclic group abstraction, with test code. Separate off exponentation

[u/mdw/catacomb] / field.h

/* -*-c-*-
 *
 * $Id: field.h,v 1.9 2004/04/01 12:50:09 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.9  2004/04/01 12:50:09  mdw
 * Add cyclic group abstraction, with test code.  Separate off exponentation
 * functions for better static linking.  Fix a buttload of bugs on the way.
 * Generally ensure that negative exponents do inversion correctly.  Add
 * table of standard prime-field subgroups.  (Binary field subgroups are
 * currently unimplemented but easy to add if anyone ever finds a good one.)
 *
 * Revision 1.8  2004/03/27 17:54:11  mdw
 * Standard curves and curve checking.
 *
 * 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

#ifndef CATACOMB_QDPARSE_H
#  include "qdparse.h"
#endif

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

typedef struct field {
  const struct field_ops *ops;		/* Field operations */
  mp *zero, *one;			/* Identities in the field */
  mp *m;				/* Modulus (prime and binary) */
  unsigned long nbits;			/* Length of field element in bits */
  size_t noctets;			/* Length of element in octets */
} 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*/);
  int (*samep)(field */*f*/, field */*g*/);

  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_SAMEP(f, g)		(f)->ops->samep((f), (g))

#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*/);

/* --- @field_samep@ --- *
 *
 * Arguments:	@field *f, *g@ = two fields
 *
 * Returns:	Nonzero if the fields are identical (not just isomorphic).
 *
 * Use:		Checks for sameness of fields.  This function does the full
 *		check, not just the field-type-specific check done by the
 *		@sampep@ field operation.
 */

extern int field_samep(field */*f*/, field */*g*/);

/* --- @field_stdsamep@ --- *
 *
 * Arguments:	@field *f, *g@ = two fields
 *
 * Returns:	Nonzero if the fields are identical (not just isomorphic).
 *
 * Use:		Standard sameness check, based on equality of the @m@
 *		member.
 */

extern int field_stdsamep(field */*f*/, field */*g*/);

/*----- 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*/);

/* --- @field_parse@ --- *
 *
 * Arguments:	@qd_parse *qd@ = parser context
 *
 * Returns:	Field pointer if OK, or null.
 *
 * Use:		Parses a field description, which has the form
 *
 *		  * `prime', `niceprime' or `binpoly'
 *		  * an optional `:'
 *		  * the field modulus
 */

extern field *field_parse(qd_parse */*qd*/);

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

#ifdef __cplusplus
  }
#endif

#endif