.gitignore: Ignore `auto-version' script.

[u/mdw/catacomb] / field.h

/* -*-c-*-
 *
 * $Id$
 *
 * 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.
 */

#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 */
  mp *q;				/* Number of elements in 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*/);
  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*/);

/*----- Arithmetic --------------------------------------------------------*/

/* --- @field_exp@ --- *
 *
 * Arguments:	@field *f@ = pointer to field
 *		@mp *d@ = fake destination
 *		@mp *a@ = base
 *		@mp *e@ = exponent
 *
 * Returns:	Result, %$a^e$%.
 *
 * Use:		Exponentiation in a finite field.  Note that all quantities
 *		are in internal format.  This is a generic implementation
 *		suitable for use with all fields and is not intended to be
 *		optimal.
 */

extern mp *field_exp(field */*f*/, mp */*d*/, mp */*a*/, mp */*e*/);

/*----- 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, or null.
 *
 * 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_binnorm@ --- *
 *
 * Arguments:	@mp *p@ = the reduction polynomial
 *		@mp *beta@ = representation of normal point
 *
 * Returns:	A pointer to the field.
 *
 * Use:		Creates a field structure for a binary field mod @p@ which
 *		uses a normal basis representation externally.  Computations
 *		are still done on a polynomial-basis representation.
 */

extern field *field_binnorm(mp */*p*/, mp */*beta*/);

/* --- @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', `binpoly', or `binnorm'
 *		  * an optional `:'
 *		  * the field modulus
 *		  * for `binnorm', an optional `,' and the beta value
 */

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

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

#ifdef __cplusplus
  }
#endif

#endif